Lektion 2.1

Einfache Sortierverfahren: Auswahl, Einfügen, Bubblesort

30 min Lesezeit

Sortierte Daten machen vieles einfacher: In einer sortierten Liste findest du ein Element mit binärer Suche in logarithmisch vielen Schritten, doppelte Einträge stehen nebeneinander, und der Median liegt in der Mitte. Kein Wunder, dass das Sortieren eines der am besten untersuchten Probleme der Informatik ist.

Wir beginnen mit drei Verfahren, die man sich leicht selbst ausdenken könnte. Alle drei haben im ungünstigen Fall einen quadratischen Aufwand. Sie sind trotzdem wichtig: Sie zeigen die Grundideen, und bei kleinen oder fast sortierten Eingaben sind sie in der Praxis oft schneller als ausgefeilte Verfahren. Du kannst jedes davon im Werkzeug Sortieralgorithmen Schritt für Schritt ablaufen lassen und die Vergleiche mitzählen.

Definition

Sortierproblem

Gegeben ist eine Folge a1,a2,…,ana_1, a_2, \dots, a_n von Elementen, die sich paarweise vergleichen lassen. Gesucht ist eine Permutation (Umordnung) der Folge, sodass aπ(1)≤aπ(2)≤⋯≤aπ(n)a_{\pi(1)} \le a_{\pi(2)} \le \dots \le a_{\pi(n)} gilt.

Ein Verfahren heißt stabil, wenn gleiche Elemente ihre ursprüngliche Reihenfolge behalten. Das ist wichtig, wenn du nacheinander nach mehreren Kriterien sortierst (erst nach Vorname, dann nach Nachname). Ein Verfahren arbeitet in place, wenn es außer wenigen Hilfsvariablen keinen zusätzlichen Speicher braucht.

aπ(1)≤aπ(2)≤⋯≤aπ(n)a_{\pi(1)} \le a_{\pi(2)} \le \dots \le a_{\pi(n)}
Definition

Selectionsort (Sortieren durch Auswählen)

Die Idee: Suche in dem noch unsortierten Rest das kleinste Element und tausche es an den Anfang dieses Rests. Dann ist der Anfang ein Stück größer sortiert.

Im ii-ten Durchgang vergleichst du das Minimum mit den restlichen n−in-i Elementen. Insgesamt sind das immer n(n−1)2\frac{n(n-1)}{2} Vergleiche, egal wie die Eingabe aussieht, aber nur höchstens n−1n-1 Vertauschungen. Selectionsort ist deshalb sinnvoll, wenn Vertauschen teuer ist.

(n−1)+(n−2)+⋯+1=n(n−1)2(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}
Definition

Insertionsort (Sortieren durch Einfügen)

Die Idee kennst du vom Kartenspiel: Du hältst die Karten in der Hand sortiert und nimmst die nächste Karte vom Stapel, um sie an der richtigen Stelle einzuschieben. Das Verfahren verschiebt dazu größere Elemente nach rechts, bis die Lücke passt.

Im besten Fall (schon sortiert) braucht es nur n−1n-1 Vergleiche, also O(n)O(n). Im schlechtesten Fall (umgekehrt sortiert) werden alle Paare verglichen: n(n−1)2\frac{n(n-1)}{2}. Insertionsort ist stabil, in place und besonders schnell bei fast sortierten Daten.

beste Laufzeit O(n),schlechteste Laufzeit O(n2)\text{beste Laufzeit } O(n), \qquad \text{schlechteste Laufzeit } O(n^2)
Beispiel

Insertionsort auf [5,2,4,6,1,3][5, 2, 4, 6, 1, 3]

Der sortierte Teil steht links vom senkrechten Strich:

  • Start: [5∣2,4,6,1,3][5 \mid 2, 4, 6, 1, 3]
  • Füge 22 ein: [2,5∣4,6,1,3][2, 5 \mid 4, 6, 1, 3]
  • Füge 44 ein: [2,4,5∣6,1,3][2, 4, 5 \mid 6, 1, 3]
  • Füge 66 ein: [2,4,5,6∣1,3][2, 4, 5, 6 \mid 1, 3] (kein Verschieben nötig)
  • Füge 11 ein: [1,2,4,5,6∣3][1, 2, 4, 5, 6 \mid 3] (alle vier Elemente rutschen nach rechts)
  • Füge 33 ein: [1,2,3,4,5,6][1, 2, 3, 4, 5, 6]

Die Zahl der nötigen Verschiebungen entspricht der Zahl der Inversionen, also der Paare, die in falscher Reihenfolge stehen. Hier sind es (5,2),(5,4),(5,1),(5,3),(2,1),(4,1),(4,3),(6,1),(6,3)(5,2), (5,4), (5,1), (5,3), (2,1), (4,1), (4,3), (6,1), (6,3), also 99 Inversionen.

Definition

Bubblesort

Die Idee: Gehe die Folge von links nach rechts durch und vertausche jedes Paar benachbarter Elemente, das in falscher Reihenfolge steht. Nach dem ersten Durchlauf ist das größte Element ganz rechts angekommen, wie eine Blase, die aufsteigt. Wiederhole das für den Rest.

Bubblesort ist stabil und in place. Die Zahl der Vertauschungen entspricht genau der Zahl der Inversionen. Mit einer Abbruchbedingung (kein Tausch im Durchlauf, also bereits sortiert) erreicht Bubblesort im besten Fall O(n)O(n), im schlechtesten und mittleren Fall O(n2)O(n^2). In der Praxis ist Bubblesort langsamer als Insertionsort, wird aber gern zur Veranschaulichung benutzt.

Vertauschungen=Anzahl der Inversionen≤n(n−1)2\text{Vertauschungen} = \text{Anzahl der Inversionen} \le \frac{n(n-1)}{2}

Zusammenfassung

  • Selectionsort wählt wiederholt das Minimum aus: immer n(n−1)2\frac{n(n-1)}{2} Vergleiche, aber höchstens n−1n-1 Vertauschungen.

  • Insertionsort fügt jedes Element in den sortierten Teil ein: O(n)O(n) im besten, O(n2)O(n^2) im schlechtesten Fall, stabil, gut bei fast sortierten Daten.

  • Bubblesort vertauscht benachbarte Paare; die Zahl der Vertauschungen ist die Zahl der Inversionen.

  • Alle drei sind im schlechtesten Fall quadratisch und deshalb nur für kleine Eingaben geeignet.

  • Stabil heißt: gleiche Elemente behalten ihre Reihenfolge.

Übungen

Aufgabe 1Numerisch

Wie viele Vergleiche führt Selectionsort bei einer Folge der Länge 88 aus?

Aufgabe 2Multiple Choice

Wie sieht die Folge [4,3,1,2][4, 3, 1, 2] nach dem ersten vollständigen Durchlauf von Bubblesort aus?

Aufgabe 3Numerisch

Wie viele Inversionen hat die Folge [3,1,2][3, 1, 2]? (So viele Vertauschungen benötigt Bubblesort.)

Aufgabe 4Freitext

Warum ist Insertionsort bei einer fast sortierten Folge viel schneller als Selectionsort?