Zum Inhalt springen
Zurück zur Themenübersicht

Praktische Informatik

Sortieralgorithmen: von der Auswahl zum Teilen und Herrschen

Drei einfache Verfahren, ein schnelles, und der Beweis, dass es durch bloßes Vergleichen nicht schneller geht.

Benötigte Grundlagen

Dieses Vorwissen brauchst du für das Kapitel. Schau kurz nach, wenn dir etwas davon nicht mehr präsent ist, sonst leg direkt los.

Einführung

Sortieren wirkt wie eine Fingerübung. Tatsächlich ist es eines der am gründlichsten untersuchten Probleme der Informatik, und der Grund steht im vorigen Kapitel: Sortierte lassen sich binär durchsuchen, und das entscheidet über Sekunden oder Stunden.

Dieses Kapitel zeigt drei einfache Verfahren, die alle O(n2)O(n^2) brauchen, und dann eines mit O(nlog⁡n)O(n \log n). Bei einer Million Einträgen ist das der Unterschied zwischen elf Tagen und einer Sekunde.

Am Ende steht eine Frage, die man selten stellt: Geht es noch besser? Die Antwort ist nein, und sie ist beweisbar.

Das kannst du nach diesem Kapitel

  • Sortieren durch Auswahl und durch Einfügen beschreiben und durchführen.

  • den Aufwand dieser Verfahren begründen, nicht nur nennen.

  • das Prinzip Teile und herrsche am Sortieren durch Mischen erläutern (Vertiefung).

  • Verfahren nach Aufwand, Stabilität und Speicherbedarf vergleichen.

  • begründen, warum vergleichendes Sortieren nicht schneller als O(nlog⁡n)O(n \log n) sein kann (Vertiefung).

Kurz aufgefrischt

Vorausgesetzt werden geschachtelte aus Algorithmen entwerfen, die aus Aufwand von Algorithmen und das Feld aus Datentypen und Datenstrukturen.

Sortieren durch Auswahl

Die Idee ist die, mit der man von Hand Karten ordnet: Man sucht die kleinste Karte, legt sie nach vorn, sucht die kleinste der übrigen, und so weiter.

für i von 0 bis n-2:
    kleinstesIndex = i
    für j von i+1 bis n-1:
        wenn a[j] < a[kleinstesIndex]:
            kleinstesIndex = j
    vertausche a[i] und a[kleinstesIndex]

Warum O(n2)O(n^2)? Die äußere läuft n−1n-1-mal. Die innere durchsucht beim ersten Mal n−1n-1 Elemente, dann n−2n-2, dann n−3n-3 und so weiter. Zusammen:

(n−1)+(n−2)+…+1=n(n−1)2≈n22(n-1) + (n-2) + \ldots + 1 = \frac{n(n-1)}{2} \approx \frac{n^2}{2}

Das ist O(n2)O(n^2). Bemerkenswert: Die Zahl der Vergleiche hängt gar nicht von den ab. Ob das Feld bereits sortiert ist oder völlig durcheinander, es werden immer gleich viele Vergleiche ausgeführt. Bester, mittlerer und schlechtester Fall sind identisch.

Dafür ist die Zahl der Vertauschungen minimal, nämlich höchstens n−1n-1. Das ist der einzige echte Vorteil des Verfahrens: Wenn das Umlagern der Elemente sehr teuer ist, etwa bei großen Datensätzen, zählt das.

Sortieren durch Auswahl

Start529171. Durchgang129572. Durchgang129573. Durchgang125974. Durchgang12579Vier Durchgänge, aber nur dreiVertauschungen, der zweitetauscht mit sich selbst.

Lies das Bild von oben nach unten: Jeder Durchgang sucht den kleinsten der noch nicht eingefärbten Werte und holt ihn an den Anfang. Der eingefärbte Bereich wächst dadurch von links, und was einmal darin steht, steht endgültig. 🔴 Sieh dir den zweiten Durchgang genau an: Dort ändert sich nichts, weil die 2 schon an ihrem Platz stand. Trotzdem hat das Verfahren alle Werte dahinter durchgesehen. Es konnte ja vorher nicht wissen, dass keiner kleiner ist. Genau das ist die Eigenart des Verfahrens: Die Zahl der Vergleiche hängt gar nicht von den ab. Bester, mittlerer und schlechtester Fall sind identisch, immer n(n−1)2\tfrac{n(n-1)}{2} Vergleiche. Dafür wird höchstens n−1n-1-mal vertauscht, und wenn das Umlagern teuer ist, ist das der Vorteil, für den man alles andere in Kauf nimmt.

Sortieren durch Einfügen

Die Idee ist die, mit der man ein Blatt Karten sortiert, das man nacheinander aufnimmt: Jede neue Karte wird an der richtigen Stelle in den bereits sortierten Teil eingeschoben.

