Sortieren 1: Bubblesort, Selectionsort und Insertionsort

Selectionsort macht bei jeder Liste mit 10 Werten genau 45 Vergleiche, ob die Liste gemischt oder schon geordnet beginnt.

Dinge in Ordnung bringen

Sortieren heißt, eine Liste so umzuordnen, dass ihre Werte vom kleinsten zum größten laufen (oder nach Name, Datum, Preis, jeder Ordnung, nach der man vergleichen kann). Es ist eine der häufigsten Aufgaben eines Computers: die Kontakte im Handy, Suchergebnisse nach Relevanz, eine Tabellenspalte nach Datum. Sortieren erleichtert auch andere Aufgaben. Wie die letzte Einheit gezeigt hat, lässt sich eine sortierte Liste binär durchsuchen, und doppelte Werte stehen in einer sortierten Liste nebeneinander.

Diese Einheit behandelt drei einfache Verfahren. Alle drei vergleichen jeweils zwei Werte und verschieben Werte innerhalb derselben Liste. Sie sind kurz zu schreiben und leicht nachzuvollziehen, und alle drei werden bei langen Listen stark langsamer. Zu beobachten, warum, ist die beste Vorbereitung auf die schnelleren Verfahren der nächsten Einheit. Dabei zählen wir durchgehend zwei Dinge: Vergleiche (die Frage „ist dieser Wert größer als jener?“) und Vertauschungen (zwei Werte tauschen die Plätze).

Bubblesort: Nachbarn in falscher Reihenfolge vertauschen

Bubblesort läuft die Liste entlang und vergleicht jedes Nachbarpaar. Ist der linke Wert größer, werden die beiden vertauscht. Nach einem vollen Durchlauf ist der größte Wert Schritt für Schritt ganz nach rechts gewandert, wie eine aufsteigende Blase, und muss sich nie wieder bewegen. Der nächste Durchlauf kann eine Stelle früher aufhören. Eine übliche Verbesserung: auf einen Durchlauf ganz ohne Vertauschung achten. Dann ist alles schon geordnet, und das Sortieren kann früher enden.

Verfolge es an der Liste [5, 1, 4, 2, 8]. Der erste Durchlauf vergleicht 5 und 1 (tauschen), 5 und 4 (tauschen), 5 und 2 (tauschen), 5 und 8 (lassen): Die Liste ist jetzt [1, 4, 2, 5, 8], und 8 steht an seinem Platz. Der zweite Durchlauf vergleicht 1 und 4, 4 und 2 (tauschen), 4 und 5, das ergibt [1, 2, 4, 5, 8]. Der dritte Durchlauf vergleicht 1 und 2, dann 2 und 4, tauscht nichts und hört auf. Insgesamt: 4 + 3 + 2 = 9 Vergleiche und 4 Vertauschungen.

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // tauschen
        swapped = true;
      }
    }
    if (!swapped) break;  // schon sortiert
  }
  return a;
}

Selectionsort: das Kleinste suchen und als Nächstes einsetzen

Selectionsort funktioniert so, wie viele Leute Spielkarten auf der Hand ordnen. Durchsuche die ganze Liste nach dem kleinsten Wert und tausch ihn an die erste Stelle. Dann durchsuche den Rest nach dem kleinsten übrigen Wert und tausch ihn an die zweite Stelle, und so weiter. Bei [5, 1, 4, 2, 8] findet der erste Durchgang 1 und tauscht es mit 5. Der zweite findet 2 und tauscht es mit 5. Die letzten beiden Durchgänge finden 4 und 5 schon an ihrem Platz. Das sind nur 2 Vertauschungen, aber die Durchgänge vergleichen trotzdem 4 + 3 + 2 + 1 = 10 Mal.

Selectionsort hört nie früher auf. Selbst bei einer schon sortierten Liste muss es jeden übrigen Wert prüfen, um sicher zu sein, dass es den kleinsten hat. Bei n Werten summieren sich die Vergleiche immer zu (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Bei 10 Werten sind das 45, bei 100 Werten 4950, bei 1000 Werten 499 500. Seine Stärke ist die kleine Zahl an Vertauschungen: höchstens n − 1. Das zählt, wenn das Verschieben eines Werts teuer ist.

Insertionsort: jeden neuen Wert an seinen Platz schieben

Insertionsort hält den linken Teil der Liste sortiert und vergrößert ihn um einen Wert nach dem anderen. Es nimmt den nächsten Wert und schiebt ihn nach links, indem es ihn mit seinem Nachbarn tauscht, bis der Nachbar nicht größer ist. Dann steht dieser Wert an seinem Platz zwischen den sortierten. Bei einer Liste, die schon fast geordnet ist, rückt jeder neue Wert nur ein oder zwei Schritte, deshalb ist Insertionsort dort sehr schnell. Bei [5, 1, 4, 2, 8] macht es 7 Vergleiche und 4 Vertauschungen.

Vertauschungen zählen: Fehlstellungen

Es gibt einen eleganten Weg vorherzusagen, wie viele Vertauschungen Bubblesort und Insertionsort brauchen. Zähl die Fehlstellungen (Inversionen): Paare von Werten, die zueinander in der falschen Reihenfolge stehen. In [5, 1, 4, 2, 8] sind das (5, 1), (5, 4), (5, 2) und (4, 2), insgesamt vier. Jede Vertauschung zweier Nachbarn in falscher Reihenfolge behebt genau eine Fehlstellung und erzeugt keine neue, also machen beide Verfahren genau 4 Vertauschungen. Eine umgekehrte Liste mit n Werten hat jedes Paar vertauscht, also n(n − 1)/2 Fehlstellungen, und das ist der schlechteste Fall.

Jede Zelle zeigt Vergleiche / Vertauschungen. Die Beispielliste ist [5, 1, 4, 2, 8]. Bubblesort ist hier die Version, die nach einem Durchlauf ohne Vertauschung aufhört.

Alle drei Verfahren haben dieselbe Schwäche. Im schlechtesten Fall vergleicht jedes ungefähr jedes Paar von Werten, also etwa n²/2 Vergleiche. Verdoppelt sich die Liste, vervierfacht sich die Arbeit. Zehnmal so viele Werte heißen hundertmal so viel Arbeit. Bei ein paar Dutzend Werten spielt das kaum eine Rolle, bei einer Million ist es hoffnungslos, und die nächste Einheit zeigt, wie es viel besser geht.