escriba una matriz de cadenas consecutivas sin clasificar clasificada en un archivo de manera eficiente: c, matrices, algoritmo, rendimiento, clasificación

Tengo una serie de cadenas que contienen números consecutivos no ordenados (rango de 0 a n), por ejemplo. [7a, 1b, 2c, 0d, 6e, 5f, 3g, 4h], y quiero escribir los números en orden en un archivo.

Después de ejemplo:

0d
1b
2c
3g
4h
5f
6e
7a

La cadena no son todas de la misma longitud.

Estaba tratando de encontrar una manera de hacerlo rápido ysin tomar demasiado espacio. Encontré una forma de hacerlo en O (n) complejidad de espacio y rendimiento O (n): creo una matriz con n celdas e inserto cada cadena en su número de celda.

for (i = 0; i < n; i++)
sortedArray[originalArray[i]] = originalArray[i]

... algo así (creando una nueva matriz en el tamaño de la original y rellénela en una ejecución), y luego con otra para escribir en bucle el contenido de la matriz ordenada en el archivo.

Pero estoy buscando una mejor manera de hacerlo.

Respuestas

Suponiendo que los principales números en sulas cadenas son, de hecho, consecutivas y no repetitivas, no logrará una mejor complejidad de tiempo que con el enfoque que describe en la pregunta, o algo parecido. Requiere espacio de trabajo proporcional al número de cadenas.

En comparación,

• una clasificación de combinación estándar también requiere un espacio de trabajo proporcional al número de cadenas (pero puede salirse con la mitad del enfoque de la pregunta, si tiene cuidado), y O(n log n) complejidad del tiempo. Alternativamente,
• clasificación rápida clasifica en el lugar y tiene O(n log n) complejidad de tiempo en promedio; Si lo implementas con cuidado entonces solo requiere O(log n) espacio de trabajo en el peor de los casos: una cantidad constante por cuadro de pila en la versión recursiva, o una pila que contenga tantos elementos en una no recursiva.
• una clasificación de fusión en el lugar requiere O(log n) espacio de trabajo (y no requiere tanto cuidado para lograrlo como lo hace la clasificación rápida), y tiene O(n^2) La complejidad del tiempo en promedio. Tiende a vencer a la mayoría de los demás. O(n^2) Se acerca bastante bien, la mayor parte del tiempo.
• ordenación por inserción clasifica en el lugar y requiere O(1) espacio de trabajo, pero tiene O(n^2) complejidad del tiempo. Es bien comprendido, fácil de implementar y muy rápido en la práctica para tamaños de entrada pequeños.

Hay muchas otras alternativas, pero creo queesos son razonablemente representativos de sus opciones. El que mejor se adapte a sus necesidades depende de los límites del tamaño de su problema y de cómo pese el espacio frente a la velocidad. Si el tamaño de su problema puede ser muy grande y no puede pagar O(n) espacio encima de la cabeza, a continuación, dar ordenamiento rápido cuidadoconsideración. Si es seguro que el tamaño del problema sea pequeño, pero la conservación del espacio es de importancia crítica, entonces considere la ordenación por inserción. Si la alta velocidad es importante y puede pagar la sobrecarga de espacio, entonces su enfoque original es muy atractivo.