Dada una array arr[] que contiene N enteros no negativos, la tarea es ordenar estos enteros alfabéticamente cuando cada número se convierte en palabras .
Ejemplos:
Entrada: arr[] = {12, 10, 102, 31, 15}
Salida: 15 102 10 31 12
Explicación:
El conjunto de números anterior está ordenado alfabéticamente. Es decir:
15 -> Quince
102 -> Ciento dos
10 -> Diez
31 -> Treinta y uno
12 -> DoceEntrada: arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
Salida: 8 5 4 9 1 7 6 10 3 2
Explicación:
El conjunto de números anterior está ordenado alfabéticamente. Es decir:
8 -> ocho
5 -> cinco
4 -> cuatro
9 -> nueve
1 -> uno
7 -> siete
6 -> seis
10 -> diez
3 -> tres
2 -> dos
Enfoque: para ordenar los números alfabéticamente, primero debemos convertir el número a su forma de palabra. Por lo tanto, la idea es almacenar cada elemento junto con su forma de palabra en un par de vectores y luego clasificar todos los elementos del vector de acuerdo con las palabras correspondientes del número. Por lo tanto:
- Calcule previamente y almacene las formas de las palabras de todos los dígitos de las unidades en una array.
- Calcule previamente y almacene las formas de las palabras de todos los dígitos de las decenas en otra array.
- Para todos los números restantes mayores de 2 dígitos, el número se divide y se suma la forma de palabra.
- Recorre cada dígito del número en la array arr[] y almacena la forma de palabra correspondiente de los números en un vector como un par.
- Iterar a través del vector y ordenar el vector según las palabras.
- Finalmente, imprima el orden ordenado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to sort an array of
// integers alphabetically
#include <bits/stdc++.h>
using namespace std;
// Variable to store the word form of
// units digit and up to twenty
string one[]
= { "", "one ", "two ", "three ",
"four ", "five ", "six ",
"seven ", "eight ", "nine ", "ten ",
"eleven ", "twelve ", "thirteen ",
"fourteen ", "fifteen ", "sixteen ",
"seventeen ", "eighteen ", "nineteen " };
// Variable to store the word form of
// tens digit
string ten[]
= { "", "", "twenty ",
"thirty ", "forty ",
"fifty ", "sixty ",
"seventy ", "eighty ",
"ninety " };
// Function to convert a two digit number
// to the word by using the above defined arrays
string numToWords(int n, string s)
{
string str = "";
// If n is more than 19, divide it
if (n > 19)
str += ten[n / 10] + one[n % 10];
else
str += one[n];
// If n is non-zero
if (n)
str += s;
return str;
}
// Function to print a given number in words
string convertToWords(int n)
{
// Stores the word representation
// of the given number n
string out;
// Handles digits at ten millions
// and hundred millions places
out += numToWords((n / 10000000),
"crore ");
// Handles digits at hundred thousands
// and one millions places
out += numToWords(((n / 100000) % 100),
"lakh ");
// Handles digits at thousands and
// tens thousands places
out += numToWords(((n / 1000) % 100),
"thousand ");
// Handles digit at hundreds places
out += numToWords(((n / 100) % 10),
"hundred ");
if (n > 100 && n % 100)
out += "and ";
// Call the above function to convert
// the number into words
out += numToWords((n % 100), "");
return out;
}
// Function to sort the array according to
// the albhabetical order
void sortArr(int arr[], int n)
{
// Vector to store the number in words
// with respective elements
vector<pair<string, int> > vp;
// Inserting number in words
// with respective elements in vector pair
for (int i = 0; i < n; i++) {
vp.push_back(make_pair(
convertToWords(arr[i]), arr[i]));
}
// Sort the vector, this will sort the pair
// according to the alphabetical order.
sort(vp.begin(), vp.end());
// Print the sorted vector content
for (int i = 0; i < vp.size(); i++)
cout << vp[i].second << " ";
}
// Driver code
int main()
{
int arr[] = { 12, 10, 102, 31, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
sortArr(arr, n);
return 0;
}
Java
// Java program to sort an array of
// integers alphabetically
import java.util.*;
class GFG{
static class pair implements Comparable<pair>
{
String first;
int second;
public pair(String first, int second)
{
this.first = first;
this.second = second;
}
@Override
public int compareTo(pair o)
{
// TODO Auto-generated method stub
return this.first.compareTo(o.first);
}
}
// Variable to store the word form of
// units digit and up to twenty
static String one[]
= { "", "one ", "two ", "three ",
"four ", "five ", "six ",
"seven ", "eight ", "nine ", "ten ",
"eleven ", "twelve ", "thirteen ",
"fourteen ", "fifteen ", "sixteen ",
"seventeen ", "eighteen ", "nineteen " };
// Variable to store the word form of
// tens digit
static String ten[]
= { "", "", "twenty ",
"thirty ", "forty ",
"fifty ", "sixty ",
"seventy ", "eighty ",
"ninety " };
// Function to convert a two digit number
// to the word by using the above defined arrays
static String numToWords(int n, String s)
{
String str = "";
// If n is more than 19, divide it
if (n > 19)
str += ten[n / 10] + one[n % 10];
else
str += one[n];
// If n is non-zero
if (n>0)
str += s;
return str;
}
// Function to print a given number in words
static String convertToWords(int n)
{
// Stores the word representation
// of the given number n
String out = "";
// Handles digits at ten millions
// and hundred millions places
out += numToWords((n / 10000000),
"crore ");
// Handles digits at hundred thousands
// and one millions places
out += numToWords(((n / 100000) % 100),
"lakh ");
// Handles digits at thousands and
// tens thousands places
out += numToWords(((n / 1000) % 100),
"thousand ");
// Handles digit at hundreds places
out += numToWords(((n / 100) % 10),
"hundred ");
if (n > 100 && n % 100!=0)
out += "and ";
// Call the above function to convert
// the number into words
out += numToWords((n % 100), "");
return out;
}
// Function to sort the array according to
// the albhabetical order
static void sortArr(int arr[], int n)
{
// Vector to store the number in words
// with respective elements
Vector<pair> vp = new Vector<pair>();
// Inserting number in words
// with respective elements in vector pair
for (int i = 0; i < n; i++) {
vp.add(new pair(
convertToWords(arr[i]), arr[i]));
}
// Sort the vector, this will sort the pair
// according to the alphabetical order.
Collections.sort(vp);
// Print the sorted vector content
for (int i = 0; i < vp.size(); i++)
System.out.print(vp.get(i).second+ " ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12, 10, 102, 31, 15 };
int n = arr.length;
sortArr(arr, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to sort an array of # integers alphabetically # Variable to store the word form of # units digit and up to twenty one = [ "", "one ", "two ", "three ", "four ", "five ", "six ", "seven ", "eight ", "nine ", "ten ", "eleven ", "twelve ", "thirteen ", "fourteen ", "fifteen ", "sixteen ", "seventeen ", "eighteen ", "nineteen " ] # Variable to store the word form of # tens digit ten = [ "", "", "twenty ", "thirty ", "forty ", "fifty ", "sixty ", "seventy ", "eighty ", "ninety " ] # Function to convert a two digit number # to the word by using the above defined arrays def numToWords(n, s): st = "" # If n is more than 19, divide it if (n > 19): st += ten[n // 10] + one[n % 10] else: st += one[n] # If n is non-zero if (n): st += s return st # Function to print a given number in words def convertToWords(n): # Stores the word representation # of the given number n out = "" # Handles digits at ten millions # and hundred millions places out += numToWords((n // 10000000), "crore ") # Handles digits at hundred thousands # and one millions places out += numToWords(((n // 100000) % 100), "lakh ") # Handles digits at thousands and # tens thousands places out += numToWords(((n // 1000) % 100), "thousand ") # Handles digit at hundreds places out += numToWords(((n // 100) % 10), "hundred ") if (n > 100 and n % 100): out += "and " # Call the above function to convert # the number into words out += numToWords((n % 100), "") return out # Function to sort the array according to # the albhabetical order def sortArr(arr, n): # Vector to store the number in words # with respective elements vp = [] # Inserting number in words # with respective elements in vector pair for i in range(n): vp.append((convertToWords(arr[i]), arr[i])); # Sort the vector, this will sort the pair # according to the alphabetical order. vp.sort() # Print the sorted vector content for i in range(len(vp)): print (vp[i][1], end = " ") # Driver code if __name__ == "__main__": arr = [ 12, 10, 102, 31, 15 ] n = len(arr) sortArr(arr, n) # This code is contributed by chitranayal
C#
// C# program to sort an array of
// integers alphabetically
using System;
using System.Collections.Generic;
public class GFG{
class pair : IComparable<pair>
{
public String first;
public int second;
public pair(String first, int second)
{
this.first = first;
this.second = second;
}
public int CompareTo(pair o)
{
return this.first.CompareTo(o.first);
}
}
// Variable to store the word form of
// units digit and up to twenty
static String []one
= { "", "one ", "two ", "three ",
"four ", "five ", "six ",
"seven ", "eight ", "nine ", "ten ",
"eleven ", "twelve ", "thirteen ",
"fourteen ", "fifteen ", "sixteen ",
"seventeen ", "eighteen ", "nineteen " };
// Variable to store the word form of
// tens digit
static String []ten
= { "", "", "twenty ",
"thirty ", "forty ",
"fifty ", "sixty ",
"seventy ", "eighty ",
"ninety " };
// Function to convert a two digit number
// to the word by using the above defined arrays
static String numToWords(int n, String s)
{
String str = "";
// If n is more than 19, divide it
if (n > 19)
str += ten[n / 10] + one[n % 10];
else
str += one[n];
// If n is non-zero
if (n>0)
str += s;
return str;
}
// Function to print a given number in words
static String convertToWords(int n)
{
// Stores the word representation
// of the given number n
String Out = "";
// Handles digits at ten millions
// and hundred millions places
Out += numToWords((n / 10000000),
"crore ");
// Handles digits at hundred thousands
// and one millions places
Out += numToWords(((n / 100000) % 100),
"lakh ");
// Handles digits at thousands and
// tens thousands places
Out += numToWords(((n / 1000) % 100),
"thousand ");
// Handles digit at hundreds places
Out += numToWords(((n / 100) % 10),
"hundred ");
if (n > 100 && n % 100!=0)
Out += "and ";
// Call the above function to convert
// the number into words
Out += numToWords((n % 100), "");
return Out;
}
// Function to sort the array according to
// the albhabetical order
static void sortArr(int []arr, int n)
{
// List to store the number in words
// with respective elements
List<pair> vp = new List<pair>();
// Inserting number in words
// with respective elements in vector pair
for (int i = 0; i < n; i++) {
vp.Add(new pair(
convertToWords(arr[i]), arr[i]));
}
// Sort the vector, this will sort the pair
// according to the alphabetical order.
vp.Sort();
// Print the sorted vector content
for (int i = 0; i < vp.Count; i++)
Console.Write(vp[i].second+ " ");
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 12, 10, 102, 31, 15 };
int n = arr.Length;
sortArr(arr, n);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript implementation of the above approach
// Variable to store the word form of
// units digit and up to twenty
var one
= [ "", "one ", "two ", "three ",
"four ", "five ", "six ",
"seven ", "eight ", "nine ", "ten ",
"eleven ", "twelve ", "thirteen ",
"fourteen ", "fifteen ", "sixteen ",
"seventeen ", "eighteen ", "nineteen " ];
// Variable to store the word form of
// tens digit
var ten
= ["", "", "twenty ",
"thirty ", "forty ",
"fifty ", "sixty ",
"seventy ", "eighty ",
"ninety " ];
// Function to convert a two digit number
// to the word by using the above defined arrays
function numToWords(n, s)
{
var str = "";
// If n is more than 19, divide it
if (n > 19)
str += ten[Math.floor(n / 10)] + one[n % 10];
else
str += one[n];
// If n is non-zero
if (n)
str += s;
return str;
}
// Function to print a given number in words
function convertToWords(n)
{
// Stores the word representation
// of the given number n
var out;
// Handles digits at ten millions
// and hundred millions places
out += numToWords(Math.floor(n / 10000000),
"crore ");
// Handles digits at hundred thousands
// and one millions places
out += numToWords((Math.floor(n / 100000) % 100),
"lakh ");
// Handles digits at thousands and
// tens thousands places
out += numToWords((Math.floor(n / 1000) % 100),
"thousand ");
// Handles digit at hundreds places
out += numToWords((Math.floor(n / 100) % 10),
"hundred ");
if (n > 100 && n % 100)
out += "and ";
// Call the above function to convert
// the number into words
out += numToWords((n % 100), "");
return out;
}
// Function to sort the array according to
// the albhabetical order
function sortArr(arr, n)
{
// Vector to store the number in words
// with respective elements
var vp = new Array(n);
// Inserting number in words
// with respective elements in vector pair
for (var i = 0; i < n; i++) {
vp[i] = [convertToWords(arr[i]), arr[i]];
}
// Sort the vector, this will sort the pair
// according to the alphabetical order.
vp.sort();
// Print the sorted vector content
for (var i = 0; i < n; i++)
document.write(vp[i][1]+" ");
}
// Driver Code
var arr = [ 12, 10, 102, 31, 15 ];
var n = arr.length;
sortArr(arr, n);
</script>
Producción:
15 102 10 31 12
Complejidad de tiempo: O(N * log(N)) , donde N es el tamaño de la array
Espacio Auxiliar: O(N)