¿Hay algún algoritmo de ordenación que funcione en el orden de n?

Sí, pero es un poco complicado.

Para realizar la ordenación en [math] \ mathcal {O} (n) [/ math], debe conocer el rango de valores posibles que pueden tomar los elementos de su lista. Si tiene una lista de n enteros [matemática] 0 \ leq x

aux [5]: = aux [5] + 1

Después de este paso, su vector auxiliar registrará cuántas veces cada entero [matemático] 0 \ leq x

para (int i = 1; i aux [i] = aux [i] + aux [i-1];

Y lo que tiene ahora es cuántos elementos más pequeños que cada número entero [matemática] 0 \ leq x

La mayoría de los algoritmos de ordenación lineal funcionan de esta manera, con pequeñas variaciones aquí y allá. Pero, curiosamente, hay algoritmos de clasificación de tiempo lineal que no requieren que asigne un espacio de memoria predefinido. De hecho, en cierto sentido, puede hacer una ordenación lineal sin siquiera saber un límite superior a los valores de los elementos de su lista. La ordenación del sueño (un algoritmo de ordenación esotérico desarrollado en el tablero de imágenes de 4 canales) hace exactamente eso: lo que hace es lanzar un hilo para cada elemento de la lista y programarlo para que dure durante una cantidad de milisegundos proporcional al valor del elemento correspondiente, e imprimirlo después . El comportamiento resultante es que todos los elementos de la lista se imprimen en orden, y lo bueno es que ignorando los detalles sobre el sistema operativo y su programador, puede hacer que la proporcionalidad constante del paso de “suspensión” sea arbitrariamente pequeña, acelerando así su algoritmo en cualquier cantidad te gusta.

Pero (obviamente) hay una trampa: lo que hace la ordenación del sueño es explorar la misma estructura algorítmica del algoritmo mencionado anteriormente, pero intercambiando espacio por tiempo para realizar cálculos. Entonces, aunque no necesite saber M, el tiempo transcurrido dependerá de él de la misma manera que el vector auxiliar de antes (piense en la ordenación del sueño como el mantenimiento de un vector “temporal”).

Si lo piensa, se dará cuenta de que todos los demás algoritmos de clasificación de tiempo lineal (como la clasificación de espagueti) también incorporan los mismos trucos básicos descritos aquí.

¡Sé que hay un algoritmo de clasificación que puede hacer aún mejor! ¡Clasificación en tiempo constante (O (k))!

Lo haces así:

1. Para N números, genere N hilos de procesamiento. Asigne cada número M a cada hilo.
2. Cada hilo tiene una tarea simple: dormir M milisegundos. Luego, imprime M.
3. Dado un planificador justo y sin contención de recursos, ahora debería ver su salida después de un máximo de (M) milisegundos, ¡lo que sin duda es un tiempo constante!

Nadie ha mencionado todavía el tipo de espagueti, que es O (N), aunque muy poco práctico.

Aquí está el algoritmo:

1. Comience con un gran manojo de espagueti seco.
2. Para cada número que desee ordenar, corte una barra de espagueti para que su longitud sea proporcional al número. Etiqueta los espaguetis con el número.
3. Tome todo el grupo y colóquelos sin apretar sobre una superficie plana (una mesa) para que la parte inferior de cada pieza esté al mismo nivel.
4. La barra más alta será el número más alto. Registre el número, saque la barra y continúe con la siguiente barra más alta. Repita hasta que esté listo.
5. [Opcional] Hervir los espaguetis y servir con salsa.

EDITAR: Aquí hay un algoritmo de clasificación O (N) basado en la clasificación Spaghetti que funciona en una computadora digital. La única advertencia es que necesitamos procesadores N:

1. Inicialice la matriz U con los números de entrada sin clasificar. [A tiempo]
2. Asigne cada procesador a una de las entradas en la matriz UIe, el procesador 0 se asigna a U [0], el procesador 1 se asigna a U [1], etc.
3. Cada procesador recorre U y calcula el índice del número más alto en U que es más bajo que el número asignado al procesador. Por ejemplo, el procesador i busca el índice del número más alto en U que es menor que U [i]. [Esto es O (N), ya que cada procesador solo tiene que hacer un bucle una vez.]
4. Cada procesador i almacena su resultado en N [i]; si el procesador no pudo encontrar un número inferior al suyo, entonces almacene nulo en N [i]. [Tiempo constante]
5. Comentario: La matriz N es esencialmente un conjunto de enlaces al siguiente número más alto para cada entrada en U. N [i] es el índice en U para el siguiente número ordenado después de U [i].
6. Hacemos un bucle sobre la matriz U y encontramos el número más alto. Establezca i como el índice en U del número más alto. Por lo tanto, U [i] es el número más alto en U. [Este es el tiempo O (N)]
7. Salida U [i]
8. Establezca i en N [i]. Si soy nulo, entonces hemos terminado. De lo contrario, vaya al paso 6. [Este ciclo final es el tiempo O (N).]

• Si su algoritmo de clasificación se basa en una función de comparación por pares, entonces la respuesta es no: hay un límite inferior estricto [matemático] \ Omega (n \ log n) [/ matemático], generalmente llamado “límite inferior teórico de información” ( La idea es que cada comparación puede producir como máximo un bit de información sobre el orden actual de los datos, y necesita al menos esa cantidad de bits para poder distinguir todos los posibles ordenamientos de entrada).
• El límite inferior se aplica al peor de los casos; Sin embargo, existen algoritmos de clasificación que pueden operar más rápidamente en algunas secuencias de entrada. Por ejemplo, la ordenación por inserción puede funcionar en tiempo [matemático] O (n) [/ matemático] si los datos de entrada ya están casi ordenados.
• Como dice Bob Dalgleish, hay algoritmos como la ordenación por radix (o la ordenación de cubetas) que no dependen de una función de comparación binaria; sin embargo, dichos algoritmos dependen de otros parámetros, como la longitud de las teclas (cuántos dígitos tienen los números). Entonces llamar a tal algoritmo [matemática] O (n) [/ matemática] es algo engañoso; su rendimiento se expresa mejor como [math] O (nk) [/ math], donde [math] n [/ math] es el número de elementos a clasificar, y [math] k [/ math] es el tamaño del artículos (por ejemplo, número de dígitos). No es exagerado suponer que [math] k [/ math] es típicamente proporcional a … al menos [math] \ log (n) [/ math].

contando sort- O (n + k) n es el número de elementos en la matriz de entrada yk es el rango de entrada

radix sort- O (d (n + k)) d es el número de dígitos del número más alto. n es el número de elementos. k es el rango de dígitos (0–9).

nota: mientras se ordena [1,998,76] 1 y 76 se debe usar como 001,076 al comparar para dar el resultado correcto.

La respuesta simple es NO en general. O (n log n) es un óptimo general. Para conjuntos de muestras específicos, O (n) puede aplicarse pero exigir memoria; por ejemplo, un conjunto único de números con un rango limitado, un conjunto único de ‘palabras’ de longitud limitada. Una búsqueda binaria simple se reduce a O (n log n)

Sí. Hay un orden llamado “” orden de radix “que puede ordenar sus entradas en un número constante de pasadas.

Un ejemplo simple es cuando la clave de clasificación es un número de 5 dígitos. En la primera pasada, coloque cada elemento en uno de los diez contenedores según el dígito decimal menos significativo. Luego, tome el contenido de cada bin en orden y vuelva a hacerlo con el siguiente dígito menos significativo. Repita tres veces más y su entrada se ordena en operaciones O (n).

Sí, tipo Radix.

Radix Sort – GeeksforGeeks

Espero que ayude.