¿Hay un algoritmo de ordenamiento de enteros O (n)?

Question

La última semana Tropecé con this paper donde los autores mencionan en la segunda página:

Tenga en cuenta que esto produce un tiempo lineal candidato a pesos de las aristas enteros.

El mismo en la tercera página:

Esto produce un tiempo de funcionamiento lineal para pesos de las aristas enteros y O (m log n) para la clasificación basada en la comparación.

Y en la página 8 de:

En particular, el uso de la clasificación rápida entero probablemente se aceleraría considerablemente GPA.

¿Quiere decir esto que hay un O (n) algoritmo de ordenación en circunstancias especiales para valores enteros? ¿O es esto una especialidad de la teoría de grafos?

PS:
Podría ser que la referencia [3] puede ser útil porque en la primera página que dicen: se han logrado

Otras mejoras de [..] clases de gráficos, tales como número entero pesas de borde [3], [...]

pero no tuve acceso a ninguna de las revistas científicas.

Answer 1

Sí, radix clasificar y contar tipo son O(N). NO son géneros basados ​​en comparación, que se ha demostrado que tienen Ω(N log N) límite inferior.

Para ser precisos, el orden de radix es O(kN), donde k es el número de dígitos en los valores que se ordenarán. Contando especie es O(N + k), donde k es el rango de los números para ser ordenados.

hay aplicaciones específicas donde k es lo suficientemente pequeño que tanto radix clasificar y contar tipo exhibir un rendimiento en tiempo lineal en la práctica.

Answer 2

tipo comparación debe ser al menos Ω (n log n) en promedio.

Sin embargo, counting sort y radix sort escalan linealmente con tamaño de entrada – porque no son tipos de comparación, explotan la estructura fija de las entradas.

Answer 3

Conteo para ordenar: http://en.wikipedia.org/wiki/Counting_sort si sus números enteros son bastante pequeñas. Radix sort si tiene números más grandes (esto es básicamente una generalización de contar tipo, o una optimización para los números más grandes si se quiere): http://en.wikipedia.org/wiki/Radix_sort

También hay cucharón para ordenar: http://en.wikipedia.org/wiki/Bucket_sort

Answer 4

Aunque no es muy práctico (debido principalmente a la gran sobrecarga de la memoria), pensé que me gustaría mencionar Abacus (Bead) Sort como otro interesante algoritmo de ordenación del tiempo lineal.

Answer 5

Estos algoritmos de clasificación basados ​​en hardware:

A Comparison-Free Sorting Algorithm
Sorting Binary Numbers in Hardware - A Novel Algorithm and its Implementation

Laser Domino Sorting Algorithm - un experimento mental por mí basada en contar Ordenar con la intención de lograr O(n) complejidad del tiempo sobre Contar Ordenar es O(n + k).

Answer 6

Añadiendo un poco más de detalle: prácticamente el mejor algoritmo de ordenación hasta la fecha no es O (n), sino 0 (n \ sqrt {\ log \ log n}).

Puede consultar más detalles sobre este algo en el periódico: http://dl.acm.org/citation.cfm?id=652131