Clasifique N números en orden de dígitos

Question

Dado un número de N rango E.g. [1 a 100], ordene los números en orden de dígitos (es decir) Para los números del 1 al 100, la salida ordenada será 1 10 100 11 12 13. . . 19 2 20 21 ..... 99

Esto es como Radix Sort, pero solo que los dígitos se ordenan en orden inverso a lo que se haría en una clasificación de radix normal.

Traté de almacenar todos los dígitos en cada número como una lista vinculada para un funcionamiento más rápido, pero da como resultado una gran Complejidad del Espacio.

Necesito un algoritmo de trabajo para la pregunta.

De todas las respuestas, "Convertir a cadenas" es una opción, pero ¿no hay otra manera de hacerlo? También se puede dar un algoritmo para ordenar cadenas como se mencionó anteriormente.

Answer 1

Utilice cualquier algoritmo de clasificación que desee, pero compare los números como cadenas, no como números. Esto es básicamente clasificación lexiográfica de números regulares. Aquí hay un ejemplo de GNOME tipo en C:

#include <stdlib.h> 
#include <string.h> 

void sort(int* array, int length) { 
    int* iter = array; 
    char buf1[12], buf2[12]; 
    while(iter++ < array+length) { 
     if(iter == array || (strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0) { 
      iter++; 
     } else { 
      *iter ^= *(iter+1); 
      *(iter+1) ^= *iter; 
      *iter ^= *(iter+1); 
      iter--; 
     } 
    } 
} 

Por supuesto, esto requiere que el itoa función no estándar a estar presente en stdlib.h. Una alternativa más estándar sería usar sprintf, pero eso hace que el código esté un poco más desordenado. Probablemente sea mejor que conviertas todo el conjunto en cadenas primero, luego clasifique y luego conviértalo de nuevo.

Editar: Como referencia, el bit relevante aquí es strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0, que sustituye *iter >= *(iter-1).

Answer 2

Creo que si convierte números a cadena, puede usar la comparación de cadenas para ordenarlos. puede usar cualquier alghorighm de clasificación para ello.

"1" < "10" < "100" < "11" ...

Answer 3

tengo una solución, pero no es exactamente un algoritmo .. Todo lo que necesita hacer es convierte todos los números a cadenas & clasificarlos como cadenas ...

Answer 4

Editar: Extrañaba que fuera un rango contiguo. Siendo ese el caso, todas las respuestas que se refieren a ordenar una matriz son incorrectas (incluida la idea que se plantea en la pregunta de que es como un tipo de raíz), y la respuesta de True Soft es correcta.

como Radix Ordenar pero igual que los dígitos se clasifican en orden inverso

Bueno manchado :-) Si realmente lo hace de esa manera, curiosamente, se llama una raíz MSD tipo.

http://en.wikipedia.org/wiki/Radix_sort#Most_significant_digit_radix_sorts

Puede implementar una manera muy simple, o con un montón de alta tecnología y fanfarria. En la mayoría de los lenguajes de programación, su ejemplo particular enfrenta una ligera dificultad. La extracción de dígitos decimales del formato de almacenamiento natural de un entero, no es una operación especialmente rápida. Puede ignorar esto y ver cuánto tiempo termina tomando (recomendado), o puede agregar aún más fanfarria convirtiendo todos los números a cadenas de decimales antes de ordenar.

Por supuesto, no tiene que implementarlo como una ordenación de radix: podría utilizar un algoritmo de ordenación de comparación con un comparador adecuado. Por ejemplo, en C, lo que sigue es adecuado para su uso con qsort (a menos He ensuciado para arriba):

int lex_compare(void *a, void *b) { 
    char a_str[12]; // assuming 32bit int 
    char b_str[12]; 
    sprintf(a_str, "%d", *(int*)a); 
    sprintf(b_str, "%d", *(int*)b); 
    return strcmp(a_str,b_str); 
} 

No

muy eficiente, ya que hace mucho trabajo repetido, pero sencillo.

Answer 5

Aquí es cómo usted puede hacerlo con una función recursiva (el código está en Java):

void doOperation(List<Integer> list, int prefix, int minimum, int maximum) { 
    for (int i = 0; i <= 9; i++) { 
     int newNumber = prefix * 10 + i; 
     if (newNumber >= minimum && newNumber <= maximum) { 
      list.add(newNumber); 
     } 
     if (newNumber > 0 && newNumber <= maximum) { 
      doOperation(list, newNumber, minimum, maximum); 
     } 
    } 
} 

Se llaman así:

List<Integer> numberList = new ArrayList<Integer>(); 
int min=1, max =100; 
doOperation(numberList, 0, min, max); 
System.out.println(numberList.toString()); 

---

EDIT:

He traducido mi código en C++ here:

#include <stdio.h> 

void doOperation(int list[], int &index, int prefix, int minimum, int maximum) { 
    for (int i = 0; i <= 9; i++) { 
     int newNumber = prefix * 10 + i; 
     if (newNumber >= minimum && newNumber <= maximum) { 
      list[index++] = newNumber; 
     } 
     if (newNumber > 0 && newNumber <= maximum) { 
      doOperation(list, index, newNumber, minimum, maximum); 
     } 
    } 
} 

