¿Existe algún algoritmo de clasificación que esté en su lugar, estable y que tenga un tiempo de ejecución lineal?

Como dijo Xiao Feng, este tiempo de ejecución asintótico no es posible en el caso de que los elementos solo se puedan comparar y los valores clave reales no se puedan usar.

Sin embargo, es posible, si es difícil, implementar una ordenación estable en el lugar que se ejecute en el tiempo [math] O (nk) [/ math] donde las claves tienen el tamaño k . Una clase de algoritmos que logra este límite de tiempo es la clase de clases de radix .

Hay dos enfoques clásicos para la clasificación de radix: los tipos de radix MSD y LSD. La ordenación de radix MSD clasifica los elementos en cubos en función de las palabras de orden más alto de sus claves, luego ordena recursivamente cada cubo hasta que los cubos sean lo suficientemente pequeños como para cambiar a un algoritmo que sea más eficiente, que generalmente es el orden de inserción en la escala más pequeña ( aunque los tipos híbridos también pueden usar la clasificación rápida, una vez que los cubos pueden caber completamente en la memoria caché). Se puede implementar de manera eficiente de manera estable o in situ, pero aún no he visto un algoritmo que logre ambas cosas.

La clasificación por radix LSD clasifica los elementos según las palabras de orden inferior de sus claves, luego en la siguiente palabra de orden superior y así sucesivamente. Esto suele ser bastante lento, ya que el proceso no puede preservar ningún orden existente. En otras palabras, la ordenación de radix LSD nunca es adaptativa. Además, debe ser estable para poder clasificar correctamente, por lo que todas las implementaciones son inherentemente estables, pero no suelen estar en su lugar.

Sin embargo, es posible crear un tipo de radix LSD que logre el peor rendimiento de [math] O (nk) [/ math] en el peor de los casos mientras sea estable e in situ. Puedo asegurarle que es extremadamente difícil hacerlo y que el algoritmo resultante probablemente será más lento que casi todo lo que existe en casos del mundo real, así que considere que lo que sigue es solo de interés teórico.


La primera idea es que el “tamaño de dígitos” para la ordenación de radix LSD podría ser un solo bit. Podemos ordenar los elementos dividiendo primero de manera estable los elementos cuyo último bit de clave es 1 hasta el final. Luego, dividimos de manera estable las claves cuyo penúltimo bit es 1 hasta el final. Y así sucesivamente hasta que hayamos revisado cada parte de la clave. Llamemos a este proceso un “Shuffle chino” en memoria de Bro. John Hamman, dado que es probable que el método utilizado por Stephan Gruber para alcanzar el récord mundial de clasificación de naipes.

Ese método nos dará la misma estabilidad y el peor de los casos asintóticos en el peor de los casos que cualquier tipo de radix LSD antiguo, pero aún no produce el algoritmo requerido. Para lograr eso, debemos ser capaces de realizar el paso de partición en el lugar, lo cual, nuevamente, no es fácil . Pero, debido a que hemos reducido el problema a una partición 0-1, ahora podemos usar el algoritmo de Katajainen y Pasanen en Particionamiento de espacio mínimo estable en tiempo lineal (1992). Este algoritmo utiliza como subrutina otro algoritmo muy difícil de Munro, Raman y Salowe que no está disponible para estudiar en línea. Tendrás que buscarlo en la biblioteca de tu universidad. Sin embargo, en conjunto, requiere una sobrecarga de espacio constante y tiempo lineal para la partición, ya que requerimos construir el algoritmo que necesita.

Entonces ahí está tu algoritmo:

  1. Para cada bit b de 0 a k -1:
    1. Use el algoritmo de Katajainen y Pasanen para dividir los elementos en el bit de sus claves.

Si observa el documento vinculado anterior, verá que se proporciona otro algoritmo para tipos de listas estables en el lugar con solo k claves distintas en el tiempo [matemático] O (nk) [/ matemático] (dado como Teorema 2) . El algoritmo es solo:

  1. Repite k veces:
    1. Encuentre las claves más pequeñas en la “partición superior” (que inicialmente es la lista completa) con una búsqueda lineal.
    2. Use el algoritmo de Katajainen y Pasanen para dividir todos los elementos cuyas claves no sean iguales a s al final de la lista. Llame a la partición con estas teclas sin clasificar la nueva “partición superior”.

Recuerde que estos algoritmos solo logran sus garantías de rendimiento sublinealítico en casos especiales: que el rango de claves es pequeño o que el número de claves distintas es pequeño. En el caso general de claves que varían enormemente, estos algoritmos no funcionan mejor asintóticamente que los tipos in situ estables al tiempo linealitmicos como WikiSort y GrailSort. Y de nuevo, para todos los problemas de tamaño razonable, querrá evitar estos algoritmos de todos modos, ya que el estado del arte para esta clase de problemas aún está lejos de ser práctico.

Lo más cercano que puede llegar al tiempo de ejecución lineal podría ser una clasificación por radix, y eso solo funciona para un dígito o elemento de módulo a la vez.

Y eso no está en su lugar, pero es estable, en la mayoría de las implementaciones.

Una falla es que si lo haces en verdadero módulo, eso implica una operación de división lenta.

El ordenamiento de conteo casi cumpliría con estos requisitos para una pequeña cantidad de valores discretos (por ejemplo, un millón de entradas entre 1 y 10). No sería estable, pero no sería significativamente inestable: solo está contando cuántos 1, 2, etc. tiene y cuándo ha terminado de reemplazar todos los artículos en la tienda original.

Hay un teorema que dice que en el modelo de computación tradicional, un algoritmo de clasificación no puede tener un tiempo de ejecución mejor que [math] O (n \ log n) [/ math] (no tengo el nombre justo encima de mi cabeza).

Lo más cercano que puedo encontrar relacionado con su pregunta es Ordenar de forma estable, en el lugar, con O (n log n) Comparaciones y O (n) Movimientos

Otro algoritmo útil es el tipo de conteo que tampoco está en su lugar, pero es estable y muy fácil de entender e implementar. Pero podría no ser una buena idea para ordenar una gran variedad de números con este algoritmo, ya que utiliza mucha memoria.