Insertionsort und Selectionsort

Code in:JavaC#PythonJavaScript

Kurz gesagt: Insertionsort fügt jedes Element an seinen Platz im sortierten Teil ein und ist bei fast sortierter Eingabe schnell, während Selectionsort das kleinste wählt und immer etwa n²/2 Vergleiche macht.

Problem

Die langsame Produktseite

Der Shop sortiert die Bestellungen des Tages nach Lieferzeit, und die Admin-Seite zeigt alle Produkte nach Preis. An beiden Stellen steht derselbe alte Code:

static void selectionSort(String[] times) {
    for (int i = 0; i < times.length - 1; i++) {
        int best = i;
        for (int j = i + 1; j < times.length; j++) {
            if (times[j].compareTo(times[best]) < 0) {
                best = j;
            }
        }
        if (best != i) {
            String earlier = times[best];
            times[best] = times[i];
            times[i] = earlier;
        }
    }
}

String[] today = {"14:30", "09:15", "11:00", "16:45", "10:30", "08:45"};
selectionSort(today);
System.out.println(String.join(" ", today));

Ausgabe

08:45 09:15 10:30 11:00 14:30 16:45

Bei sechs Bestellungen geht es sofort. Aber es gibt 50.000 Produkte, und die Seite braucht Sekunden zum Öffnen. Der Code findet das kleinste Element im ganzen Rest, setzt es nach vorn und wiederholt das. Bei 50.000 Elementen sind das 49.999 + 49.998 + … + 1 = 1.249.975.000 Vergleiche. Jedes Mal, auch wenn die Produkte schon sortiert sind und nur zwei vertauscht wurden.

Diese Lektion hat die zwei grundlegenden Sortieralgorithmen: diesen, den Selectionsort, und den Insertionsort. Du zählst sie Vergleich für Vergleich und siehst, wo welcher passt.

Die Idee

Insertionsort: wie Karten in der Hand

So sortierst du Karten in der Hand. Du nimmst die nächste Karte und schiebst sie nach links, an den größeren vorbei, bis sie eine kleinere erreicht. Die Karten links von ihr sind immer sortiert.

static void insertionSort(String[] times) {
    for (int i = 1; i < times.length; i++) {
        String key = times[i];
        int j = i - 1;
        while (j >= 0 && times[j].compareTo(key) > 0) {
            times[j + 1] = times[j];
            j--;
        }
        times[j + 1] = key;
    }
}

key ist die Bestellung, die an ihren Platz kommt. j beginnt bei der Bestellung links davon. Solange die Bestellung bei j später ist als key, rückt sie einen Platz nach rechts und j sinkt. Wo die Schleife anhält, ist bei j + 1 eine Lücke, und key kommt dorthin.

In Java vergleicht man Strings nicht mit >. times[j].compareTo(key) > 0 heißt „times[j] kommt nach key“. Die Uhrzeiten haben eine führende Null (09:15), also ist die Reihenfolge des Textes die Reihenfolge der Zeit.

String[] today = {"14:30", "09:15", "11:00", "16:45", "10:30", "08:45"};
insertionSort(today);
System.out.println(String.join(" ", today));

Ausgabe

08:45 09:15 10:30 11:00 14:30 16:45

Sieh es dir an

Die Karten an ihrem Platz

static void insertionSort(String[] times) {
    for (int i = 1; i < times.length; i++) {
        String key = times[i];
        int j = i - 1;
        while (j >= 0 && times[j].compareTo(key) > 0) {
            times[j + 1] = times[j];
            j--;
        }
        times[j + 1] = key;
    }
}

Schritt für Schritt, in Worten

1. 6 Bestellungen nach Lieferzeit. Links wächst der sortierte Teil: Am Anfang ist es nur die erste Bestellung, 14:30.
2. key = 09:15. 1 spätere Bestellung rückt einen Platz nach rechts, bis ganz an den Anfang, und 09:15 kommt auf Platz 0. 1 Vergleich.
3. key = 11:00. 1 spätere Bestellung rückt einen Platz nach rechts, bis 09:15, und 11:00 kommt auf Platz 1. 2 Vergleiche.
4. key = 16:45. 14:30 ist nicht später: Nichts bewegt sich, und 16:45 kommt auf Platz 3. 1 Vergleich.
5. key = 10:30. 3 spätere Bestellungen rücken einen Platz nach rechts, bis 09:15, und 10:30 kommt auf Platz 1. 4 Vergleiche.
6. key = 08:45. 5 spätere Bestellungen rücken einen Platz nach rechts, bis ganz an den Anfang, und 08:45 kommt auf Platz 0. 5 Vergleiche.
7. Sortiert: 13 Vergleiche und 10 Verschiebungen. Die fast sortierte Liste des Tages braucht nur 6 Vergleiche und 1 Verschiebung.

