Algunas veces, los entrevistadores preguntan cómo ordenar millones/mil millones de enteros de 32 bits (por ejemplo, here y here). Supongo que esperan que los candidatos comparen el tipo O (N Log (N)) con ordenación de radix. Para millones de enteros O (N Log (N)) el género es probablemente mejor, pero para mil millones probablemente sea el mismo. Tiene sentido ?Cómo ordenar (millones/millones/...) enteros?
Si recibe una pregunta como esta, no están buscando la respuesta. Lo que están tratando de hacer es ver cómo piensas a través de un problema. ¿Entra directamente o hace preguntas sobre los requisitos del proyecto?
Una pregunta que debe hacer es: "¿Qué tan óptima de solución requiere el problema?" Tal vez un tipo de registros de burbuja almacenados en un archivo es lo suficientemente bueno, pero tienes que preguntar. Haga preguntas sobre qué pasa si la entrada cambia a números de 64 bits, ¿debería actualizarse fácilmente el proceso de clasificación? Pregunte cuánto tiempo tiene el programador para desarrollar el programa.
Ese tipo de preguntas me muestran que el candidato es lo suficientemente inteligente como para ver que hay más en el problema que simplemente ordenar los números.
Espero que estén buscando ampliar la diferencia entre internal sorting y external sorting. Al parecer, la gente no lee hoy en día Knuth
Depende de la estructura de datos que están almacenados. Radix late tipo N-log-N tipo de problema bastante pequeño tamaño de si la entrada está en una lista enlazada, ya que doesn No es necesario asignar ninguna memoria reutilizable, y si puede permitirse asignar un búfer cero al tamaño de la entrada al comienzo del ordenamiento, lo mismo se aplica a las matrices. En realidad, solo la opción incorrecta (para llaves enteras) tiene un espacio de almacenamiento adicional muy limitado y su entrada está en una matriz.
Esperaría que el punto de cruce estuviera muy por debajo de un millón, independientemente.
Utilice el mapa de bits. Necesitas unos 500 Mb para representar un rango entero entero de 32 bits. Para cada número entero en la matriz dada, simplemente configure el bit correspondiente. Luego, simplemente escanee su mapa de bits de izquierda a derecha y obtenga su matriz de enteros ordenada.
Como dijo aaaa bbbb, depende de la situación. Haría preguntas sobre los requisitos del proyecto. Por ejemplo, si desean contar las edades de los empleados, probablemente use Counting sort, puedo ordenar los datos en la memoria. Pero cuando los datos son totalmente aleatorios, probablemente utilices el external sorting. Por ejemplo, puede dividir los datos del archivo fuente en los diferentes archivos, cada archivo tiene un rango único (File1 es de 0-1m, File2 es de 1m + 1 - 2m, ect), luego ordena cada archivo, y finalmente combinarlos en un nuevo archivo.
+ lotes. Seguramente no quieren saber que usted conoce algunos algoritmos de clasificación –