Sortieren durch Auswählen
Sortieren ist das zweite große Grundproblem der Informatik. Es gibt dafür Dutzende Verfahren – wir sehen uns drei an, die alle mit denselben Mitteln auskommen, die du längst kennst.
Erst mit Karten, dann am Rechner
Legt euch fünf Spielkarten mit den Werten 5, 2, 4, 1, 8 in dieser Reihenfolge hin.
Sortiert sie aufsteigend – aber nur nach diesen Regeln:
- Ihr dürft immer nur zwei Karten gleichzeitig anschauen.
- Ihr dürft nur zwei Karten miteinander vertauschen.
- Ihr dürft die Karten nicht anderswo ablegen.
Notiert die Reihenfolge eurer Schritte. Vergleicht sie danach mit denen der anderen Gruppen.
Wahrscheinlich habt ihr eines von zwei Verfahren erfunden. Beide schauen wir uns an – dieses hier zuerst.
Die Idee
Sortieren durch Auswählen (englisch selection sort, auch Minsort):
Suche im unsortierten Rest das kleinste Element und tausche es an die vorderste Stelle dieses Restes. Der sortierte Bereich vorne wächst dabei um eins. Wiederhole das, bis nur noch ein Element übrig ist.
Der Ablauf mit den Karten 5 2 4 1 8:
| Durchlauf | Feld vorher | kleinstes im Rest | Tausch | Feld nachher |
|---|---|---|---|---|
| 1 | 5 2 4 1 8 |
1 (Index 3) | Index 0 ↔ 3 | 1 2 4 5 8 |
| 2 | 1 2 4 5 8 |
2 (Index 1) | Index 1 ↔ 1 | 1 2 4 5 8 |
| 3 | 1 2 4 5 8 |
4 (Index 2) | Index 2 ↔ 2 | 1 2 4 5 8 |
| 4 | 1 2 4 5 8 |
5 (Index 3) | Index 3 ↔ 3 | 1 2 4 5 8 |
Der senkrechte Strich, den man sich zwischen sortiertem und unsortiertem Teil denkt, wandert bei jedem Durchlauf um eine Stelle nach rechts.
Führe das Verfahren auf Papier an dem Feld 3 7 1 9 4 durch. Notiere nach jedem Durchlauf den Zustand.
Wie viele Durchläufe brauchst du? Wie viele Vertauschungen?
Auflösung
| Durchlauf | Feld | kleinstes im Rest | Tausch |
|---|---|---|---|
| Start | 3 7 1 9 4 |
||
| 1 | 1 7 3 9 4 |
1 (Index 2) | 0 ↔ 2 |
| 2 | 1 3 7 9 4 |
3 (Index 2) | 1 ↔ 2 |
| 3 | 1 3 4 9 7 |
4 (Index 4) | 2 ↔ 4 |
| 4 | 1 3 4 7 9 |
7 (Index 4) | 3 ↔ 4 |
Vier Durchläufe – bei fünf Elementen immer n - 1. Hier vier echte Vertauschungen.
Als Struktogramm
┌────────────────────────────────────────────────────────┐
│ für i von 0 bis n - 2 │
│ ┌──────────────────────────────────────────────────┐ │
│ │ kleinstesIndex ← i │ │
│ ├──────────────────────────────────────────────────┤ │
│ │ für j von i + 1 bis n - 1 │ │
│ │ ┌────────────────────────────────────────────┐ │ │
│ │ │ werte[j] < werte[kleinstesIndex] │ │ │
│ │ │ ja ╱────────────────╲ nein │ │ │
│ │ ├───────────────────────────┬────────────────┤ │ │
│ │ │ kleinstesIndex ← j │ ∅ │ │ │
│ │ └───────────────────────────┴────────────────┘ │ │
│ ├──────────────────────────────────────────────────┤ │
│ │ tausche werte[i] und werte[kleinstesIndex] │ │
│ └──────────────────────────────────────────────────┘ │
└────────────────────────────────────────────────────────┘Die innere Schleife ist die Suche nach dem Minimum – das Muster aus Kapitel 5, nur auf einen Teilbereich angewendet. Die äußere Schleife schiebt den Trennstrich nach rechts.
In Java
Sieh dem Verfahren zu: Ergänze am Ende der äußeren Schleife die Zeile
IO.println("nach Durchlauf " + i + ": " + alsText(pWerte));Vergleiche die Ausgabe mit deiner Handrechnung von oben.
Wie viele Vergleiche?
Zähle ohne Rechner, wie viele Vergleiche das Verfahren bei einem Feld mit n Elementen macht.
a) Wie oft läuft die innere Schleife im ersten Durchlauf? Im zweiten? Im letzten?
b) Bilde die Summe für n = 5.
c) Finde eine Formel für beliebiges n.
Tipp
Im ersten Durchlauf vergleicht die innere Schleife n - 1 mal, im zweiten n - 2 mal, und so weiter bis 1.
Gesucht ist also die Summe 1 + 2 + … + (n − 1). Die Formel dafür kennst du aus dem Matheunterricht.
Auflösung
a) Im ersten Durchlauf n - 1 Vergleiche, im zweiten n - 2, …, im letzten genau 1.
b) Bei n = 5: 4 + 3 + 2 + 1 = 10 Vergleiche.
c) Die Summe 1 + 2 + … + (n − 1) beträgt
Für n = 5 ergibt das 5 · 4 / 2 = 10. ✓
Der entscheidende Punkt: Ausmultipliziert steht dort n²/2 − n/2. Für große n ist der n²-Anteil das, was zählt. Verdoppelt sich die Anzahl der Elemente, vervierfacht sich der Aufwand.
| n | Vergleiche |
|---|---|
| 10 | 45 |
| 100 | 4 950 |
| 1 000 | 499 500 |
| 10 000 | 49 995 000 |
Man sagt: Das Verfahren hat quadratischen Aufwand.
Ein Bild dafür: Zeichne ein Quadrat aus n mal n Feldern. Die Vergleiche des Verfahrens sind genau die Felder unterhalb der Diagonalen – etwas weniger als die Hälfte des Quadrats.
Deshalb quadratisch: Verdoppelt sich die Seitenlänge, vervierfacht sich die Fläche.
Aufgabe: Selbst implementieren
Ergänze die Methoden so, dass alle Tests grün werden.
Tipp 1: Baue von unten nach oben
Fang mit tausche an – die kennst du aus Kapitel 5. Dann indexDesKleinsten. Erst wenn beide grün sind, schreibst du sortiere und benutzt darin die beiden fertigen Methoden.
So bleibt jede Methode kurz und du weißt bei einem Fehler sofort, wo er steckt.
Tipp 2: indexDesKleinsten
Die Extremwertsuche aus Kapitel 5, nur mit zwei Änderungen: Sie sucht das kleinste statt des größten Wertes, und sie beginnt bei pVon statt bei 0.
Und sie liefert den Index, nicht den Wert.
Tipp 3: Warum läuft die äußere Schleife nur bis length - 2?
Wenn nur noch ein Element unsortiert ist, ist es automatisch das größte – da gibt es nichts mehr zu tun. Der letzte Durchlauf wäre wirkungslos.
Mit length - 1 als Grenze wäre das Ergebnis genauso richtig, nur ein Durchlauf länger.
Zusatzaufgabe
Baue eine Visualisierung des Verfahrens mit Scratch for Java:
- Stelle die Werte als Säulen dar.
- Färbe in jedem Durchlauf den bereits sortierten Bereich grün.
- Färbe die gerade betrachtete Säule gelb und die bisher kleinste rot.
- Nutze
SystemTools.pause(100), damit man dem Verfahren zusehen kann.
Setze speed hier nicht hoch – langsam ist der Sinn der Sache.