für i von 1 bis n-1:
    wert = a[i]
    j = i - 1
    solange j ≥ 0 und a[j] > wert:
        a[j+1] = a[j]          // nach rechts schieben
        j = j - 1
    a[j+1] = wert

Der Bereich links von ii ist dabei immer schon sortiert. Man nennt eine solche Aussage, die während der ganzen gilt, eine Invariante; sie ist der Kern jeder Begründung, dass ein Verfahren wirklich sortiert.

Aufwand: Im schlechtesten Fall (absteigend sortiert) muss jedes Element ganz nach vorn geschoben werden, also wieder etwa n2/2n^2/2 Schritte, damit O(n2)O(n^2).

Im besten Fall aber, wenn das Feld bereits sortiert ist, bricht die innere Schleife sofort ab, und es bleiben n−1n-1 Vergleiche, also O(n)O(n). Genau das unterscheidet dieses Verfahren vom Sortieren durch Auswahl: Es profitiert von Vorsortierung.

Deshalb ist es bei kleinen oder fast sortierten Feldern das Verfahren der Wahl, und deshalb schalten gute Sortierbibliotheken bei kurzen Teilstücken darauf um.

Sortieren durch Einfügen

Start529171. Durchgang259172. Durchgang259173. Durchgang125974. Durchgang12579Dieselbe Ausgangsfolge wie oben,vergleiche, wie viele Zellen sichje Durchgang ändern.

Dieselben fünf Zahlen, ein anderer Gedanke: Jeder Durchgang nimmt den nächsten Wert und schiebt ihn an die richtige Stelle des schon sortierten Anfangs. 🔴 Und jetzt vergleiche mit dem Bild darüber. Beim Auswählen ändern sich je Durchgang genau zwei Zellen, nämlich die getauschten. Hier ändern sich im dritten Durchgang vier, die 1 muss ganz nach vorn, und alles davor rückt einen Platz nach rechts. Das Verschieben ist die Arbeit dieses Verfahrens, und darum steht es im schlechtesten Fall (absteigend sortiert) wieder bei O(n2)O(n^2). Dafür bekommt es etwas, das das Auswählen nicht hat: Ist das Feld schon fast sortiert, bricht die innere sofort ab und es bleiben n−1n-1 Vergleiche, also O(n)O(n). Deshalb schalten gute Sortierbibliotheken bei kurzen Teilstücken genau hierauf um.

Sortieren durch Vertauschen

Beim Sortieren durch Vertauschen (Bubblesort) vergleicht man wiederholt benachbarte Elemente und tauscht sie, wenn sie in falscher Reihenfolge stehen. Nach dem ersten Durchlauf steht das größte Element ganz hinten, nach dem zweiten das zweitgrößte, und so weiter.

Auch das ist O(n2)O(n^2). Das Verfahren ist in der Praxis das langsamste der drei, weil es sehr viele Vertauschungen ausführt; es wird fast nur zu Lehrzwecken benutzt, weil sein Ablauf besonders anschaulich ist.

Vertiefung: Sortieren durch Mischen

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Alle drei bisherigen Verfahren haben denselben Aufbau: eine in einer Schleife. Daraus folgt O(n2)O(n^2), und daran ändert kein Detailtrick etwas. Für einen echten Fortschritt braucht es eine andere Idee.

Die Idee heißt Teile und herrsche:

Teilen: Das Problem in kleinere gleichartige Teilprobleme zerlegen. Herrschen: Die Teile auf dieselbe Weise lösen. Zusammenfügen: Die Teillösungen verbinden.

Beim Sortieren durch Mischen (Mergesort) heißt das:

sortiere(Feld):
    wenn Länge ≤ 1: fertig                    // Abbruch
    teile das Feld in zwei Hälften
    sortiere(linke Hälfte)                    // Rekursion
    sortiere(rechte Hälfte)                   // Rekursion
    mische die beiden sortierten Hälften

Das Mischen zweier bereits sortierter Folgen ist der Kern und erstaunlich einfach: Man vergleicht die beiden vordersten Elemente und nimmt das kleinere. Das wiederholt man, bis beide leer sind.

  [2, 5, 8]   und   [1, 3, 9]

  1 < 2  →  1        Rest: [2,5,8] [3,9]
  2 < 3  →  1,2      Rest: [5,8]   [3,9]
  3 < 5  →  1,2,3    Rest: [5,8]   [9]
  5 < 9  →  1,2,3,5  Rest: [8]     [9]
  8 < 9  →  1,2,3,5,8
  Rest   →  1,2,3,5,8,9

Jedes Element wird dabei genau einmal angefasst, das Mischen kostet also O(n)O(n).

