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.
Wiederhole die Schritte 2 bis 4 \(\sf n\) Mal. Setzte die Hilfsvariable \(i\) initial auf Null.
Suche den minimalen Wert der Liste ab dem \(\sf i\)-ten Element.
Tausche dieses Element mit dem \(\sf i\)-ten Element.
Erhöhe den Wert von \(\sf i\) um Eins.
Die Vertauschungen der Elemente haben zu einer sortierten Liste geführt.
Der Selectionsort kann auch als folgendes Flussdiagramm dargestellt werden.
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.
Die Schritte 2 bis 4 werden \(\sf n\) Mal durchgeführt. Die Hilfsvariable \(\sf i\) wird initial auf Null gesetzt.
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.
Falls in Schritt 2 keine Vertauschungen durchgeführt wurden, gehe zu Schritt 5.
Addiere Eins zum Wert der Variable \(\sf i\).
Die Liste ist sortiert und der Algorithmus ist fertig.
Das nachfolgende Flussdiagramm verdeutlicht den Ablauf des Bubblesort Algorithmus.
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