Notas: He pensado en el género Radix, en el tipo de cubo, en el tipo de conteo.¿Cuál es la forma más rápida de ordenar 1 millón de enteros cuando los enteros son del rango [1,100]?
¿Hay alguna forma de lograr una O grande (n)?
Usted puede utilizar counting sort.
Contando tipo (a veces conocido como Ultra especie o matemáticas especie) es un algoritmo de clasificación que (como cubo especie) realiza ventaja de conocer el rango de los números en la matriz para ser ordenada (array A).
El ordenamiento por recuento es estable y tiene un tiempo de ejecución de Θ (n + k), donde nyk son las longitudes de las matrices A (la matriz de entrada) y C (la matriz de recuento), respectivamente. Para que este algoritmo sea eficiente, k no debe ser mucho más grande que n.
En este caso k es 100 y n es 1000000.
+1 Cegadoramente obvio, pero nunca lo había visto antes. Gracias. –
Quiero votar, pero actualmente está en 42 y realmente quiero que se quede allí. Este es el mayor dilema que he enfrentado hoy. – EmmaGamma
Una clasificación de conteo sería la elección obvia en estas circunstancias. Sí, correctamente implementado, debería tener una complejidad lineal.
Con contando tipo que presentamos lo mejor O (N) si el rango es fijo y pequeño (como 1..100 :))
cómo sobre simplemente contando la ocurrencia de cada número entero y luego imprimir de ellos todos. suena como O (n)
Sí, y eso es exactamente lo que cuenta. Esto muestra que la mayoría de los algoritmos no son difíciles; puedes inventarlos tú mismo. :-) – ShreevatsaR
contar es un poco más complejo que eso (ordena las claves, pero puede manejar datos asociados), pero sí, esa es la idea básica –
Supongo que quiere decir que quiere lograr un pequeño O (n); entonces el tipo de cubo sería el más rápido. De hecho, ya que conoce el rango de los enteros, entonces el uso de clasificación de cubo simplemente se convierte en un problema de contar las ocurrencias de los números que se pueden hacer en O (n), es decir, tiempo lineal.
El llamado tipo de conteo es simplemente un caso especial de ordenación del cucharón.
No, el ordenamiento de recuento no es un caso especial de ordenación de depósitos. En la clasificación por cubo, en realidad almacena los elementos en los cubos. En la clasificación de conteo, solo almacena el conteo. –
Para todos los interesados, que rápidamente se lanzaron juntos este pedazo de Ruby, antes de leer las respuestas:
module Enumerable
def counting_sort(k)
reduce(Array.new(k+1, 0)) {|counting, n| counting.tap { counting[n] += 1 }}.
map.with_index {|count, n| [n] * count }.flatten
end
end
ary = Array.new(1_000_000){ rand(100) + 1 }
ary.counting_sort(100) # I'll spare you the output :-)
yo ni siquiera sabía que tenía un nombre. Debería transmitir la idea incluso a alguien que nunca antes haya visto a Ruby. (Lo único que necesita saber es que el combinador K se escribe tap en Ruby.)
Y realmente es bastante rápido, aunque desafortunadamente no he podido vencer al O (n & thinsp; log & thinsp; n) sort, que está escrito en C en MRI y YARV y Java en JRuby.
Aquí es una especie de recuento en Scala:
val res = Array.fill (100)(0)
val r = util.Random
// generate data to sort
val nums = for (i <- 1 to 1000*1000) yield r.nextInt (100)
for (i <- nums) res(i) += 1
println (res.mkString (" "))
Usando Radix Sort (en Ruby):
def sort(array)
sorted_array = Array.new(100,[])
array.each do |t|
sorted_array[t-1] = sorted_array[t-1] + [t]
end
sorted_array.flatten!
end
No es posible, en general, para ordenar una lista en O (n), incluso si cada número en la lista es menor que 100. – SLaks
@SLaks: El mínimo de O (N lgN) se aplica solo a ordenaciones basadas en comparaciones. –
en este caso puede, simplemente contando elementos entre 1 y 100. –