Warum insgesamt O(nlog⁡n)O(n \log n)? Zwei Beobachtungen genügen:

  • Halbieren, bis Stücke der Länge 1 übrig sind, geht log⁡2n\log_2 n-mal. Das ist dieselbe Rechnung wie bei der binären Suche.
  • Auf jeder dieser Ebenen wird zusammen jedes Element einmal gemischt, das kostet je Ebene O(n)O(n).

Zusammen: log⁡2n\log_2 n Ebenen mal O(n)O(n) je Ebene, also O(nlog⁡n)O(n \log n).

Der Vergleich in Zahlen bei n=1 000 000n = 1\,000\,000:

VerfahrenSchritte (Größenordnung)
O(n2)O(n^2)101210^{12}
O(nlog⁡n)O(n \log n)2⋅1072 \cdot 10^7

Ein Faktor von etwa 50 000. Bei einer Million Datensätzen ist das der Unterschied zwischen elf Tagen und einer Sekunde.

Der Preis ist der Speicher: Das Mischen braucht ein zweites Feld, also O(n)O(n) zusätzlichen Platz. Die einfachen Verfahren kommen ohne aus.

Warum Mischen n mal log n kostet

844222211111111

Die Zahl in jedem ist die Länge des Stücks, nicht sein Inhalt, denn genau darauf kommt es beim Aufwand an. Zähle die beiden Größen, aus denen sich alles ergibt. Erstens die Ebenen: von 8 über 4 und 2 bis 1 sind es drei Halbierungen, und log⁡28=3\log_2 8 = 3. Bei einer Million wären es zwanzig. Zweitens jede Ebene für sich: 8=4+4=2+2+2+2=1⋅88 = 4 + 4 = 2+2+2+2 = 1 \cdot 8, auf jeder Ebene stehen zusammen wieder alle acht Elemente, und alle acht werden beim Zusammenmischen genau einmal angefasst. Also kostet jede Ebene O(n)O(n), und es gibt log⁡2n\log_2 n davon: O(nlog⁡n)O(n \log n). 🔴 Der Unterschied zu den drei Verfahren davor liegt nicht im Fleiß, sondern im Bau: Eine in einer Schleife ergibt zwangsläufig n2n^2, ein Baum dieser Form zwangsläufig nlog⁡nn \log n.

Stabilität

Ein Sortierverfahren heißt stabil, wenn es die Reihenfolge gleichwertiger Elemente beibehält.

Das klingt nebensächlich und ist es nicht. Sortiert man eine Liste erst nach Vorname und dann stabil nach Nachname, sind gleiche Nachnamen anschließend nach Vorname geordnet. Bei einem instabilen Verfahren wäre diese Ordnung zerstört, und mehrstufige Sortierungen wären unmöglich.

Verfahrenstabil
Auswahlnein (das Vertauschen über weite Strecken zerreißt die Reihenfolge)
Einfügenja
Vertauschenja
Mischenja

Vertiefung: die untere Schranke

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Geht es noch besser als O(nlog⁡n)O(n \log n)? Für Verfahren, die ausschließlich vergleichen, lautet die Antwort nein, und der Beweis benutzt reines Abzählen.

Es gibt n!n! mögliche Anordnungen von nn Elementen, und genau eine davon ist die sortierte. Ein Verfahren muss also durch seine Vergleiche zwischen n!n! Möglichkeiten unterscheiden können.

Jeder Vergleich hat zwei mögliche Ausgänge, halbiert die Zahl der verbliebenen Möglichkeiten also höchstens. Mit kk Vergleichen lassen sich damit höchstens 2k2^k Fälle unterscheiden. Notwendig ist also

2k≥n!⟺k≥log⁡2(n!)2^k \ge n! \quad \Longleftrightarrow \quad k \ge \log_2(n!)

und log⁡2(n!)\log_2(n!) wächst wie nlog⁡nn \log n.

🔴 Also braucht jedes vergleichende Sortierverfahren mindestens O(nlog⁡n)O(n \log n) Vergleiche. Das Sortieren durch Mischen ist damit nicht nur gut, sondern in der Größenordnung optimal. Wer ein schnelleres vergleichendes Verfahren sucht, sucht etwas beweisbar Nichtexistierendes.

Der Zusatz „vergleichend" ist wesentlich. Verfahren, die zusätzliche Annahmen über die machen, können schneller sein: Weiß man, dass alle Werte ganze Zahlen zwischen 1 und 100 sind, kann man sie einfach in 100 Fächern zählen und ist in O(n)O(n) fertig. Diese Verfahren umgehen die Schranke nicht, sie fallen nicht unter sie, weil sie gar nicht vergleichen.

Warum kein Vergleichsverfahren schneller sein kann

nAnordnungen n!nötig: k ≥log₂(n!)363424551207103 628 80022Jeder Vergleich hat zwei Ausgänge,unterscheidet also höchstens 2 hochk Fälle.

Die Tabelle rechnet den Beweis in Zahlen nach. Ein Sortierverfahren muss am Ende eine von n!n! möglichen Anordnungen herausgefunden haben, bei zehn Elementen also eine von über 3,6 Millionen. Jeder Vergleich liefert genau ein , ja oder nein, und trennt die verbliebenen Möglichkeiten damit höchstens in zwei Hälften. Mit kk Vergleichen sind so höchstens 2k2^k Fälle unterscheidbar, also braucht es 2k≥n!2^k \ge n! und damit k≥log⁡2(n!)k \ge \log_2(n!). Prüfe die dritte Zeile: 26=64<1202^6 = 64 < 120, aber 27=128≥1202^7 = 128 \ge 120, sieben Vergleiche, keiner weniger. 🔴 Und log⁡2(n!)\log_2(n!) wächst wie nlog⁡nn \log n. Das Sortieren durch Mischen ist damit nicht bloß gut, sondern in der Größenordnung optimal: Wer ein schnelleres vergleichendes Verfahren sucht, sucht etwas beweisbar Nichtexistierendes.

Die Übersicht

Verfahrenbester Fallschlechtester FallSpeicherstabil
AuswahlO(n2)O(n^2)O(n2)O(n^2)O(1)O(1)nein
EinfügenO(n)O(n)O(n2)O(n^2)O(1)O(1)ja
VertauschenO(n)O(n)O(n2)O(n^2)O(1)O(1)ja
MischenO(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(n)O(n)ja

Sortieren durch Auswahl von Hand

Sortiere [5,2,9,1,7][5, 2, 9, 1, 7] durch Auswahl. Notiere jeden Durchlauf.

  1. 1

    Durchlauf 1 (i=0i = 0): Kleinstes im Bereich 0–4 ist die 1 an Index 3. Tausche mit Index 0. → [1,2,9,5,7][\mathbf{1}, 2, 9, 5, 7]

  2. 2

    Durchlauf 2 (i=1i = 1): Kleinstes im Bereich 1–4 ist die 2, steht schon an Index 1. Tausch mit sich selbst. → [1,2,9,5,7][1, \mathbf{2}, 9, 5, 7]

  3. 3

    Durchlauf 3 (i=2i = 2): Kleinstes im Bereich 2–4 ist die 5 an Index 3. Tausche mit Index 2. → [1,2,5,9,7][1, 2, \mathbf{5}, 9, 7]

  4. 4

    Durchlauf 4 (i=3i = 3): Kleinstes im Bereich 3–4 ist die 7 an Index 4. Tausche mit Index 3. → [1,2,5,7,9][1, 2, 5, \mathbf{7}, 9]

  5. 5

    Nach vier Durchläufen ist das Feld sortiert. Der letzte Platz braucht keinen eigenen Durchlauf, denn dort steht zwangsläufig das größte übrige Element; deshalb läuft die äußere nur bis n−2n-2.

  6. 6

    Vergleiche gezählt: 4+3+2+1=10=5⋅424 + 3 + 2 + 1 = 10 = \frac{5 \cdot 4}{2}. Genau die Formel aus dem Theorieteil, und diese Zahl fällt bei jedem Ausgangsfeld gleich aus, auch bei einem bereits sortierten.

[1,2,5,7,9][1,2,5,7,9] nach vier Durchläufen mit 10 Vergleichen und höchstens 4 Vertauschungen.

Zwei sortierte Hälften mischen

Mische [1,4,6][1, 4, 6] und [2,3,8][2, 3, 8] zu einer sortierten Folge und bestimme den Aufwand.

  1. 1

    Regel: Immer die beiden vordersten Elemente vergleichen und das kleinere übernehmen.

  2. 2

    Ablauf:

    SchrittlinksrechtsVergleichAusgabe
    1[1,4,6][2,3,8]1<21 < 21
    2[4,6][2,3,8]4>24 > 21,2
    3[4,6][3,8]4>34 > 31,2,3
    4[4,6][8]4<84 < 81,2,3,4
    5[6][8]6<86 < 81,2,3,4,6
    6[][8]links leer1,2,3,4,6,8
  3. 3

    Warum das genügt: Da beide Hälften sortiert sind, ist das kleinste noch nicht ausgegebene Element zwangsläufig eines der beiden vordersten. Man muss also nie weiter hineinschauen.

  4. 4

    Aufwand: Jeder Schritt gibt genau ein Element aus, und insgesamt sind es nn Elemente. Also O(n)O(n) Vergleiche.

  5. 5

    Wichtig für die Stabilität: Bei Gleichstand nimmt man das Element aus der linken Hälfte. Damit bleiben gleichwertige Elemente in ihrer ursprünglichen Reihenfolge, und das Verfahren ist stabil.

  6. 6

    Der Schluss auf O(nlog⁡n)O(n \log n): Dieses Mischen findet auf jeder Halbierungsebene statt, insgesamt kostet jede Ebene O(n)O(n). Da es log⁡2n\log_2 n Ebenen gibt, ergibt sich O(nlog⁡n)O(n \log n).

[1,2,3,4,6,8][1,2,3,4,6,8] in sechs Schritten. Mischen kostet O(n)O(n), weil jedes Element genau einmal angefasst wird.

Typischer Fehler

„Sortieren durch Auswahl ist schneller, wenn das Feld schon fast sortiert ist."

Das gilt für das Sortieren durch Einfügen, nicht für das durch Auswahl, und der Unterschied lohnt genaues Hinsehen.

Beim Sortieren durch Auswahl muss die innere immer den gesamten Restbereich durchsuchen, um das kleinste Element sicher zu finden. Sie kann nicht früher abbrechen, denn das Minimum könnte ganz am Ende stehen. Deshalb sind es immer n(n−1)2\frac{n(n-1)}{2} Vergleiche, ob das Feld bereits sortiert ist oder nicht. Bester und schlechtester Fall sind identisch.

Beim Sortieren durch Einfügen ist das anders. Die innere Schleife bricht ab, sobald ein kleineres Element gefunden wird. In einem bereits sortierten Feld ist das sofort der Fall, also bleibt es bei einem Vergleich je Element und damit O(n)O(n) insgesamt.

Was beim Auswahlverfahren tatsächlich sinkt, ist die Zahl der Vertauschungen: höchstens n−1n-1, unabhängig von den . Das ist sein einziger echter Vorteil, und er zählt nur, wenn das Umlagern der Elemente teuer ist, etwa bei sehr großen Datensätzen.

Die Lehre daraus ist allgemeiner: Man muss unterscheiden, was gezählt wird. Vergleiche und Vertauschungen sind zwei verschiedene Kostenarten, und welche wichtiger ist, hängt von den Daten ab.

Übung 1

leicht

a) Sortiere [4,1,3,2][4, 1, 3, 2] durch Auswahl und notiere jeden Durchlauf. b) Wie viele Vergleiche braucht das Verfahren bei n=6n = 6? c) Welches der behandelten Verfahren wird schneller, wenn das Feld schon fast sortiert ist?

Tipp anzeigen

Zu b): Verwende n(n−1)2\frac{n(n-1)}{2}.

Lösung anzeigen

a) Durchläufe:

[4,1,3,2]→[1,4,3,2]→[1,2,3,4]→[1,2,3,4][4,1,3,2] \to [\mathbf{1},4,3,2] \to [1,\mathbf{2},3,4] \to [1,2,\mathbf{3},4]

Durchlauf 1: Kleinstes ist 1 an Index 1, tausche mit Index 0. Durchlauf 2: Kleinstes im Rest ist 2 an Index 3, tausche mit Index 1. Durchlauf 3: Kleinstes im Rest ist 3, steht schon richtig.

b) 6⋅52=15\frac{6 \cdot 5}{2} = 15 Vergleiche.

c) Sortieren durch Einfügen. Die innere bricht ab, sobald ein kleineres Element gefunden wird; bei einem bereits sortierten Feld ist das sofort der Fall, und es bleiben n−1n-1 Vergleiche, also O(n)O(n).

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    a) Sortieren durch Auswahl: jeden Durchlauf einzeln notieren

    Das Verfahren sucht in jedem Durchlauf das kleinste Element des Restes und tauscht es nach vorn. Durchlauf 1: Kleinstes ist 1 an Index 1, tauschen mit Index 0 → [1,4,3,2][1,4,3,2]. Durchlauf 2: Kleinstes im Rest ist 2 an Index 3, tauschen mit Index 1 → [1,2,3,4][1,2,3,4]. Durchlauf 3: Kleinstes im Rest ist 3, steht schon richtig.

    [4,1,3,2]→[1,4,3,2]→[1,2,3,4]→[1,2,3,4][4,1,3,2] \to [\mathbf{1},4,3,2] \to [1,\mathbf{2},3,4] \to [1,2,\mathbf{3},4]

  2. 2

    b) Die Vergleichszahl über die Summenformel

    Im ersten Durchlauf werden n−1n-1 Elemente verglichen, im zweiten n−2n-2, und so weiter. Die Summe 1+2+…+(n−1)1 + 2 + \ldots + (n-1) ergibt n(n−1)2\frac{n(n-1)}{2}. Für n=6n = 6: 6⋅52=15\frac{6 \cdot 5}{2} = 15 Vergleiche.

    n(n−1)2=6⋅52=15\frac{n(n-1)}{2} = \frac{6 \cdot 5}{2} = 15

    Zwischenergebnis

    15 Vergleiche.

  3. 3

    c) Welches Verfahren von einer Vorsortierung profitiert

    Sortieren durch Einfügen. Seine innere Schleife bricht ab, sobald ein kleineres Element gefunden wird; bei einem bereits sortierten Feld ist das sofort der Fall, und es bleiben n−1n-1 Vergleiche, also O(n)O(n).

Übung 2

mittel

a) Sortiere [7,3,9,2,5][7, 3, 9, 2, 5] durch Einfügen. Notiere den Feldzustand nach jedem eingefügten Element. b) Wie viele Vergleiche braucht dieses Verfahren im besten und im schlechtesten Fall? c) Erkläre, was die Invariante des Verfahrens ist und wozu sie dient. d) Warum ist das Sortieren durch Auswahl nicht stabil? Gib ein Gegenbeispiel.

Tipp anzeigen

Zu d): Betrachte zwei gleiche Werte und ein kleineres Element weiter hinten.

Lösung anzeigen

a) Ablauf, der bereits sortierte Teil ist fett:

Start: [7,3,9,2,5][\mathbf{7}, 3, 9, 2, 5] i=1i=1, Wert 3: vor die 7 → [3,7,9,2,5][\mathbf{3, 7}, 9, 2, 5] i=2i=2, Wert 9: bleibt hinten → [3,7,9,2,5][\mathbf{3, 7, 9}, 2, 5] i=3i=3, Wert 2: ganz nach vorn → [2,3,7,9,5][\mathbf{2, 3, 7, 9}, 5] i=4i=4, Wert 5: zwischen 3 und 7 → [2,3,5,7,9][\mathbf{2, 3, 5, 7, 9}]

b) Bester Fall (schon sortiert): Jedes Element wird genau einmal mit seinem linken Nachbarn verglichen, die innere bricht sofort ab. Das sind n−1n-1 Vergleiche, also O(n)O(n).

Schlechtester Fall (absteigend sortiert): Jedes Element muss bis ganz nach vorn geschoben werden, also 1+2+…+(n−1)=n(n−1)21 + 2 + \ldots + (n-1) = \frac{n(n-1)}{2} Vergleiche, also O(n2)O(n^2).

c) Die Invariante lautet: Nach jedem Durchlauf der äußeren Schleife ist der Bereich von Index 0 bis ii sortiert. Sie gilt vor dem ersten Durchlauf (ein einzelnes Element ist trivialerweise sortiert) und bleibt bei jedem Schritt erhalten, weil das neue Element genau an seine richtige Stelle geschoben wird.

Wozu: Sie ist die Begründung, dass das Verfahren wirklich sortiert. Am Ende ist i=n−1i = n-1, also der gesamte Bereich sortiert. Ohne eine solche Aussage könnte man nur beobachten, dass es in den ausprobierten Fällen funktioniert hat.

d) Betrachte [3a,3b,1][3_a, 3_b, 1], wobei die Kennzeichnungen nur der Unterscheidung dienen.

Durchlauf 1: Kleinstes ist die 1 an Index 2, sie wird mit Index 0 vertauscht → [1,3b,3a][1, 3_b, 3_a].

Die beiden Dreien haben ihre Reihenfolge getauscht: vorher stand 3a3_a vor 3b3_b, jetzt umgekehrt. Das Verfahren ist also nicht stabil. Die Ursache ist das Vertauschen über weite Strecken: Das Element an Position ii wird an eine ganz andere Stelle geworfen, ohne Rücksicht auf gleichwertige Elemente dazwischen.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    Teil a): Den sortierten Teil markieren

    Man schreibt nach jedem Schritt das ganze Feld auf und markiert, welcher Teil bereits sortiert ist. Genau dieser Teil wächst in jedem Durchlauf um eins.

    Zwischenergebnis

    Nach i=3i=3: [2,3,7,9,5][\mathbf{2,3,7,9},5].

    Beachte, dass die 9 in ihrem Durchlauf gar nicht bewegt wird. Die innere Schleife bricht sofort ab, weil links davon ein kleinerer Wert steht.

  2. 2

    Teil b): Beide Extreme konstruieren

    Man überlegt, welche Eingabe die innere Schleife sofort abbrechen lässt und welche sie maximal lange laufen lässt. Das sind das bereits sortierte und das absteigend sortierte Feld.

    1 + 2 + \ldots + (n-1) = \frac{n(n-1)}{2}

    Zwischenergebnis

    O(n)O(n) bester, O(n2)O(n^2) schlechtester Fall.

  3. 3

    Teil c): Was eine Invariante leistet

    Die Invariante ist eine Aussage, die vor und nach jedem Schleifendurchlauf gilt. Hier: Der Bereich links von ii ist sortiert.

    Zwischenergebnis

    Am Ende ist der ganze Bereich sortiert.

  4. 4

    Teil d): Ein Gegenbeispiel konstruieren

    Man braucht zwei gleichwertige Elemente und ein kleineres dahinter, das den Tausch über sie hinweg auslöst.

    [3_a, 3_b, 1] \to [1, 3_b, 3_a]

    Zwischenergebnis

    Die Reihenfolge der Dreien ist vertauscht.

    Ein einziges Gegenbeispiel genügt, um Stabilität zu widerlegen. Um sie zu belegen, müsste man dagegen für alle Fälle argumentieren.

