Dada una array de strings Arr[] . La tarea es clasificarlos en orden lexicográfico .
Ejemplos:
Entrada: Arr[] = {“ordenar”, “este”, “lista”}
Salida: [listar, ordenar, esto]Entrada: Arr[] = {“sol”, “tierra”, “marte”, “mercurio”}
Salida: [tierra, marte, mercurio, sol]
Enfoque de clasificación por selección: el mismo problema también se puede resolver utilizando la clasificación por selección .
El algoritmo de ordenación por selección ordena una array encontrando repetidamente el elemento mínimo (considerando el orden ascendente) de la parte no ordenada y colocándolo al principio
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to sort
// array of strings
#include <bits/stdc++.h>
using namespace std;
// Function to compare 2 words
bool isAlphabeticallySmaller(string str1, string str2)
{
transform(str1.begin(), str1.end(), str1.begin(),
::toupper);
transform(str2.begin(), str2.end(), str2.begin(),
::toupper);
if (str1 < str2) {
return true;
}
return false;
}
void selectionSort(vector<string>& arr)
{
int n = arr.size();
// One by one move boundary of
// unsorted subarray
for (int i = 0; i < n - 1; i++) {
// Find the minimum element
// in unsorted array
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (isAlphabeticallySmaller(arr[j],
arr[min_idx]))
min_idx = j;
// Swap the found minimum
// element with the first element
string temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
// Driver code
int main()
{
vector<string> Arr
= { "sun", "earth", "mars", "mercury" };
int N = Arr.size();
selectionSort(Arr);
for (int i = 0; i < N; i++) {
cout << Arr[i] << "\n";
}
// This code is contributed by rakeshsahni
return 0;
}
Java
// Java Program to sort
// array of strings
class GFG {
static void selectionSort(String[] arr)
{
int n = arr.length;
// One by one move boundary of
// unsorted subarray
for (int i = 0; i < n - 1; i++) {
// Find the minimum element
// in unsorted array
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (isAlphabeticallySmaller(
arr[j], arr[min_idx]))
min_idx = j;
// Swap the found minimum
// element with the first element
String temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
// Function to compare 2 words
static boolean isAlphabeticallySmaller(
String str1, String str2)
{
str1 = str1.toUpperCase();
str2 = str2.toUpperCase();
if (str1.compareTo(str2) < 0) {
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
String[] Arr
= { "sun", "earth", "mars", "mercury" };
int N = Arr.length;
selectionSort(Arr);
for (int i = 0; i < N; i++) {
System.out.println(Arr[i]);
}
}
}
Python3
# Python3 code for the above approach # function perform selection sorting on the array def selectionSort(arr): n = len(arr) # One by one move boundary of # unsorted subarray for i in range(n - 1): # Find the minimum element # in unsorted array min_idx = i for j in range(i + 1, n): if (isAlphabeticallySmaller(arr[j], arr[min_idx])): min_idx = j # Swap the found minimum # element with the first element temp = arr[min_idx] arr[min_idx] = arr[i] arr[i] = temp return arr # Function to compare 2 words def isAlphabeticallySmaller(str1, str2): str1 = str1.upper() str2 = str2.upper() if str1 < str2: return True return False # Driver code Arr = ["sun", "earth", "mars", "mercury"] N = len(Arr) # function call Arr = selectionSort(Arr) for word in Arr: print(word) # This code is contributed by phasing17
C#
// C# Program to sort
// array of strings
using System;
public class GFG
{
static void selectionSort(string[] arr)
{
int n = arr.Length;
// One by one move boundary of
// unsorted subarray
for (int i = 0; i < n - 1; i++) {
// Find the minimum element
// in unsorted array
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (isAlphabeticallySmaller(
arr[j], arr[min_idx]))
min_idx = j;
// Swap the found minimum
// element with the first element
String temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
// Function to compare 2 words
static bool isAlphabeticallySmaller(
string str1, String str2)
{
str1 = str1.ToUpper();
str2 = str2.ToUpper();
if (str1.CompareTo(str2) < 0) {
return true;
}
return false;
}
// Driver code
static public void Main (){
string[] Arr = { "sun", "earth", "mars", "mercury" };
int N = Arr.Length;
selectionSort(Arr);
for (int i = 0; i < N; i++) {
Console.WriteLine(Arr[i]);
}
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript code for the above approach
function selectionSort(arr)
{
let n = arr.length;
// One by one move boundary of
// unsorted subarray
for (let i = 0; i < n - 1; i++) {
// Find the minimum element
// in unsorted array
let min_idx = i;
for (let j = i + 1; j < n; j++)
if (isAlphabeticallySmaller(
arr[j], arr[min_idx]))
min_idx = j;
// Swap the found minimum
// element with the first element
let temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
// Function to compare 2 words
function isAlphabeticallySmaller(
str1, str2)
{
str1 = str1.toUpperCase();
str2 = str2.toUpperCase();
if (str1.localeCompare(str2) == -1) {
return true;
}
return false;
}
// Driver Code
let Arr
= [ "sun", "earth", "mars", "mercury" ];
let N = Arr.length;
selectionSort(Arr);
for (let i = 0; i < N; i++) {
document.write(Arr[i] + "<br/>");
}
// This code is contributed by sanjoy_62.
</script>
Producción
earth mars mercury sun
Complejidad de Tiempo: O(K * N 2 )
Espacio Auxiliar: O(K)
Método de clasificación de burbujas: el enfoque básico para clasificar las strings dadas en orden lexicográfico es mediante el uso de clasificación de burbujas .
En Bubble sort, las dos strings sucesivas Arr[i] y Arr[i+1] se intercambian siempre que arr[i]> arr[i+1]. Al final de cada paso, los valores más pequeños gradualmente «burbujean» hacia arriba hasta la parte superior y, por lo tanto, se denominan clasificación de burbuja.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to compare 2 words
bool isAlphabeticallySmaller(
string str1, string str2)
{
transform(str1.begin(), str1.end(), str1.begin(),
::toupper);
transform(str2.begin(), str2.end(), str2.begin(),
::toupper);
if (str1 < str2) {
return true;
}
return false;
}
void bubbleSort(vector<string> &arr, int n)
{
int i, j;
string temp;
bool swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (isAlphabeticallySmaller(
arr[j + 1], arr[j])) {
// Swap arr[j] and arr[j+1]
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no two elements were
// swapped by inner loop,
// then break
if (swapped == false)
break;
}
}
// Driver code
int main()
{
vector<string> Arr
= { "sun", "earth", "mars", "mercury" };
int N = Arr.size();
bubbleSort(Arr,N);
for (int i = 0; i < N; i++) {
cout << Arr[i] << "\n";
}
return 0;
}
// This code is contributed by Pushpesh Raj
Java
// Java code for the above approach:
public class GFG {
static void bubbleSort(String[] arr, int n)
{
int i, j;
String temp;
boolean swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (isAlphabeticallySmaller(
arr[j + 1], arr[j])) {
// Swap arr[j] and arr[j+1]
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no two elements were
// swapped by inner loop,
// then break
if (swapped == false)
break;
}
}
// Function to compare 2 words
static boolean isAlphabeticallySmaller(
String str1, String str2)
{
str1 = str1.toUpperCase();
str2 = str2.toUpperCase();
if (str1.compareTo(str2) < 0) {
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
String[] Arr
= { "sun", "earth", "mars", "mercury" };
int N = Arr.length;
bubbleSort(Arr, N);
for (int i = 0; i < N; i++) {
System.out.println(Arr[i]);
}
}
}
C#
// C# code for the above approach:
// Include namespace system
using System;
public class GFG {
public static void bubbleSort(String[] arr, int n)
{
int i;
int j;
String temp;
bool swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (GFG.isAlphabeticallySmaller(arr[j + 1],
arr[j])) {
// Swap arr[j] and arr[j+1]
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no two elements were
// swapped by inner loop,
// then break
if (swapped == false) {
break;
}
}
}
// Function to compare 2 words
public static bool isAlphabeticallySmaller(String str1,
String str2)
{
str1 = str1.ToUpper();
str2 = str2.ToUpper();
if (string.CompareOrdinal(str1, str2) < 0) {
return true;
}
return false;
}
// Driver code
public static void Main(String[] args)
{
String[] Arr
= { "sun", "earth", "mars", "mercury" };
var N = Arr.Length;
GFG.bubbleSort(Arr, N);
for (int i = 0; i < N; i++) {
Console.WriteLine(Arr[i]);
}
}
}
// This code is contributed by mukulsomukesh
Producción
earth mars mercury sun
Producción
earth mars mercury sun
Complejidad temporal: O(K * N 2 ) donde K es la longitud de cada palabra.
Espacio Auxiliar: O(K)
Método de ordenación por inserción: el problema también se puede resolver mediante la ordenación por inserción .
En la ordenación por inserción, la array se divide virtualmente en una parte ordenada y otra no ordenada. Los valores de la parte no ordenada se seleccionan y colocan en la posición correcta en la parte ordenada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to compare 2 words
bool isAlphabeticallySmaller(
string str1, string str2)
{
transform(str1.begin(), str1.end(), str1.begin(),
::toupper);
transform(str2.begin(), str2.end(), str2.begin(),
::toupper);
if (str1 < str2) {
return true;
}
return false;
}
// Function to sort array
// using insertion sort
void insertionSort(vector<string> &arr)
{
int n = arr.size();
for (int i = 1; i < n; ++i) {
string key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1],
// that are greater than key,
// to one position ahead
// of their current position
while (j >= 0
&& isAlphabeticallySmaller(key, arr[j])) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// Driver code
int main()
{
vector<string> Arr
= { "sun", "earth", "mars", "mercury" };
int N = Arr.size();
insertionSort(Arr);
for (int i = 0; i < N; i++) {
cout << Arr[i] << "\n";
}
return 0;
}
// This code is contributed by Pushpesh Raj
Java
// Java program to sort array of strings
class GFG {
// Function to sort array
// using insertion sort
static void insertionSort(String[] arr)
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
String key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1],
// that are greater than key,
// to one position ahead
// of their current position
while (j >= 0
&& isAlphabeticallySmaller(key, arr[j])) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// Function to compare 2 words
static boolean isAlphabeticallySmaller(
String str1, String str2)
{
str1 = str1.toUpperCase();
str2 = str2.toUpperCase();
if (str1.compareTo(str2) < 0) {
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
String[] Arr
= { "sun", "earth", "mars", "mercury" };
int N = Arr.length;
insertionSort(Arr);
for (int i = 0; i < N; i++) {
System.out.println(Arr[i]);
}
}
}
C#
// Include namespace system
using System;
// C# code for the above approach:
public class GFG
{
public static void bubbleSort(String[] arr, int n)
{
int i;
int j;
String temp;
bool swapped;
for (i = 0; i < n - 1; i++)
{
swapped = false;
for (j = 0; j < n - i - 1; j++)
{
if (GFG.isAlphabeticallySmaller(arr[j + 1], arr[j]))
{
// Swap arr[j] and arr[j+1]
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no two elements were
// swapped by inner loop,
// then break
if (swapped == false)
{
break;
}
}
}
// Function to compare 2 words
public static bool isAlphabeticallySmaller(String str1, String str2)
{
str1 = str1.ToUpper();
str2 = str2.ToUpper();
if (string.CompareOrdinal(str1,str2) < 0)
{
return true;
}
return false;
}
// Driver code
public static void Main(String[] args)
{
String[] Arr = {"sun", "earth", "mars", "mercury"};
var N = Arr.Length;
GFG.bubbleSort(Arr, N);
for (int i = 0; i < N; i++)
{
Console.WriteLine(Arr[i]);
}
}
}
// This code is contributed by mukulsomukesh
Producción
earth mars mercury sun
Producción
earth mars mercury sun
Complejidad de Tiempo: O(K * N 2 )
Espacio Auxiliar: O(K)
Enfoque eficiente: la idea de resolver el problema de manera más eficiente es usar Merge Sort en las strings.
Merge Sort es un algoritmo Divide and Conquer . Divide la array de entrada en dos mitades, se llama a sí mismo para las dos mitades y luego fusiona las dos mitades ordenadas.
Siga los pasos a continuación para implementar este enfoque:
Si la array tiene más de 1 elemento,
- Divide la array Arr[] en dos mitades iguales.
- Llame a mergeSort() para la primera mitad y luego la segunda mitad.
- Combine la array ordenada devuelta de las llamadas anteriores y devuelva la array combinada.
De lo contrario, si la array tiene solo 1 elemento,
- devuelve una array que consta solo de este elemento.
Función para fusionar 2 arrays ordenadas de strings:
- Cree una array, digamos arr3[] .
- Tome otro puntero , diga ‘idx’ inicializado en 0.
- Atraviese ambas arrays simultáneamente usando 2 punteros ( digamos i y j )
- Si arr1[i] es lexicográficamente más pequeño que arr2[j] .
- Almacenar arr1[i] en arr3[idx]
- Aumenta i e idx en 1.
- Más
- Almacenar arr2[j] en arr3[idx]
- Aumente j e idx en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to sort
// arrays of strings using merge sort
#include <bits/stdc++.h>
using namespace std;
// Function to compare 2 words
bool isAlphabeticallySmaller(string str1, string str2)
{
transform(str1.begin(), str1.end(), str1.begin(),
::toupper);
transform(str2.begin(), str2.end(), str2.begin(),
::toupper);
if (str1 < str2) {
return true;
}
return false;
}
vector<string> merge(vector<string> Arr1,
vector<string> Arr2)
{
int m = Arr1.size();
int n = Arr2.size();
vector<string> Arr3;
int idx = 0;
int i = 0;
int j = 0;
while (i < m && j < n) {
if (isAlphabeticallySmaller(Arr1[i], Arr2[j])) {
Arr3.push_back(Arr1[i]);
i++;
idx++;
}
else {
Arr3.push_back(Arr2[j]);
j++;
idx++;
}
}
while (i < m) {
Arr3.push_back(Arr1[i]);
i++;
idx++;
}
while (j < n) {
Arr3.push_back(Arr2[j]);
j++;
idx++;
}
return Arr3;
}
// Function to mergeSort 2 arrays
vector<string> mergeSort(vector<string> Arr, int lo, int hi)
{
if (lo == hi) {
vector<string> A = { Arr[lo] };
return A;
}
int mid = lo + (hi - lo) / 2;
vector<string> arr1 = mergeSort(Arr, lo, mid);
vector<string> arr2 = mergeSort(Arr, mid + 1, hi);
vector<string> arr3 = merge(arr1, arr2);
return arr3;
}
// Driver code
int main()
{
vector<string> Arr
= { "sun", "earth", "mars", "mercury" };
int N = Arr.size();
vector<string> a = mergeSort(Arr, 0, N - 1);
for (int i = 0; i < N; i++) {
cout << a[i] << "\n";
}
return 0;
}
// This code is contributed by karandeep1234.
Java
// Java program to sort
// arrays of strings using merge sort
class GFG {
// Function to mergeSort 2 arrays
static String[] mergeSort(String[] Arr,
int lo, int hi)
{
if (lo == hi) {
String[] A = { Arr[lo] };
return A;
}
int mid = lo + (hi - lo) / 2;
String[] arr1 = mergeSort(Arr, lo, mid);
String[] arr2 = mergeSort(Arr, mid + 1, hi);
String[] arr3 = merge(arr1, arr2);
return arr3;
}
static String[] merge(
String[] Arr1, String[] Arr2)
{
int m = Arr1.length;
int n = Arr2.length;
String[] Arr3 = new String[m + n];
int idx = 0;
int i = 0;
int j = 0;
while (i < m && j < n) {
if (isAlphabeticallySmaller(
Arr1[i], Arr2[j])) {
Arr3[idx] = Arr1[i];
i++;
idx++;
}
else {
Arr3[idx] = Arr2[j];
j++;
idx++;
}
}
while (i < m) {
Arr3[idx] = Arr1[i];
i++;
idx++;
}
while (j < n) {
Arr3[idx] = Arr2[j];
j++;
idx++;
}
return Arr3;
}
// Return true if str1 appears before
// str2 in alphabetical order
static boolean isAlphabeticallySmaller(
String str1, String str2)
{
str1 = str1.toUpperCase();
str2 = str2.toUpperCase();
if (str1.compareTo(str2) < 0) {
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
String[] Arr
= { "sun", "earth", "mars", "mercury" };
String[] a = mergeSort(Arr, 0, Arr.length - 1);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
Producción
earth mars mercury sun
Complejidad de tiempo: O(K * N * (log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por karandeep1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA