Nachdem ich im letzten Teil die Standard-Algorithmen in gängigen Implementationen vorgestellt habe, will ich jetzt dazu kommen, diese zu vergleichen.
Als Basis habe ich ein Array mit 100.000 Elementen, welches einmalig mit Zufallszahlen gefüllt wird. Dieses Array wurde gesichert und für jeden Sortier-Algorithmus in genau der selben Form wieder hergestellt, so dass alle hier behandelten Algorithmen die gleiche Ausgangs-Situation vorfanden.
Verglichen werden jeweils die Laufzeit sowie die benötigte Anzahl an Vergleichen:
Bubble-Sort
Dauer: 74.157 ms
Anzahl Vergleiche: 5 * 10^9
Selection-Sort
Dauer: 42.341 ms
Anzahl Vergleiche: 5 * 10^9
Insertion-Sort
Dauer: 20.359 ms
Anzahl Vergleiche: 2,5 * 10^9
Shell-Sort
Dauer: 80 ms
Anzahl Vergleiche: 7.146.727
Quick-Sort (Rekursiv)
Dauer: 30 ms
Anzahl Vergleiche: 2.224.657
Quick-Sort (Iterativ)
Dauer: 71 ms
Anzahl Vergleiche: 2.224.657
Heap-Sort
Dauer: 65 ms
Anzahl Vergleiche: 2.984.590
Merge-Sort
Dauer: 40 ms
Anzahl Vergleiche: 1.668.946
Wie man unschwer erkennen kann, bilden der Bubble-, der Selection- und der Insertion-Sort die Schlusslichter.
Für diese Anzahl an Elementen spielt es ansonsten kaum eine Rolle, für welchen Algorithmus man sich entscheidet. Das könnte man zumindest meinen... Interessant wird es jetzt, wenn man sich die Anzahl an benötigten Vergleichen ansieht. Dieser Wert wird genau dann wichtig, wenn der Zugriff auf die benötigten Elemente Zeit kostet. In solch einem Szenario wäre es wichtig, die Vergleiche zu minimieren, um so die gesamte Laufzeit zu drücken. Folgende Variationen des Heap- und des Quicksort bringen diesbezüglich weitere Vorteile:
Heap-Sort (Optimiert)
Dauer: 50 ms
Anzahl Vergleiche: 1.560.387
Quick-Sort (Rekursiv / Optimiert)
Dauer: 20 ms
Anzahl Vergleiche: 1.628.846
Was verbirgt sich hinter diesen Varianten? Nun - der Heapsort hält sich lange damit auf, die Heapbedingung wieder herzustellen. Zu diesem Zweck schreibt er die Werte immer ganz nach unten an den Heap und bringt die von dort aus in die richtige Position. Es hat sich aber gezeigt, dass es im Mittel reicht, nur die halbe Strecke zurück zu legen und die Werte von der Mitte aus an die richtige Position zu bringen - sei es nun nach oben oder unten.
Code:
Procedure downHeapRisky( index, heapSize : Integer );
var ix, son1, son2, ixson : Integer;
Begin
ix:= index;
While (ix <= (heapSize div 2)) Do
Begin
son1:= 2 * ix;
son2:= son1 + 1;
If (son2 > heapSize) or (Data[son1] > Data[son2]) Then
ixson:= son1
Else
ixson:= son2;
SwapValues( ix, ixSon );
ix:= ixSon;
End;
upHeap( index, ix );
End;
Procedure upHeap( index, heapSize : Integer );
var temp, upix, upix2 : Integer;
Begin
temp:= Data[heapSize];
upix:= heapSize;
upix2:= upix div 2;
While ((upix2 >= index) and (Data[upix2] < temp)) Do
Begin
SwapValues( upix, upix div 2 );
upix:= upix div 2;
upix2:= upix div 2;
End;
Data[upix]:= temp;
End;
Procedure HeapSortFast;
var size, i : Integer;
Begin
size:= AnzahlElemente;
For i:= (size div 2) downTo 1 Do downHeapRisky( i, size );
For i:= 1 To size Do
Begin
SwapValues( 1, size-i+1 );
downHeapRisky( 1, size-i );
End;
End;
Und was wurde beim Quicksort geändert? Der wesentliche Vorteil des Quicksorts liegt darin, dass er die Daten über große Entfernungen hin austauschen kann. (
Aus genau dem konträren Verhalten heraus ist der Bubble-Sort so langsam; er tauscht lediglich benachbarte Elemente aus). Je näher der Quicksort dem Ende kommt, desto häufiger hat er die Daten geteilt und desto kleiner werden die Teilmengen. Hier wird der Quicksort mehr und mehr ineffizient, da der Verwaltungsaufwand für die Rekursion oder den eigenen Stack deutlicher ins Gewicht fallen. Also hört man einfach auf, wenn die Größe der Mengen eine Größe von beispielsweise 25 erreicht haben. Dann setzt man einen Insertion-Sort ein, der bei kleinen vor-sortierten Teilmengen unschlagbar schnell ist. In dieser Kombination erreicht man den o.g. Vorteil.
Code:
Procedure InsertionSortForQuickSort;
var i,j,v : Integer;
Begin
For i:= ErstesElement+1 To LetztesElement Do
Begin
v:= Data[i];
j:= i;
While (j > 1) and (Data[j-1] > v) Do
Begin
Data[j]:= Data[j-1];
dec( j );
End;
Data[j]:= v;
End;
End;
Procedure QuickSortOptimal( l, r : Integer );
var i, j, p, q, v, k : Integer;
Begin
i:= l-1;
p:= l-1;
j:= r;
q:= r;
v:= Data[r];
If (r - l) > 20 Then
Begin
Repeat
inc( i );
While (Data[i] < v) Do
Begin
inc( i );
End;
dec( j );
While (v < Data[j]) Do
Begin
dec( j );
If (j < l) Then Break;
End;
If (i >= j) Then Break;
SwapValues(i, j);
If (Data[i] = v) Then
Begin
inc( p );
SwapValues( p, i );
End;
If (Data[j] = v) Then
Begin
dec( q );
SwapValues( j, q );
End;
until (j < i);
SwapValues( i, r );
j:= i-1;
inc( i );
k:= l;
While (k < p) Do
Begin
inc( k );
dec( j );
SwapValues( k, j );
End;
k:= r-1;
While (k > q) Do
Begin
dec( k );
inc( i );
SwapValues( i, k );
End;
QuickSortOptimal( l, j);
QuickSortOptimal( i, r);
End;
End;
Ich hoffe, dass der eine oder andere ein paar für ihn brauchbare Infos herausziehen konnte (wenngleich es natürlich ein etwas spezielleres Thema ist...
)
Grüße,
Daniel
Daniel R. Wolf