¿Hay algún algoritmo de clasificación que sea sustancialmente más rápido que QuickSort?

En 1985 inventé y publiqué un algoritmo de clasificación único que denominé UnShuffle. UnShuffle es O (kN) donde k es un entero típicamente pequeño que representa el nivel de entropía en los datos. Unshuffle mueve solo los punteros sin hacer intercambios de datos costosos y requiere como máximo 5N palabras de memoria adicional (2N palabras al ordenar las fuentes de datos de la lista vinculada). Al extender su fusión de la capacidad de sumideros ordenados, puede clasificar eficientemente conjuntos de datos que no caben en la memoria. Utilicé UnShuffle para escribir una utilidad de clasificación de archivos que maneja muy bien los archivos de datos muy grandes.

Para datos de baja entropía, datos que están casi ordenados, UnShuffle funciona muy bien y, para muchos conjuntos de datos del mundo real, superará a QuickSort. El rendimiento en conjuntos de datos ya ordenados es O (N). UnShuffle es un tipo de distribución / fusión. Es único en el sentido de que la forma en que los elementos se distribuyen a las sublistas tiende a exponer el orden inherente en el conjunto de datos, como desarmar una baraja de cartas. De ahí el nombre.

Aquí hay un enlace a un artículo aún no publicado que he escrito que describe el algoritmo. Estoy esperando el momento de repetir las pruebas de rendimiento que hice en 1985 para agregar al artículo antes de publicar:

http://www.askdbmgt.com/uploads/ …

Otra cosa única de UnShuffle es que se presta para clasificar fuentes de datos inusuales, como listas vinculadas y datos de transmisión. La fase de distribución de la clasificación se puede realizar en paralelo o procesar múltiples flujos de entrada. La fase de fusión utiliza un algoritmo de fusión que tampoco he encontrado descrito en otra parte. Disfrutar.

O (n log n) se trata del límite inferior para cualquier algoritmo de clasificación basado en comparación, incluido el ordenamiento rápido. Para un pequeño conjunto de datos (digamos n <20), algunos de los algoritmos de ordenación lineal, como la ordenación por inserción, en realidad pueden ejecutarse más rápido y algunos códigos de ordenación cambian a una ordenación por inserción una vez que una submatriz se vuelve lo suficientemente pequeña.

Hay algoritmos de clasificación que no usan comparaciones y, como resultado, pueden ejecutarse en un tiempo cercano al lineal. Estos incluyen orden de conteo, clasificación de cubeta y clasificación de radix.

Mergesort supera la clasificación rápida para algunos conjuntos de datos / estructuras de datos.

Si se debe acceder a los datos que se van a ordenar en secuencia, es decir, no tiene acceso aleatorio al conjunto de datos, como en una lista vinculada o una secuencia de puntos de datos entrantes o un escenario de recopilación de datos en tiempo real, o algo así. como eso.

Las unidades de cinta son el ejemplo canónico de esto, especialmente en los viejos tiempos cuando la memoria era 1000 veces más costosa y 1,000,000 más voluminosa y lenta que hoy, y los discos duros también lo eran.

Merge Sort puede superar sustancialmente el ordenamiento rápido cuando no es posible almacenar todo el conjunto en la RAM al mismo tiempo, o cuando no está permitido intercambiar datos dentro del conjunto.

El peor caso de Mergesort es O (N logN), que está cerca del mejor caso de quicksort.
El caso promedio de Mergesort es aproximadamente un 40% mejor que el caso promedio de quicksort.
El mejor caso de Mergesort es casi el doble de bueno que el peor.

Pero de nuevo, mergesort no se ordena en su lugar como lo hace quicksort. Puede ser eficiente en casos de listas enlazadas, pero requiere más memoria y es extremadamente recursivo: incluso una lista completamente ordenada podría llevar a cabo las iteraciones de NlogN antes de terminar sin cambiar nada.

Para la ordenación secuencial general en memoria sin condiciones previas, QuickSort sigue siendo la solución más rápida que existe. IntroSort es básicamente QuickSort con respaldo inteligente a HeapSort cuando la partición va hacia el sur: obtiene el mejor rendimiento de QuickSort y HeapSort (aunque posiblemente el comportamiento de HeapSort rara vez sea necesario), y es lo que recomendaría en el caso general (es lo que es el estándar de C ++ std::sort hace).

Otros tipos superan a QuickSort si:

• la entrada tiene un tipo limitado (por ejemplo, RadixSort)
• la entrada tiene un desorden limitado (por ejemplo, TimSort)
• muchas CPU están disponibles (por ejemplo, Batcher impar-par MergeSort para GPU)

La ordenación rápida tiene un mejor caso y un caso promedio en O (n × lg (n)), que es casi tan bueno como puede esperar obtener una ordenación. Sin embargo, existe la posibilidad de O (n ^ 2) en el peor de los casos. En la implementación más ingenua, este peor caso es para datos ordenados. La segunda opción habitual es el peor de los casos para los datos ordenados. Incluso para las mejores opciones de pivote, todavía existe la posibilidad de golpear cerca del peor de los casos.

La ordenación del montón siempre es O (n × lg (n)), pero no conserva el orden de las claves idénticas. Es más difícil de entender que la clasificación rápida, pero se garantiza que no será peor y, a menudo, es mejor.

La clasificación de burbujas es típicamente O (n ^ 2), pero el mejor caso es O (n) para una lista ya ordenada. Cuanto más cerca se ordene la lista, más cerca de O (n) estará el algoritmo.

FlashSort () para la ordenación numérica es más rápido que QuickSort para n lo suficientemente grande. Alrededor de 10000 es donde FlashSort comienza a superar a QuickSort. MergeSort usando Efficient Merge () en realidad supera a QuickSort a 10000. Para N> 100000 muy grande, QuickSort logra un rendimiento de 500000 / GHz. Hay tipos de radix que son más rápidos que ambos.

Simplemente agregue a otras excelentes respuestas: Conteo ordenado: Wikipedia es más rápido que el ordenamiento rápido si los valores de los objetos que se ordenarán tienen un rango limitado, es decir, si los objetos son enteros pequeños.

El algoritmo de conteo ordena elementos en complejidad O (N) pero ocupa espacio O (M) M = valor máximo de cualquier elemento.