Jede Karte leistet so viel Arbeit, wie im sortierten Teil vor ihr spätere Karten liegen. 16:45 kommt nach allen und bewegt nichts. 08:45 ist früher als alle und bewegt alle fünf.

Probier es aus

Zähle mit

Derselbe Insertionsort, aber jeder Vergleich und jede Verschiebung wird gezählt. Zuerst bei den Bestellungen aus der Szene, dann bei einer fast sortierten Liste: Eine Bestellung kam etwas nach der nächsten an.

static void insertionSort(String[] times) {
    int comparisons = 0;
    int shifts = 0;
    for (int i = 1; i < times.length; i++) {
        String key = times[i];
        int j = i - 1;
        while (j >= 0) {
            comparisons++;
            if (times[j].compareTo(key) <= 0) {
                break;
            }
            times[j + 1] = times[j];
            shifts++;
            j--;
        }
        times[j + 1] = key;
    }
    System.out.println("Vergleiche: " + comparisons + ", Verschiebungen: " + shifts);
}

String[] today = {"14:30", "09:15", "11:00", "16:45", "10:30", "08:45"};
insertionSort(today);
System.out.println(String.join(" ", today));

String[] almost = {"08:45", "09:15", "11:00", "10:30", "14:30", "16:45"};
insertionSort(almost);

Ausgabe

Vergleiche: 13, Verschiebungen: 10
08:45 09:15 10:30 11:00 14:30 16:45
Vergleiche: 6, Verschiebungen: 1

Der Unterschied kommt davon, wann die innere Schleife aufhört. Ist die Bestellung schon nach allem links von ihr, reicht ein Vergleich. Also:

• der beste Fall ist eine sortierte Liste: n - 1 Vergleiche, null Verschiebungen. O(n);
• der schlechteste Fall ist eine umgekehrte Liste: Jede Bestellung wandert auf Platz 0, n(n - 1)/2 Vergleiche und ebenso viele Verschiebungen. O(n²);
• bei zufälliger Eingabe wandert jede Bestellung im Durchschnitt durch die Hälfte des sortierten Teils: etwa n²/4. Immer noch O(n²).

Die fast sortierte Liste liegt nahe am besten Fall: Jede falsch stehende Bestellung kostet einen Vergleich oder zwei mehr.

Probier es aus

Sage die Ausgabe voraus

Die Bestellungen sind schon sortiert. Was gibt der zählende Insertionsort aus?

String[] today = {"08:45", "09:15", "10:30", "11:00", "14:30", "16:45"};
insertionSort(today);

Antwort

Vergleiche: 15, Verschiebungen: 0

Vergleiche: 0, Verschiebungen: 0

Vergleiche: 5, Verschiebungen: 0

Prüfen

Die Idee

Selectionsort: wähle die früheste

Der alte Code vom Anfang macht etwas anderes. Für Platz i schaut er den ganzen Rest an, findet die früheste Bestellung (ihr Index ist best: die bisher beste) und tauscht sie mit der Bestellung bei i. Danach wird Platz i nicht mehr angefasst.

static void selectionSort(String[] times) {
    for (int i = 0; i < times.length - 1; i++) {
        int best = i;
        for (int j = i + 1; j < times.length; j++) {
            if (times[j].compareTo(times[best]) < 0) {
                best = j;
            }
        }
        if (best != i) {
            String earlier = times[best];
            times[best] = times[i];
            times[i] = earlier;
        }
    }
}

Schritt für Schritt, in Worten

1. Dieselben 6 Bestellungen. Selectionsort geht alles noch Unsortierte durch, findet die früheste Bestellung und setzt sie nach vorn.
2. i = 0: 5 Vergleiche über den Rest. Die früheste ist 08:45, und sie tauscht den Platz mit 14:30.
3. i = 1: 4 Vergleiche über den Rest. Die früheste ist 09:15, und sie steht schon an ihrem Platz: kein Tausch.
4. i = 2: 3 Vergleiche über den Rest. Die früheste ist 10:30, und sie tauscht den Platz mit 11:00.
5. i = 3: 2 Vergleiche über den Rest. Die früheste ist 11:00, und sie tauscht den Platz mit 16:45.
6. i = 4: 1 Vergleich über den Rest. Die früheste ist 14:30, und sie tauscht den Platz mit 16:45.
7. 15 Vergleiche und 4 Tausche. Die Vergleiche sind immer n(n − 1)/2 = 15: Auch die fast sortierte Liste braucht 15, mit 1 Tausch.

