Tutorial: Sortier-Algorithmen I+II

[Daniel]

Bitte beachten: Dieses Tutorial muss überarbeitet werden, dazu fehlt im Moment aber einfach die Zeit.sorry


Sortier-Algorithmen

Eines der grundlegenden Probleme der Informatik: Das Sortieren einer Menge an Daten. Es gibt viele verschiedene Verfahren, die sich mehr oder weniger gut für den Einsatz in einem Programm eignen.

Man kann Sortierverfahren grob in zwei Klassen unterteilen: In die sogenannten internen Sortierverfahren und in die externen Sortierverfahren. Ein internes Sortierverfahren zeichnet sich dadurch aus, dass die zu sortierenden Daten im Speicher (z.B. in einem Array) untergebracht werden. Der Zugriff auf jeden einzelnen Datensatz ist hier leicht und vor allem schnell realisiert. Das genaue Gegenteil haben wir bei den externen Sortierverfahren, bei denen die zu sortierenden Daten auf einem (externen) Speichermedium vorliegen und der Zugriff sequentiell oder blockweise erfolgen muss.

Ich werde im Rahmen dieses Tutorials lediglich auf interne Verfahren eingehen. Es sind im Wesentlichen diejenigen Verfahren, die als die Standard-Verfahren bekannt sind:

• Selection-Sort
• Insertion-Sort
• Bubble-Sort
• Shell-Sort
• QuickSort
• Heap-Sort
• Merge-Sort

Alle diese Sortier-Verfahren machen im Endeffekt genau das Gleiche: Sie sortieren ein Array von Zahlen. Allerdings unterscheiden sie sich in drei Faktoren:

• benötigte Dauer
• benötigter Speicherplatz
• benötigte Anzahl an Vergleichen

Die Bedeutung dieser Faktoren, welche die Leistungsfähigkeit eines Verfahrens bestimmen, steigt mit der Menge der zu sortierenden Daten. Hat man nur wenige Datensätze oder sortiert nur selten, so kann es sinnvoller sein, einen einfachen Algorithmus zu Nutzen, der zwar ein wenig länger braucht, dafür aber schnell und fehlerfrei programmiert ist.
Bei weniger als zweitausend Datensätzen im Speicher macht es oftmals keinen Sinn, sich große Gedanken über einen schnellen Sortier-Algorithmus zu machen. Die Unterschiede liegen im Bereich von unter einer Sekunde.

Um die oben genannten Algorithmen in Bezug auf die drei wesentlichen Kenngrößen analysieren zu können, werde ich sie jetzt hier der Reihe nach vorstellen. Zuvor noch eine kurze Bemerkung zur den Beispiel-Codes:
Die Anzahl der zu sortierenden Elemente bezeichne ich mit dem Buchstaben N. (Dies ist die in der Fachliteratur gängige Methode). Zudem unterstelle ich als Datenfeld ein Array, welches von 1..N indiziert ist.

Selection-Sort
"Sortieren durch direktes Auswählen"
Der Selection-Sort ist einer der einfachsten Sortier-Algorithmen und läuft nach folgendem Schema ab:
Finde zuerst das kleinste Element und tausche es gegen das an erster Stelle befindliche Element aus, finde danach das zweitkleinste Element und tausche es gegen das an zweiter Stelle befindliche Element aus und setze dies so lange fort, bis das gesamte Feld sortiert ist.

Code:

Procedure SelectionSort;
var i, j, min : Integer;
Begin
  For i:= 1 to N-1 Do
  Begin
    min:= i;
    For j:= i+1 To N Do
      If (Data[j] < Data[min]) Then min:= j;

    SwapValues( i, min);
  End;
End;

Ich werde später noch darauf eingehen, dass dieser Algorithmus nicht einer der schnellsten ist. Dennoch hat er eine Eigenschaft, die sich unter Umständen als sehr positiv erweisen kann: Jeder Datensatz wird höchstens einmal verschoben. Gerade bei sehr großen Datensätzen kann dies ein Vorteil sein.