int main(void) { 
     int min=1, max =100; 
     int* numberList = new int[max-min+1]; 
     int index = 0; 
     doOperation(numberList, index, 0, min, max); 
     printf("["); 
     for(int i=0; i<max-min+1; i++) { 
       printf("%d ", numberList[i]); 
     } 
     printf("]"); 
     return 0; 
} 

Básicamente, la idea es: para cada dígito (0-9), lo agrego a la matriz si está entre minimum y maximum. Luego, invoco la misma función con este dígito como prefijo. Hace lo mismo: para cada dígito, lo agrega al prefijo (prefix * 10 + i) y si está entre los límites, lo agrega a la matriz. Se detiene cuando newNumber es mayor que el máximo.

Answer 6

Si no desea convertirlos en cadenas, pero tiene espacio suficiente para almacenar una copia adicional de la lista, almacenaría la mayor potencia de diez menos que el elemento en la copia. Esto es probablemente lo más fácil de hacer con un bucle. Ahora llame a su matriz original x y las potencias de diez y.

int findPower(int x) { 
    int y = 1; 
    while (y * 10 < x) { 
     y = y * 10; 
    } 
    return y; 
} 

También se puede calcular directamente

y = exp10(floor(log10(x))); 

pero sospecho que la iteración puede ser más rápido que las conversiones desde y hacia el punto flotante.

el fin de comparar los i º y j th elementos

bool compare(int i, int j) { 
    if (y[i] < y[j]) { 
    int ti = x[i] * (y[j]/y[i]); 
    if (ti == x[j]) { 
     return (y[i] < y[j]); // the compiler will optimize this 
    } else { 
     return (ti < x[j]); 
    } 
    } else if (y[i] > y[j]) { 
    int tj = x[j] * (y[i]/y[j]); 
    if (x[i] == tj) { 
     return (y[i] < y[j]); // the compiler will optimize this 
    } else { 
     return (x[i] < tj); 
    } 
    } else { 
    return (x[i] < x[j]; 
    } 
} 

lo que se hace aquí es que estamos multiplicando el número más pequeño por la potencia adecuada de diez a hacer que los dos números tienen el mismo número de dígitos, luego compararlos. si los dos números modificados son iguales, entonces compare las longitudes de los dígitos.

Si no tiene espacio para almacenar las matrices y, puede calcularlas en cada comparación.

En general, es mejor que utilice las rutinas de conversión de dígitos preoptimized.

Answer 7

Optimice la forma en que está almacenando los números: use un tipo binary-coded decimal (BCD) que le da acceso simple a un dígito específico. Luego puede usar su algoritmo actual, que Steve Jessop identificó correctamente como most significant digit radix sort.

Me trataron de almacenar todos los dígitos en cada número como una lista enlazada de un funcionamiento más rápido, pero el resultado es una gran complejidad espacial .

Almacenamiento de cada dígito en un espacio lista de residuos ligados de dos maneras diferentes:

1. Un dígito (0-9) sólo se requiere 4 bits de memoria para almacenar, pero es probable que esté utilizando en cualquier lugar de 8 a 64 bits. Un tipo char o short toma 8 bits, y un int puede tomar hasta 64 bits. Eso es usar de 2X a 16X más memoria que la solución óptima.
2. Las listas vinculadas añaden una sobrecarga adicional de memoria innecesaria. Para cada dígito, necesita 32 a 64 bits adicionales para almacenar la dirección de memoria del siguiente enlace. Nuevamente, esto aumenta la memoria requerida por dígito entre 8X y 16X.

A más tiendas solución de memoria eficiente BCD dígitos de forma contigua en la memoria:

1. BCD sólo utiliza 4 bits por dígito.
2. Almacene los dígitos en un bloque de memoria contiguo, como una matriz. Esto elimina la necesidad de almacenar direcciones de memoria. No necesita la capacidad de las listas vinculadas para insertar/eliminar fácilmente desde el centro. Si necesita la capacidad de aumentar los números a una longitud desconocida, existen otros tipos de datos abstractos que permiten eso con mucha menos sobrecarga. Por ejemplo, un vector.

Una opción, si otras operaciones como la adición/multiplicación no son importantes, es asignar suficiente memoria para almacenar cada dígito BCD más un terminador BCD. El terminador BCD puede ser cualquier combinación de 4 bits que no se usa para representar un dígito BCD (como el binario 1111). Sin embargo, almacenar de esta manera hará que otras operaciones como la suma y la multiplicación sean más complicadas.

Tenga en cuenta que esto es muy similar a la idea de convertir a cadenas y ordenar lexicográficamente esas cadenas. Los enteros se almacenan internamente como binarios (base 2) en la computadora. Almacenar en BCD es más como base 10 (base 16, de hecho, pero se ignoran 6 combinaciones), y las cadenas son como base 256. Las cadenas usarán aproximadamente el doble de memoria, pero ya hay funciones eficientes escritas para ordenar cadenas. Los BCD probablemente requieran el desarrollo de un tipo de BCD personalizado para sus necesidades.