Übung 3

schwer

a) (Vertiefung) Erkläre das Prinzip Teile und herrsche am Sortieren durch Mischen und begründe den Aufwand O(nlog⁡n)O(n \log n). b) (Vertiefung) Warum kann kein vergleichendes Sortierverfahren schneller als O(nlog⁡n)O(n \log n) sein? c) Warum sortieren gute Bibliotheken kurze Teilstücke mit einem O(n2)O(n^2)-Verfahren? d) Wann ist Stabilität wichtig? Nenne ein konkretes Beispiel.

Tipp anzeigen

Zu b): Wie viele Anordnungen gibt es, und wie viele Fälle unterscheiden kk Vergleiche?

Lösung anzeigen

a) Prinzip: Das Feld wird in zwei Hälften geteilt (teilen), jede Hälfte auf dieselbe Weise sortiert (herrschen, also ), und die beiden sortierten Hälften werden gemischt (zusammenfügen). Der Abbruch erfolgt bei Länge 1, denn ein einzelnes Element ist bereits sortiert.

Aufwand: Das Halbieren lässt sich log⁡2n\log_2 n-mal durchführen, bis Stücke der Länge 1 übrig sind. Auf jeder dieser Ebenen wird insgesamt jedes Element genau einmal gemischt, was O(n)O(n) je Ebene kostet, denn beim Mischen zweier sortierter Folgen ist das kleinste Element immer eines der beiden vordersten. Zusammen also log⁡2n\log_2 n Ebenen mal O(n)O(n), das ergibt O(nlog⁡n)O(n \log n).

b) Es gibt n!n! mögliche Anordnungen von nn Elementen, und genau eine davon ist die sortierte. Das Verfahren muss allein durch Vergleiche herausfinden, welche Anordnung vorliegt.

Jeder Vergleich hat zwei mögliche Ausgänge, teilt die verbliebenen Möglichkeiten also höchstens in zwei Gruppen. Mit kk Vergleichen sind damit höchstens 2k2^k Fälle unterscheidbar. Notwendig ist folglich

2k≥n!⟺k≥log⁡2(n!)2^k \ge n! \quad \Longleftrightarrow \quad k \ge \log_2(n!)

und log⁡2(n!)\log_2(n!) wächst wie nlog⁡nn \log n. Also braucht jedes vergleichende Verfahren mindestens diese Größenordnung.

Der Zusatz „vergleichend" ist wesentlich: Verfahren, die zusätzliche Annahmen über die nutzen, unterliegen der Schranke nicht. Weiß man etwa, dass alle Werte ganze Zahlen zwischen 1 und 100 sind, kann man sie in 100 Fächern zählen und ist in O(n)O(n) fertig, ohne je zwei Werte zu vergleichen.

c) Weil die nur das Wachstum beschreibt und die konstanten Faktoren weglässt. Diese Faktoren sind bei den einfachen Verfahren klein: Sortieren durch Einfügen braucht keine Rekursion, keine Funktionsaufrufe und keinen zusätzlichen Speicher, sondern arbeitet direkt im Feld.

Bei kurzen Stücken, etwa bis zehn oder zwanzig Elementen, überwiegt dieser Vorteil den Nachteil des schlechteren Wachstums. Hinzu kommt, dass die Teilstücke beim Sortieren durch Mischen oft bereits fast sortiert sind, und genau davon profitiert das Einfügeverfahren mit seinem besten Fall O(n)O(n).

Das ist kein Widerspruch zur Theorie, sondern ihre saubere Anwendung: Die Aussage von O(nlog⁡n)O(n \log n) gilt für große nn, und die Bibliothek nutzt genau die Lücke, die für kleine nn bleibt.

d) Immer dann, wenn mehrstufig sortiert wird.

Konkretes Beispiel: Eine Tabelle mit Schülerdaten soll nach Klasse und innerhalb jeder Klasse nach Nachname geordnet werden. Man sortiert zuerst nach Nachname, dann stabil nach Klasse. Da die stabile zweite Sortierung die Reihenfolge gleicher Klassen unangetastet lässt, bleiben die Nachnamen innerhalb jeder Klasse geordnet.