static void selectionSort(String[] times) {
    int comparisons = 0;
    int swaps = 0;
    for (int i = 0; i < times.length - 1; i++) {
        int best = i;
        for (int j = i + 1; j < times.length; j++) {
            comparisons++;
            if (times[j].compareTo(times[best]) < 0) {
                best = j;
            }
        }
        if (best != i) {
            String earlier = times[best];
            times[best] = times[i];
            times[i] = earlier;
            swaps++;
        }
    }
    System.out.println("Vergleiche: " + comparisons + ", Tausche: " + swaps);
}

String[] today = {"14:30", "09:15", "11:00", "16:45", "10:30", "08:45"};
selectionSort(today);
System.out.println(String.join(" ", today));

String[] almost = {"08:45", "09:15", "11:00", "10:30", "14:30", "16:45"};
selectionSort(almost);

Ausgabe

Vergleiche: 15, Tausche: 4
08:45 09:15 10:30 11:00 14:30 16:45
Vergleiche: 15, Tausche: 1

Beide Listen brauchen 15 Vergleiche: Um sicher zu sein, dass er die früheste gefunden hat, schaut Selectionsort jedes Mal den ganzen Rest an. Bei n Bestellungen sind das (n - 1) + (n - 2) + … + 1 = n(n - 1)/2 Vergleiche bei jeder Eingabe. Einen besseren Fall gibt es nicht.

Seine Stärke liegt woanders: Es gibt höchstens n - 1 Tausche, einen pro Platz. Insertionsort verschiebt bis zu n²/2-mal. Ist das Vergleichen billig und das Bewegen teuer (große Datensätze, die kopiert werden, oder Schreibvorgänge in Flash-Speicher, der verschleißt), zählen die wenigen Tausche.

Sieh es dir an

Miss es

Die Operation ist ein Vergleich zweier Elemente. Insertionsort läuft mit drei Eingaben: zufällig, fast sortiert (sortiert, dann n/20 benachbarte Paare vertauscht) und umgekehrt. Selectionsort läuft nur mit zufälliger Eingabe, weil er bei jeder Eingabe dasselbe tut.

• Insertion Sort, zufällige Eingabe O(n²)
• Insertion Sort, fast sortierte Eingabe O(n)
• Insertion Sort, umgekehrte Eingabe O(n²)
• Selection Sort, zufällige Eingabe O(n²)

Algorithmus	n = 10	n = 100	n = 1.000	n = 10.000	n = 100.000
Insertion Sort, zufällige Eingabe	37	2.481	254.808	25.057.917	≈ 2.505.791.700
Insertion Sort, fast sortierte Eingabe	9	104	1.049	10.474	104.755
Insertion Sort, umgekehrte Eingabe	45	4.950	499.500	49.995.000	≈ 4.999.500.000
Selection Sort, zufällige Eingabe	45	4.950	499.500	49.995.000	≈ 4.999.500.000

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

static void insertionSort(String[] times) {
    for (int i = 1; i < times.length; i++) {
        String key = times[i];
        int j = i - 1;
        while (j >= 0 && times[j].compareTo(key) > 0) {
            times[j + 1] = times[j];
            j--;
        }
        times[j + 1] = key;
    }
}

Bei 1000 Elementen: zufällige Eingabe 254.808, fast sortiert 1049, umgekehrt 499.500, und Selectionsort 499.500 bei jeder Eingabe. Bei 100.000 läuft nur die fast sortierte: Die anderen würden Milliarden Vergleiche machen. Die Seite mit 50.000 Produkten liegt dazwischen: über eine Milliarde Vergleiche mit Selectionsort.

Probier es aus

Finde den Fehler

Diese Version lässt eine Bestellung an der falschen Stelle:

String[] today = {"14:30", "09:15", "11:00", "16:45", "10:30", "08:45"};
insertionSort(today);
System.out.println(String.join(" ", today));

Ausgabe

14:30 08:45 09:15 10:30 11:00 16:45

Wähle die Zeile mit dem Fehler.

1static void insertionSort(String[] times) {2 for (int i = 1; i < times.length; i++) {3 String key = times[i];4 int j = i - 1;5 while (j > 0 && times[j].compareTo(key) > 0) {6 times[j + 1] = times[j];7 j--;8 }9 times[j + 1] = key;10 }11}

Prüfen

Probier es aus

Bring die Zeilen in die richtige Reihenfolge

Das ist der Rumpf der äußeren Schleife des Insertionsort. Bring ihn in die richtige Reihenfolge.

