Einzelnen Beitrag anzeigen

Daniel
(Administrator)

Registriert seit: 30. Mai 2002
Ort: Hamburg
14.214 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#2
  Alt 10. Jul 2002, 20:38
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
  Mit Zitat antworten Zitat