Insertion-Sort
"Sortieren durch direktes Einfügen"
Dieser Algorithmus ist fast so einfach wie der Selection-Sort, jedoch ein wenig flexibler. Dies ist eine Methode, die Menschen oft beim Kartenspiel anwenden, um die auf ihrer Hand befindlichen Karten zu sortieren:
Betrachte die Elemente eines nach dem anderen und fügen jedes an seinen richtigen Platz zwischen den bereits betrachteten Elementen ein.
Hierzu wird erst eine Lücke geschaffen (die größeren Elemente werden nach rechts gerückt) und dann kann man auf den frei gewordenen Platz das aktuelle Element einfügen.

Code:

Procedure InsertionSort;
var i,j,v : Integer;
Begin
  For i:= 2 To N 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;

Bubble-Sort
"Sortieren durch direktes Austauschen"
Dieser Algorithmus ist bestimmt in jedem Informatik-Grundkurs und jeder Informatik-Vorlesung gelehrt worden. Er gehört eindeutig zu den gemütlichen Sortier-Algorithmen. Schon bei 100.000 Elementen kann sich erst mal einen Kaffee holen, bevor dieser Algorithmus mit seiner Arbeit fertig ist. Trotzdem ist er leicht zu begreifen:
Durchlaufe immer wieder das Feld und tausche wenn nötig zwei benachbarte Elemente miteinander aus.

Code:

Procedure BubbleSort;
var i,j : Integer;
Begin
  For i:= N downto 1 Do
    For j:= 1 To i Do
      If (Data[j-1] > Data[j]) Then SwapValues( j-1, j );
End;

Shell-Sort
Der Shell-Sort ist eine Erweiterung des Insertion-Sort und setzt genau dort an, wo dieser seine Schwäche hat. Insertion-Sort ist langsam, weil stets nur benachbarte Elemente ausgetauscht werden. Steht zufälligerweise das kleinste Element ganz hinten, so werden N Vertauschungen benötigt, um es an seine richtige Position zu bringen.
Der Shell-Sort vertauscht also auch weit voneinander entferne Elemente miteinander. Diese Distanz wird als "h" bezeichnet. Der Grundgedanke besteht nun darin, dass man die Daten so umordnet, dass man eine sortierte Reihenfolge erhält, wenn man jedes h-te Element entnimmt. Lässt man dieses "h" nun gegen 1 laufen, wird nach und nach die gesamte Datenmenge sortiert.

Code:

Procedure ShellSort;
var i, j, h, v : Integer;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > N);

  Repeat
    h:= (h div 3);
    For i:= (h+1) To N Do
    Begin
      v:= Data[i];
      j:= i;

      While ((j > h) and (Data[j-h] > v)) Do
      Begin
        Data[j]:= Data[j-h];
        dec( j, h );
      End;
      Data[j]:= v;
    End;
  Until (h = 1);
End;

Quick-Sort
Der Quick-Sort wurde 1960 entwickelt und dürfte einer der am häufigsten angewandten Sortier-Algorithmen sein. Seinen Namen verdient er der Tatsache, dass er für das Sortieren von N Elementen im Durchschnitt nur N * log (N) Operationen benötigt. (Ob das viel oder wenig ist, werden wir noch sehen) Der Quick-Sort kann sowohl rekursiv als auch iterativ programmiert werden. In rekursiver Variante belastet er den Stack-Speicher - dies kann bei großen Datenmengen zu einem Stack-Überlauf führen. In iterativer Variante läuft er zwar ein wenig langsamer, belastet dafür aber nur den Heap, welcher üblicherweise weniger beschränkt ist als der Stack.
Einen gravierenden Nachteil hat der Quick-Sort allerdings auch: Im ungünstigsten Fall benötigt er N*N Operationen, um die sortierte Reihenfolgen herzustellen. In diesem Fall zeigt er ein ähnlich schlechtes Verhalten wie der Bubble-Sort.
Das Prinzip des Quick-Sort beruht auf dem Prinzip, die Daten in Teilmengen aufzuspalten und diese unabhängig voneinander zu sortieren. Die rekursive Variante des Quick-Sort hat folgenden Rumpf:

