¿Cuál es el algoritmo de ordenación más rápido para enteros 0-65535?

Question

Tengo que ordenar una serie de enteros, que pueden tener valores entre 30.000.000 y 350.000.000. Habrá entre 0 y 65.535 enteros, con un recuento promedio de 20.000. El uso de RAM es irrelevante y la velocidad solo es importante.

Más adelante también tendré que dividirlos en grupos, siempre con la división siempre que la brecha entre dos de estos valores sea> 65.535, que es para lo que necesito el algoritmo.

Si hace alguna diferencia, el algoritmo se usará en una secuencia de comandos de Perl.

Editar: Después de pensarlo y leer las respuestas me he dado cuenta de algo: en realidad no me importan los datos en sí. Como realmente solo quiero encontrar los valores de inicio y fin de grupos con espacios pequeños, la ordenación solo necesita crear divisiones y puede descartar los datos.

Edit2: Después de algunas pruebas y probar las respuestas proporcionadas, la manera más rápida que encontré fue esto:

my @sort = sort {$a <=> $b} @item_offsets; 
my @buckets; 
my $start = shift @sort; 
push @buckets, [$start,$start]; 
for my $item (@sort) { 
    if ($item < $buckets[$#buckets][1]+$gap) { 
     $buckets[$#buckets][1] = $item; 
    } 
    else { 
     push @buckets, [$item,$item]; 
    } 
} 
say $#buckets; 

Answer 1

que acababa de hacer una serie de cubos antes de ejecutar el algoritmo, una para cada grupo de 65536 valores consecutivos. Los depósitos contendrán un valor mínimo y máximo de sus contenidos, pero no almacenarán los contenidos ellos mismos. Después de ejecutar el algoritmo, haga una sola pasada sobre los cubos. Si hay dos cubos no vacíos consecutivos con min (bucket2) -max (bucket1) < 65536, combínelos. La combinación no ocurrirá hasta que el algoritmo termine de ejecutarse. Deseche los cubos vacíos. Este algoritmo es tiempo lineal.

Tome nota de Bucket Sort.

Answer 2

que haría uso de una especie radix, ya que hay que agrupar el resultado.

Answer 3

Sólo iba a decir tipo de raíz, http://en.wikipedia.org/wiki/Radix_sort, sin embargo, eso podría ser un poco más de lo que buscaba implementar, Introsort es generalmente la solución de clasificación aceptada para datos http://en.wikipedia.org/wiki/Introsort, es una variación de quicksort que cambia a heapsort cuando alcanza conjuntos más pequeños, ya que es más rápido en juegos más pequeños que en el grupo rápido.

Answer 4

Si utiliza el número como índice de una matriz, y luego incrementa el recuento de esa posición, los ha "agrupado" y lo ha hecho de una vez.

en pseudocódigo:

while(morenumbers) 
    sorted[[unsorted[number]]++ 
    number++ 

Si el rango es conocido de antemano, se puede reducir el índice de los valores (por ejemplo, el valor-30000 para ponerla en el rango de la derecha).

Answer 5

Es poco probable que usted será capaz de escribir un algoritmo de ordenación en Perl que se obtienen mejores resultados que incorporado sort función de Perl:

Usted puede experimentar con el pragma tipo para ver si un algoritmo particular es mejor:

use sort '_quicksort'; 
use sort '_mergesort'; 

Desde sus puntos de corte pueden variar en función de la distribución de los datos, creo que es necesario para ordenar la lista entera primero y luego bucle sobre ella para hacer el corte.

my $prev = shift @numbers; # already sorted 
my @group = [$prev]; 
my $i  = 0; 

foreach my $n (@numbers) { 
    $i++ if ($n - $prev > 65535); 
    push @{$group[$i]}, $n; 
    $prev = $n; 
} 

Answer 6

me gustaría probar esto:

my @sorted = map { unpack "N" } sort map { pack "N" } @unsorted;