Sortieralgorithmen

1.2.1. Sortieralgorithmen#

Sortieralgoritmen werden genutzt um Listen von Werten der Größe nach zu sortieren. Anwendung finden diese Algorithmen bei Datenbanken oder Suchvorgängen. Insbesondere bei langen Listen mit Millionen oder Milliarden Einträgen ist es wichtig, dass der Algorithmus mit möglichst wenigen Operationen pro Element auskommt. Diese, als Komplexität bezeichnete Eigenschaft, wird im nächsten Kapitel genauer erläutert.

Zunächst werden zwei einfache Sortieralgorithmen

vorgestellt. Diese werden in der Praxis kaum noch eingesetzt, da es eine Vielzahl anderer Sortierverfahren gibt, welche effektiver arbeiten. Jedoch eignen sich diese beiden besonders gut, um die Grundideen zu verdeutlichen.

Selectionsort#

Folgende Grundidee liegt dem Selectionsort zugrunde: Es wird der minimale Wert der Liste gesucht, dann der zweit-kleinste und so weiter bis die ganze Liste sortiert ist. Dies kann als Abfolge dieser Schritte für eine Liste mit \(\sf n\) Elementen formalisiert werden.

  1. Wiederhole die Schritte 2 bis 4 \(\sf n\) Mal. Setzte die Hilfsvariable \(i\) initial auf Null.

  2. Suche den minimalen Wert der Liste ab dem \(\sf i\)-ten Element.

  3. Tausche dieses Element mit dem \(\sf i\)-ten Element.

  4. Erhöhe den Wert von \(\sf i\) um Eins.

  5. Die Vertauschungen der Elemente haben zu einer sortierten Liste geführt.

Der Selectionsort kann auch als folgendes Flussdiagramm dargestellt werden.

../../../_images/alg_selsort.svg

Fig. 1.17 Flussdiagramm des Selectionsort#

Als Zahlenbeispiel wird die Liste mit den Elementen 42, 6, 22, 11, 54, 12, 31 mit dem Selectionsort sortiert.

Zu sortierende Werteliste  [42, 6, 22, 11, 54, 12, 31]

Iteration  1: 
   Minimum von  [42, 6, 22, 11, 54, 12, 31] ist 6
   Sortiert / Unsortiert:  [6] / [42, 22, 11, 54, 12, 31]

Iteration  2: 
   Minimum von  [42, 22, 11, 54, 12, 31] ist 11
   Sortiert / Unsortiert:  [6, 11] / [22, 42, 54, 12, 31]

Iteration  3: 
   Minimum von  [22, 42, 54, 12, 31] ist 12
   Sortiert / Unsortiert:  [6, 11, 12] / [42, 54, 22, 31]

Iteration  4: 
   Minimum von  [42, 54, 22, 31] ist 22
   Sortiert / Unsortiert:  [6, 11, 12, 22] / [54, 42, 31]

Iteration  5: 
   Minimum von  [54, 42, 31] ist 31
   Sortiert / Unsortiert:  [6, 11, 12, 22, 31] / [42, 54]

Iteration  6: 
   Minimum von  [42, 54] ist 42
   Sortiert / Unsortiert:  [6, 11, 12, 22, 31, 42] / [54]

Iteration  7: 
   Minimum von  [54] ist 54
   Sortiert / Unsortiert:  [6, 11, 12, 22, 31, 42, 54] / []

Bubblesort#

Im Gegensatz zum Selectionsort beruht die Idee des Bubblesort auf rein lokalen Operationen. D.h. hier wird nicht nach den maximalen Werten gesucht, sondern durch Vertauschungen eine Sortierung erzielt. Das Verfahren für eine Liste mit \(\sf n\) Elementen ist durch folgende Vorschrift gegeben.

  1. Die Schritte 2 bis 4 werden \(\sf n\) Mal durchgeführt. Die Hilfsvariable \(\sf i\) wird initial auf Null gesetzt.

  2. Starte beim \(\sf i\)-ten Element und iteriere bis zum Ende der Liste. Falls das aktuell betrachtete Element größer ist als das Folgende, tausche beide Elemente.

  3. Falls in Schritt 2 keine Vertauschungen durchgeführt wurden, gehe zu Schritt 5.

  4. Addiere Eins zum Wert der Variable \(\sf i\).

  5. Die Liste ist sortiert und der Algorithmus ist fertig.

Das nachfolgende Flussdiagramm verdeutlicht den Ablauf des Bubblesort Algorithmus.

../../../_images/alg_bubblesort.svg

Fig. 1.18 Flussdiagramm des Bubblesort#

Der Ablauf des Bubblesort wird beispielhaft für die Liste 42, 6, 22, 11, 54, 12, 31 (gleich der im obigen Beispiel) vorgeführt.

Zu sortierende Werteliste  [42, 6, 22, 11, 54, 12, 31]

Iteration  1: 
   Liste zu Beginn der Iteration:  [42, 6, 22, 11, 54, 12, 31]
   Tausche:  42 und 6
   Liste nach Tausch:  [6, 42, 22, 11, 54, 12, 31]
   Tausche:  42 und 22
   Liste nach Tausch:  [6, 22, 42, 11, 54, 12, 31]
   Tausche:  42 und 11
   Liste nach Tausch:  [6, 22, 11, 42, 54, 12, 31]
   Elemente  42 und 54  müssen nicht getauscht werden
   Tausche:  54 und 12
   Liste nach Tausch:  [6, 22, 11, 42, 12, 54, 31]
   Tausche:  54 und 31
   Liste nach Tausch:  [6, 22, 11, 42, 12, 31, 54]

Iteration  2: 
   Liste zu Beginn der Iteration:  [6, 22, 11, 42, 12, 31, 54]
   Elemente  6 und 22  müssen nicht getauscht werden
   Tausche:  22 und 11
   Liste nach Tausch:  [6, 11, 22, 42, 12, 31, 54]
   Elemente  22 und 42  müssen nicht getauscht werden
   Tausche:  42 und 12
   Liste nach Tausch:  [6, 11, 22, 12, 42, 31, 54]
   Tausche:  42 und 31
   Liste nach Tausch:  [6, 11, 22, 12, 31, 42, 54]

Iteration  3: 
   Liste zu Beginn der Iteration:  [6, 11, 22, 12, 31, 42, 54]
   Elemente  6 und 11  müssen nicht getauscht werden
   Elemente  11 und 22  müssen nicht getauscht werden
   Tausche:  22 und 12
   Liste nach Tausch:  [6, 11, 12, 22, 31, 42, 54]
   Elemente  22 und 31  müssen nicht getauscht werden

Iteration  4: 
   Liste zu Beginn der Iteration:  [6, 11, 12, 22, 31, 42, 54]
   Elemente  6 und 11  müssen nicht getauscht werden
   Elemente  11 und 12  müssen nicht getauscht werden
   Elemente  12 und 22  müssen nicht getauscht werden
   kein Tausch mehr notwendig, Liste ist nun sortiert
Contents