1. times[j + 1] = key;↑↓
2. j--;↑↓
3. times[j + 1] = times[j];↑↓
4. String key = times[i];↑↓
5. while (j >= 0 && times[j].compareTo(key) > 0) {↑↓
6. }↑↓
7. int j = i - 1;↑↓

Prüfen

Die Idee

Wo man sie einsetzt

Sie sind bei vielen Elementen langsam, aber nicht nur zum Lernen da. Insertionsort ist für kleine Arrays und für fast sortierte am schnellsten: keine Rekursion, kein zusätzlicher Speicher, und seine innere Schleife ist kurz.

Deshalb nutzen eingebaute Sortierfunktionen ihn im Inneren:

Genauer, für Neugierige

• Java. Arrays.sort für Objekte und Collections.sort sind TimSort: Er sucht in den Daten nach schon sortierten Läufen und verlängert die kurzen mit binärem Insertionsort, bis zu etwa 32 Elementen. Arrays.sort für Zahlen ist Dual-Pivot-Quicksort, der die kleinen Teile mit Insertionsort sortiert.
• C#. Array.Sort und List<T>.Sort sind Introsort: ein Quicksort, der bei Teilen bis 16 Elemente auf Insertionsort umschaltet.
• Python. list.sort() und sorted() sind TimSort (seit 3.11 mit der Powersort-Mergeregel), und auch sie verlängern kurze Läufe mit binärem Insertionsort.
• JavaScript. In V8 (Chrome, Node.js) ist Array.prototype.sort seit 2018 TimSort, mit demselben binären Insertionsort für kurze Läufe.

Binärer Insertionsort findet den Platz von key mit binärer Suche, nicht einzeln. Die Vergleiche werden zu etwa n log n, aber die Verschiebungen bleiben gleich.

Große Arrays brauchen O(n log n)-Algorithmen. Der erste ist Mergesort.

Übung

Die größten Bestellungen nach oben

Löse die Aufgabe in deinem eigenen Editor.

Nach Summe, größte zuerst. Der Tagesbericht zeigt die Bestellungen nach Summe, von der größten zur kleinsten. Schreibe sortByTotalDescending(int[] totals) mit Insertionsort und sortiere Bestellungen zu 46 €, 13 €, 89 €, 23 € und 67 €. Die Ausgabe ist:

Ausgabe

89 €
67 €
46 €
23 €
13 €

Weitere Aufgaben

• Selectionsort von hinten. Schreibe einen Selectionsort, der jedes Mal die späteste Bestellung findet und sie ans Ende des unsortierten Teils setzt. Zähle die Vergleiche: Sind es immer noch n(n - 1)/2?
• Verschiebungen gegen Tausche. Lass die zählenden Versionen auf einer umgekehrten Liste mit 10 Bestellungen laufen. Wie viele Verschiebungen macht Insertionsort, und wie viele Tausche macht Selectionsort?
• Binärer Insertionsort. Finde den Platz von key im sortierten Teil mit binärer Suche, dann verschiebe. Wie viele Vergleiche macht er bei 1000 zufälligen Bestellungen?

Test

Teste dich

1. Die Bestellliste ist schon nach Uhrzeit sortiert, nur zwei Nachbarn sind vertauscht. Welcher Algorithmus ist schneller fertig?

Gleich schnell: Beide sind O(n²)Selectionsort: Er macht die wenigsten TauscheInsertionsort: Fast jede Bestellung wird einmal verglichen und bleibt

2. Wie viele Vergleiche macht Selectionsort bei 1000 Bestellungen?

499.500, bei jeder EingabeEtwa 10.000Etwa 1000, wenn sie sortiert sind

3. Wann ist Selectionsort die bessere Wahl?

Wenn es eine Million Elemente gibtWenn jedes Schreiben auf einen Platz teuer ist: Er macht höchstens n - 1 TauscheWenn die Liste fast sortiert ist

4. Was macht Insertionsort mit einer Bestellung, die früher ist als alles im sortierten Teil?

Tauscht sie mit der erstenLässt sie am EndeVerschiebt alle um einen Platz nach rechts und setzt sie auf Platz 0

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Parameter und return · Zeitkomplexität: Schritte zählen · Big-O: wie die Arbeit wächst · Bester, durchschnittlicher und schlechtester Fall
• Geht weiter in: Mergesort und „Teile und herrsche“ · Quicksort und der schlechte Pivot · Stabiles Sortieren und die eingebaute Sortierung · Teile und herrsche und der Rekursionsbaum
• Aufgaben zum Thema: Sortieren