Mit einem instabilen Verfahren wäre die Ordnung nach Nachname im zweiten Schritt zerstört, und das Ergebnis wäre nur noch nach Klasse sortiert. Genau deshalb bieten Tabellenprogramme und Datenbanken stabile Sortierungen an: Sie erlauben, eine Ansicht schrittweise zu verfeinern.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    a) (Vertiefung) Teile und herrsche am Sortieren durch Mischen

    Prinzip: Das Feld wird in zwei Hälften geteilt, jede Hälfte auf dieselbe Weise sortiert (herrschen, also Rekursion), und die beiden sortierten Hälften werden gemischt. Der Abbruch erfolgt bei Länge 1, denn ein einzelnes Element ist bereits sortiert.

  2. 2

    a) (Vertiefung) Warum der Aufwand O(n log n) ist

    Das Halbieren lässt sich log⁡2n\log_2 n-mal durchführen, bis Stücke der Länge 1 übrig sind. Das ist die Zahl der Ebenen. Auf jeder Ebene wird insgesamt jedes Element genau einmal gemischt, was O(n)O(n) je Ebene kostet. Zusammen: log⁡2n\log_2 n Ebenen mal O(n)O(n), also O(nlog⁡n)O(n \log n).

    log⁡2n⋅O(n)=O(nlog⁡n)\log_2 n \cdot O(n) = O(n \log n)

  3. 3

    b) (Vertiefung) Die untere Schranke für vergleichendes Sortieren

    Es gibt n!n! mögliche Anordnungen von nn Elementen, und genau eine davon ist die sortierte. Jeder Vergleich hat zwei mögliche Ausgänge, teilt die verbliebenen Möglichkeiten also höchstens in zwei Gruppen. Mit kk Vergleichen sind damit höchstens 2k2^k Fälle unterscheidbar. Notwendig ist folglich 2k≥n!2^k \ge n!, also k≥log⁡2(n!)k \ge \log_2(n!), und log⁡2(n!)\log_2(n!) wächst wie nlog⁡nn \log n.

    2k≥n!⇔k≥log⁡2(n!)2^k \ge n! \Leftrightarrow k \ge \log_2(n!)

  4. 4

    c) Warum Bibliotheken kurze Teilstücke mit O(n²) sortieren

    Weil die O-Notation nur das Wachstum beschreibt und die konstanten Faktoren weglässt. Diese Faktoren sind bei den einfachen Verfahren klein: Sortieren durch Einfügen braucht keine Rekursion, keine Funktionsaufrufe und keinen zusätzlichen Speicher, sondern arbeitet direkt im Feld. Bei kurzen Stücken, etwa bis zehn oder zwanzig Elementen, überwiegt dieser Vorteil den Nachteil des schlechteren Wachstums.

  5. 5

    d) Wann Stabilität wichtig ist

    Immer dann, wenn mehrstufig sortiert wird. Beispiel: Eine Tabelle mit Schülerdaten soll nach Klasse und innerhalb jeder Klasse nach Nachname geordnet werden. Man sortiert zuerst nach Nachname, dann stabil nach Klasse, da die stabile zweite Sortierung die Reihenfolge gleicher Klassen unangetastet lässt, bleiben die Nachnamen innerhalb jeder Klasse geordnet.

Zusammenfassung

Sortieren durch Auswahl sucht wiederholt das kleinste Element des Restes und tauscht es nach vorn; es braucht immer n(n−1)2\frac{n(n-1)}{2} Vergleiche, unabhängig von den , dafür aber höchstens n−1n-1 Vertauschungen. Sortieren durch Einfügen schiebt jedes Element in den bereits sortierten linken Teil und profitiert deshalb von Vorsortierung, mit O(n)O(n) im besten und O(n2)O(n^2) im schlechtesten Fall; der sortierte linke Teil ist dabei die Invariante, aus der sich die Richtigkeit des Verfahrens begründen lässt. Alle Verfahren mit zwei geschachtelten bleiben bei O(n2)O(n^2), weshalb ein echter Fortschritt eine andere Idee verlangt: Teile und herrsche zerlegt das Feld, sortiert die Teile und mischt sie anschließend, was über log⁡2n\log_2 n Ebenen mit je O(n)O(n) Mischaufwand auf O(nlog⁡n)O(n \log n) führt, allerdings zum Preis von O(n)O(n) zusätzlichem Speicher. Stabilität, also die Erhaltung der Reihenfolge gleichwertiger Elemente, entscheidet darüber, ob mehrstufiges Sortieren möglich ist. Schneller als O(nlog⁡n)O(n \log n) kann kein vergleichendes Verfahren sein, denn kk Vergleiche unterscheiden höchstens 2k2^k Fälle, und es gibt n!n! mögliche Anordnungen.