Code:

Procedure QuickSort( l,r : Integer );
var i : Integer;
Begin
  If (r > l) Then
  Begin
    i:= Partition( l, r);
    QuickSortRekursiv( l, i-1 );
    QuickSortRekursiv( i+1, r );
  End;
End;

Von entscheidender Bedeutung ist hierbei die Prozedur "Partition". Diese muss das Datenfeld so umsortieren, dass drei Bedingungen erfüllt sind:

• das Element Daten[ i ] befindet sich an seinem endgültigen Platz
• alle Elemente, die links von i liegen, sind kleiner oder gleich dem Element Daten[ i ]
• alle Elemente, die rechts von i liegen, sind größer oder gleich dem Element Daten[ i ]

Die Methodik, nach der vorgegangen wird, um diese Ziele zu erreichen, ist von entscheidender Bedeutung für die Leistungsfähigkeit des Algorithmus. (Mehr zu diesem Aspekt später)
Diese Prozedur setzt i = r und wählt somit willkürlich das Element ganz rechts (also ist Data[ i ] = Data[ r ]) und sucht jetzt von links beginnend ein Element, welches größer als Data[ i ] ist. Nun wird von rechts beginnend ein Element gesucht, welches kleiner als Data[ i ] ist. Beide gefundenen Elemente werden vertauscht. Fährt man so fort, ist sicher gestellt, dass die Teildatenmenge sortiert ist und dass das anfangs ausgewählte Element an seiner endgültigen Position liegt. Je näher i in der Mitte des Feldes liegt, desto erfolgreicher war die Partitionierung. (An dieser Stelle werden wir später noch optimieren)

Code:

Function Partition( l,r : Integer ) : Integer;
var v,t,i,j : Integer;
Begin
  v:= Data[r];
  i:= l-1;
  j:= r;
  Repeat
    Repeat inc( i ); Until (Data[i] >= v);
    Repeat dec( j ); Until (Data[j] <= v);
    t:= Data[i]; Data[i]:= Data[j]; Data[j]:= t;
  Until (j<=i);

  Data[j]:= Data[i]; Data[i]:= Data[r]; Data[r]:= t;
  Result:= i;
End;

Man kann wie bereits erwähnt die Rekursion entfernen. Man muss jedoch noch eine Hilfs-Struktur schaffen, in welcher man sich die Indizes der Teilmengen merkt. Hier bietet sich die Datenstruktur "Stack" an. (Ich setzte diese als bekannt voraus, kann aber auf Wunsch gerne einmal tiefer auf "Stacks" eingehen)
Die rekursiven Aufrufe werden also durch Stack-Operationen ersetzt und es wird eine innere Schleife hinzugefügt, welche solange läuft, bis der Stack vollständig abgearbeitet ist.

Code:

Procedure QuickSortIterativ;
var i, l, r : Integer;     
Begin
  l:= 1; r:= N;
  Stack.Push( l ); Stack.Push( r );

  Repeat
    If (r > l) Then
    Begin
      i:= Partition( l, r );
      If (i-l) > (r-i) Then
      Begin
        Stack.Push( l );
        Stack.Push( i-1 );
        l:= i+1;
      End
      Else
      Begin
        Stack.Push( i+1 );
        Stack.Push( r );
        r:= i-1;
      End;
    End
    Else
    Begin
      r:= Stack.Pop;
      l:= Stack.Pop;
    End;
  Until StackisEmpty;
End;

Wichtig hier bei ist, dass die Indizes der Teilmengen nicht in beliebiger Reihenfolge abgelegt werden, sondern dass die Indizes der größeren Teilmenge immer zuerst auf den Stack geschrieben werden. Dies bewirkt, dass der Stack im Durchschnitt lediglich für log(N) Einträge Platz bieten muss. Im ungünstigsten Fall könnte die Belastung des Stacks N erreichen.


