Was ist der schnellste Sortieralgorithmus für 0-65535 Ganzzahlen?

Question

Ich muss eine ganze Reihe von Ganzzahlen sortieren, die Werte zwischen 30.000.000 und 350.000.000 haben können. Es wird zwischen 0 und 65.535 Ganzzahlen geben, wobei die durchschnittliche Anzahl 20.000 beträgt. RAM-Nutzung ist irrelevant und Geschwindigkeit ist nur wichtig.

Später werde ich sie auch in Gruppen aufteilen müssen, wobei die Division immer dann gesetzt wird, wenn die Lücke zwischen zwei dieser Werte> 65.535 ist, wozu ich den Algorithmus brauche.

Wenn es einen Unterschied macht, wird der Algorithmus in einem Perl-Skript verwendet.

Edit: Nachdem ich darüber nachgedacht und die Antworten gelesen habe, bin ich zu etwas gekommen: Ich kümmere mich eigentlich nicht um die Daten selbst. Da ich nur die Anfangs- und Endwerte von Gruppen mit kleinen Lücken finden möchte, muss die Sortierung nur Buckets erstellen und die Daten verwerfen.

Edit2: Nach einigen Tests und die Antworten zur Verfügung gestellt versuchen, fand der schnellste Weg, ich war:

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

Ich hatte gerade eine Reihe von Eimern, bevor der Algorithmus ausgeführt wird, eine für jede Gruppe von 65536 aufeinanderfolgende Werte. Die Buckets enthalten einen Min- und Max-Wert ihres Inhalts, speichern den Inhalt jedoch nicht selbst. Führen Sie nach dem Ausführen des Algorithmus einen einzelnen Durchlauf über die Buckets aus. Wenn es zwei aufeinanderfolgende nicht leere Buckets mit min (bucket2) -max (bucket1) < 65536 gibt, kombinieren Sie sie. Das Kombinieren findet erst statt, wenn der Algorithmus beendet ist. Entsorgen Sie leere Eimer. Dieser Algorithmus ist eine lineare Zeit.

Notieren Sie sich Bucket Sort.

Answer 2

ich eine Radixsort benutzen würde, da Sie zum Gruppieren der Ausgabe.

Answer 3

Ich wollte gerade Radixsort sagen, http://en.wikipedia.org/wiki/Radix_sort jedoch, das ein wenig über sein könnte, was Sie zu implementieren suchen zu, Introsort ist in der Regel die akzeptierte Sortierlösung für Daten http://en.wikipedia.org/wiki/Introsort, dann ist es eine Variante von Quicksort, die es HeapSort schaltet, wenn erreicht kleinere Sets, da es bei kleineren Sets schneller ist als Quicksort.

Answer 4

Wenn Sie die Zahl als Index für ein Array verwenden und dann die Anzahl dieser Position erhöhen, haben Sie sie gruppiert und in einem Durchgang erstellt.

in Pseudo-Code:

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

Wenn der Bereich vor der Zeit bekannt ist, können Sie die Werte Index reduzieren können (beispielsweise der Wert-30000 sie in den richtigen Bereich zu bringen).

Answer 5

Es ist unwahrscheinlich, dass Sie in der Lage sein, einen Sortieralgorithmus in Perl zu schreiben, die besser als Perl builtin sort Funktion ausführen sollen:

Sie mit der Art Pragma, wenn ein bestimmte Algorithmus ist zu sehen, experimentieren besser:

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

Da Ihr Cutpoints auf der Datenverteilung variieren wird, ich glaube, Sie die gesamte Liste sortieren, müssen zuerst, dann Schleife über den Schneid zu tun.

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

Ich würde dies versuchen:

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