Sortieren durch Einfügen
Das dritte Verfahren ist das, mit dem die meisten Menschen tatsächlich Karten sortieren – wahrscheinlich auch du, ohne je darüber nachgedacht zu haben.
Die Idee
Sortieren durch Einfügen (englisch insertion sort):
Nimm ein Element nach dem anderen aus dem unsortierten Teil und füge es an der richtigen Stelle in den bereits sortierten Teil ein. Alle größeren Elemente rücken dabei um eine Position nach rechts.
So sortiert man ein Blatt Spielkarten: Man nimmt eine Karte auf und schiebt sie zwischen die schon sortierten.
Der Ablauf mit 5 2 4 1 8. Der senkrechte Strich trennt sortiert von unsortiert:
| Schritt | Feld | Aktion |
|---|---|---|
| Start | 5 | 2 4 1 8 |
die 5 allein gilt als sortiert |
| 1 | 2 5 | 4 1 8 |
2 vor die 5 einfügen |
| 2 | 2 4 5 | 1 8 |
4 zwischen 2 und 5 einfügen |
| 3 | 1 2 4 5 | 8 |
1 ganz nach vorne |
| 4 | 1 2 4 5 8 | |
8 bleibt hinten |
Führe das Verfahren auf Papier an dem Feld 3 7 1 9 4 durch. Notiere nach jedem Schritt den Zustand und die Position des Trennstrichs.
Auflösung
| Schritt | Feld | eingefügt |
|---|---|---|
| Start | 3 | 7 1 9 4 |
|
| 1 | 3 7 | 1 9 4 |
7 bleibt, wo sie ist |
| 2 | 1 3 7 | 9 4 |
1 ganz nach vorne |
| 3 | 1 3 7 9 | 4 |
9 bleibt hinten |
| 4 | 1 3 4 7 9 | |
4 zwischen 3 und 7 |
Zwei Teilaufgaben
Das Verfahren zerfällt sauber in zwei Teile – das ist Modularisierung in der Praxis:
- Die Stelle finden, an die das Element gehört.
- Platz schaffen, indem alle größeren Elemente nach rechts rücken.
In der üblichen Umsetzung erledigt man beides gleichzeitig: Man wandert vom Einfügeelement aus nach links und schiebt dabei jedes zu große Element eine Position nach rechts. Sobald ein kleineres kommt, ist die Lücke die richtige Stelle.
┌──────────────────────────────────────────────────────────┐
│ für i von 1 bis n - 1 │
│ ┌────────────────────────────────────────────────────┐ │
│ │ merker ← werte[i] │ │
│ ├────────────────────────────────────────────────────┤ │
│ │ j ← i - 1 │ │
│ ├────────────────────────────────────────────────────┤ │
│ │ solange j >= 0 und werte[j] > merker │ │
│ │ ┌──────────────────────────────────────────────┐ │ │
│ │ │ werte[j + 1] ← werte[j] │ │ │
│ │ ├──────────────────────────────────────────────┤ │ │
│ │ │ j ← j - 1 │ │ │
│ │ └──────────────────────────────────────────────┘ │ │
│ ├────────────────────────────────────────────────────┤ │
│ │ werte[j + 1] ← merker │ │
│ └────────────────────────────────────────────────────┘ │
└──────────────────────────────────────────────────────────┘In Java
Zwei Stellen in diesem Code sind erklärungsbedürftig.
a) Warum beginnt die äußere Schleife bei i = 1 und nicht bei 0?
b) Warum steht in der Bedingung j >= 0 && vor dem Vergleich – und was passiert, wenn man die beiden Teile vertauscht?
Auflösung
a) Ein einzelnes Element ist immer schon sortiert. Der Bereich werte[0] bis werte[0] braucht keine Behandlung – man fängt beim zweiten Element an.
b) Die Bedingung j >= 0 schützt den Zugriff pWerte[j]. Wandert das Einfügeelement bis ganz nach vorne, wird j irgendwann -1 – und pWerte[-1] gäbe einen Laufzeitfehler.
Java wertet && von links nach rechts aus und hört auf, sobald das Ergebnis feststeht. Ist j >= 0 falsch, wird pWerte[j] > merker gar nicht mehr ausgewertet. Das nennt man Kurzschlussauswertung.
Vertauscht man die beiden Teile, wird zuerst pWerte[-1] ausgewertet – und das Programm stürzt ab. Probiere es aus.
Kurzschlussauswertung: Bei a && b wird b nur ausgewertet, wenn a wahr ist. Bei a || b nur, wenn a falsch ist.
Das ist nicht nur eine Optimierung, sondern ein Werkzeug: Man stellt die Prüfung, die den Zugriff absichert, nach vorne.
Der beste Fall
a) Wie viele Verschiebungen macht das Verfahren bei einem bereits sortierten Feld?
b) Wie viele bei einem rückwärts sortierten?
c) Vergleiche mit den beiden anderen Verfahren. Welches ist bei fast sortierten Daten am besten?
Auflösung
a) Keine. Bei jedem i ist pWerte[j] > merker sofort falsch, die innere Schleife läuft null Mal. Es bleiben nur die n − 1 Vergleiche der äußeren Schleife. Das ist linearer Aufwand.
b) Jedes Element muss durch den ganzen sortierten Teil wandern: 1 + 2 + … + (n − 1) Verschiebungen, also wieder n·(n−1)/2. Quadratisch.
c) Bei fast sortierten Daten sind Sortieren durch Einfügen und Bubblesort beide gut, Sortieren durch Auswählen nicht – letzteres macht immer gleich viele Vergleiche, ganz gleich wie die Daten liegen.
In der Praxis wird Sortieren durch Einfügen tatsächlich noch eingesetzt: Viele professionelle Sortierbibliotheken schalten für kleine oder fast sortierte Teilstücke darauf um.
Aufgabe: Selbst implementieren
Ergänze die Methoden so, dass alle Tests grün werden.
Tipp 1: fuegeEin
Fang bei pBis an und wandere nach links, solange dort ein Wert steht, der größer als pWert ist. Schiebe ihn jeweils eine Stelle nach rechts.
Denk an die Absicherung j >= 0 vor dem Vergleich.
Tipp 2: sortiere mit fuegeEin
for (int i = 1; i < pWerte.length; i++) {
fuegeEin(pWerte, i - 1, pWerte[i]);
}Der einzufügende Wert ist pWerte[i], der sortierte Bereich reicht bis i - 1.
Tipp 3: Verschiebungen zählen
Für sortiereUndZaehle brauchst du die Schleife noch einmal ausgeschrieben – oder du gibst aus fuegeEin die Anzahl der Verschiebungen zurück und summierst sie auf. Der zweite Weg ist der schönere.
Die drei Verfahren im Überblick
| Auswählen | Bubblesort | Einfügen | |
|---|---|---|---|
| Vergleiche, bester Fall | n·(n−1)/2 | n − 1 | n − 1 |
| Vergleiche, schlechtester Fall | n·(n−1)/2 | n·(n−1)/2 | n·(n−1)/2 |
| Vertauschungen bzw. Verschiebungen, schlechtester Fall | n − 1 | n·(n−1)/2 | n·(n−1)/2 |
| erkennt sortierte Daten | nein | ja | ja |
| Grundidee | Minimum suchen und nach vorne tauschen | Nachbarn tauschen | an die richtige Stelle einfügen |
Alle drei sind im schlechtesten Fall quadratisch. Verfahren, die deutlich besser sind, lernst du im Lernpfad Erweiterungen kennen – sie brauchen dafür eine neue Problemlösestrategie.
Zusatzaufgabe
Bei den drei Verfahren wurde immer aufsteigend sortiert. Was müsstest du jeweils ändern, um absteigend zu sortieren?
a) Ändere alle drei Verfahren entsprechend.
b) Wie wenige Zeichen musst du bei jedem Verfahren ändern? Bei welchem am wenigsten?
c) Schlage vor, wie man ein Verfahren so schreiben könnte, dass es die Sortierrichtung als Parameter bekommt.