Heap-Sort
(Es sind jetzt Vorkenntnisse in Bezug auf Bäume und deren Repräsentation als Feld (Array) nötig. Auf Wunsch kann ich gerne einmal näher darauf eingehen)
Der Heap-Sort basiert auf der Datenstruktur "Heap". Darunter versteht man einen Binärbaum, der die sog. Heap-Bedingung erfüllt. Unter dieser Heap-Bedingung versteht man die Eigenschaft, dass der größte (oder der kleinste) Wert stets an der Wurzel steht und dass alle folgenden Knoten die Bedingung erfüllen, dass der Wert jedes Knotens größer (oder kleiner) gleich dem seiner Nachfolger ist.
Das Prinzip des Heap-Sort basiert darauf, aus den zu sortierenden Daten einen Heap zu konstruieren, dann die Elemente nacheinander vom Heap zu entfernen und nach jedem Entfernen die Heap-Bedingung wieder herzustellen.

Code:

Procedure HeapSort;
var i, k, m : Integer;
Begin
  m:= N;
  k:= m div 2;

  For i:= k downto 1 Do downHeap( i, m );

  While (m > 1) Do
  Begin
    SwapValues( 1, m );
    dec( m );
    downHeap( 1, m );
  End;
End;

Von zentraler Bedeutung ist die Methode "downHeap", welche die Heap-Bedingung wider herstellt:

Code:

Procedure downHeap( index, heapSize : Integer );
var j, k, m, v : Integer;
Begin
  k:= index;
  v:= Data[k];
  m:= heapSize;
  While (k <= (m div 2)) Do
  Begin
    j:= 2*k;
    If (j < n) Then
      If (Data[j] < Data[j+1]) Then inc( j );
    If (v > Data[j]) Then
    Begin
      Data[k]:= v;
      Exit;
    End;
    SwapValues( k, j );
    k:= j;
  End;
End;

Der Heapsort hat den eindeutigen Vorteil, dass er ohne zusätzlichen Speicher auskommt und zudem selbst im ungünstigsten Fall noch eine nahezu konstante Laufzeit von N * log(N) garantiert. (Ich gehe später darauf ein, wie dieser Umstand zu bewerten ist)

Merge-Sort
Der Merge-Sort sortiert eine Datenmenge, indem er sie in Hälften teilt, diese dann (rekursiv) sortiert und anschließend zusammenfügt. Der Mergesort hat eine Eigenschaft, die als wesentlicher Vorteil gesehen werden kann: Man kann ihn so implementieren, dass der Zugriff auf die Daten hauptsächlich sequentiell erfolgt. Zum Beispiel ist der Mergesort ein gern genutztes Sortier-Verfahren für verkettete Listen, bei denen ein sequentieller Zugriff die einzig mögliche Zugriffsart ist. Leider hat er aber auch einen Nachteil: Er benötigt proportional zu N weiteren Speicher. (Im Code-Beispiel durch 'HilfsArray' dargestellt)

Code:

Procedure MergeSort( l, r : Integer );
var i, j, k, m : Integer;
Begin
  If (l < r) Then
  Begin
    m:= (r+l) div 2;

    MergeSort( l, m  );
    MergeSort( m+1, r );

    For i:= l To m Do HilfsArray[i]:= Data[i];
    i:= l;

    For j:= m+1 To r Do HilfsArray[r+m+1-j]:= Data[j];
    j:= r;

    For k:= l To r Do
    Begin
      If (HilfsArray[i] < HilfsArray[j]) Then
      Begin
        Data[k]:= HilfsArray[i];
        inc( i );
      End
      Else
      Begin
        Data[k]:= HilfsArray[j];
        dec( j );
      End;
    End;
  End;
End;

Das war also ein erster Überblick über die Standard-Sortierverfahren. Ich hoffe, dass ich mich einigermaßen verständlich ausgedrückt habe. Für Fragen und Anmerkungen bin ich natürlich jederzeit offen.

Im nächsten Teil werde ich die vorstellten Algorithmen hinsichtlich der Laufzeit analysieren und vergleichen. In diesem Zusammenhang werde ich auch Varianten des Quick- und Heap-Sorts vorstellen, welche Laufzeit drastisch verbessern. Dann wird es auch das vollständige Programm-Listing zum Download geben.

Grüße,
Daniel