Sortieralgorithmus: Verfahren einfach vergleichen

Eine Zahlenfolge besteht aus Zahlen in einer bestimmten Reihenfolge. Jede einzelne Zahl darin heißt Element. Eine Folge ist aufsteigend sortiert, wenn keine Zahl größer als ihr rechter Nachbar ist. Gleiche Nachbarn sind erlaubt.

Prüfe dazu alle benachbarten Zahlenpaare von links nach rechts. Findest du eine linke Zahl, die größer als die rechte ist, ist die Folge nicht aufsteigend sortiert. Gibt es bei keinem Nachbarpaar einen solchen Abstieg, ist die ganze Folge aufsteigend sortiert: Die Zahlen werden nach rechts hin nicht kleiner.

Ein richtig geordnetes Nachbarpaar allein genügt für diese Prüfung nicht. Auch die übrigen Nachbarpaare müssen passen. Eine leere Folge und eine Folge mit nur einer Zahl gelten ebenfalls als sortiert, weil sie kein falsch geordnetes Nachbarpaar enthalten.

Wir sortieren aufsteigend und verwenden die folgenden festen Varianten. Ihre Schritte sind Beschreibungen in Alltagssprache, kein ausführbarer Programmcode.

Bei Bubblesort gehst du von links nach rechts durch die Folge. Vergleiche jeweils zwei Nachbarn und tausche sie, wenn die linke Zahl größer ist. Gleiche Zahlen werden nicht getauscht. Nach einem vollständigen Durchlauf steht eine größte Zahl des geprüften Bereichs an dessen rechtem Ende. Diese Stelle ist fertig. Im nächsten Durchlauf prüfst du eine Stelle weniger. Wiederhole das, bis der Bereich höchstens eine Zahl enthält. Mit Frühabbruch darfst du schon dann aufhören, wenn ein ganzer Durchlauf durch den noch zu prüfenden Bereich ohne Tausch endet. Ein einzelnes Nachbarpaar ohne Tausch reicht nicht.

Bei Selectionsort suchst du im noch nicht fertigen Bereich die kleinste Zahl. Gibt es sie dort mehrfach, wähle die erste von links. Tausche sie direkt mit der ersten Zahl dieses Bereichs. Steht sie bereits dort, bleibt sie stehen. Danach gehört diese Stelle zum fertigen linken Teil. Suche und tausche im verbleibenden rechten Bereich weiter. Ist dort höchstens eine Zahl übrig, bist du fertig. Beim direkten Tausch wechseln die beiden betroffenen Zahlen ihre Plätze; die Zahlen dazwischen werden nicht verschoben.

Bei Insertionsort beginnst du mit der ersten Zahl als sortiertem linken Teil. Nimm jeweils die nächste Zahl rechts daneben und merke sie dir. Vergleiche sie im linken Teil von rechts nach links mit den Vorgängern. Verschiebe jeden größeren Vorgänger um eine Stelle nach rechts. Sobald du einen kleineren oder gleichen Vorgänger erreichst, fügst du die gemerkte Zahl direkt dahinter ein. Erreichst du den Anfang, kommt sie nach ganz links. Gleiche Vorgänger werden nicht verschoben. Wiederhole das mit jeder weiteren Zahl.

Der Zeitbedarf hängt von der Anzahl der Elemente ab. Diese Anzahl nennen wir n. Für den Vergleich betrachten wir Folgen mit mindestens zwei Zahlen. Wir zählen Zahlenvergleiche, Tausche und Verschiebungen als Arbeitsschritte. Dabei behandeln wir jeden Zahlenvergleich und jede Bewegung einer Zahl als gleich aufwendig, unabhängig von der Ziffernzahl. Das ist ein vereinfachtes Modell, keine Messung von Sekunden auf einem bestimmten Computer.

Die O-Schreibweise, gesprochen „O von …“, beschreibt eine obere Grenze für das Wachstum des Arbeitsbedarfs bei längeren Folgen. Feste Faktoren und kleine Zusatzarbeiten stehen dabei nicht im Vordergrund. Die Tabelle nennt die üblichen engen Grenzen: O(n) steht dort für lineares Wachstum, also Wachstum ungefähr im Verhältnis zur Folgenlänge. O(n^2) steht dort für quadratisches Wachstum; n^2 bedeutet n mal n. Bei doppelter Länge kann der führende quadratische Anteil etwa viermal so groß werden. Daraus folgt keine genaue Vervierfachung gemessener Sekunden.

Der beste und der schlechteste Fall beziehen sich auf Anordnungen derselben Anzahl von Zahlen. Für „im Mittel“ betrachten wir zufällige Anordnungen verschiedener Zahlen, bei denen jede Reihenfolge gleich wahrscheinlich ist. Ein Mittelwert sagt nicht voraus, wie lange jede einzelne Folge braucht.

Bubblesort mit Frühabbruch prüft eine bereits sortierte Folge in einem Durchlauf. Stehen verschiedene Zahlen von der größten bis zur kleinsten, braucht es mit wachsender Folgenlänge immer mehr Durchläufe. Selectionsort sucht auch in einer sortierten Folge immer wieder die kleinste verbleibende Zahl. Dabei entstehen insgesamt n(n-1)/2 Vergleiche: erst n-1, dann n-2 und schließlich ein Vergleich. Insertionsort muss bei einer sortierten Folge keine Zahl verschieben. Stehen verschiedene Zahlen von der größten bis zur kleinsten, muss dagegen jede neu genommene Zahl an allen bisherigen Zahlen vorbei. Diese Arbeitsweisen erklären die Unterschiede in der Tabelle; ein einzelner Beispieldurchlauf allein beweist sie nicht.

Stabilität betrifft Elemente mit demselben Sortierwert. Ein Sortierwert ist die Zahl oder Eigenschaft, nach der geordnet wird. Ein stabiles Verfahren erhält die bisherige Reihenfolge von Elementen mit gleichem Sortierwert. Unsere Bubble- und Insertion-Varianten sind stabil, weil sie gleiche Werte nicht aneinander vorbeibewegen. Selectionsort mit direktem Tausch ist nicht stabil: Die Reihenfolge gleicher Werte kann sich ändern. Sie muss sich aber nicht bei jeder Folge ändern.

Zusätzlicher Speicher ist Speicher über die gespeicherte Eingabefolge hinaus. Unsere Varianten brauchen nur wenige Hilfswerte, etwa zum Merken einer Zahl und einer Stelle. Dafür steht O(1), gesprochen „O von eins“: Der zusätzliche Bedarf bleibt durch eine feste Größe begrenzt, wenn die Folge länger wird. Der Speicher für die Eingabefolge selbst wird dabei nicht mitgezählt. Keine unserer Varianten braucht eine zweite vollständige Folge.

Einfache Sortierverfahren können für kleine Folgen sinnvoll sein. Bei wenigen Elementen bleibt auch eine quadratische Zahl von Arbeitsschritten klein. Die Verfahren sind außerdem leicht nachzuvollziehen und brauchen wenig zusätzlichen Speicher. Das garantiert nicht, dass sie auf jedem Computer bei jeder kleinen Folge am schnellsten sind. Für eine Auswahl zählen neben der Folgenlänge auch die Ausgangsordnung und eine mögliche Forderung nach Stabilität.

Für Insertionsort ist wichtig, wie viele falsch geordnete Paare die Folge enthält. Ein solches Paar besteht aus einer früheren größeren und einer späteren kleineren Zahl. Die beiden müssen keine direkten Nachbarn sein. Gleiche Zahlen bilden kein falsch geordnetes Paar. Wir nennen die Anzahl dieser Paare I. Wie groß die Zahlenwerte sind oder wie viele Ziffern sie haben, bestimmt in unserem Modell nicht die Zahl der Verschiebungen.

Jede Verschiebung bei Insertionsort bewegt einen größeren Vorgänger nach rechts an der gerade einzufügenden Zahl vorbei. Dadurch wird genau eines dieser falsch geordneten Paare beseitigt. Insgesamt gibt es deshalb genau I solche Verschiebungen. Hinzu kommt die Arbeit, jede weitere Zahl aufzunehmen und ihren Platz zu prüfen. Zusammen ergibt das O(n+I), wobei n wieder die Anzahl der Zahlen ist. Wenn I höchstens im Verhältnis zu n wächst, bleibt dieser Bedarf linear. Wenige falsch geordnete Paare helfen Insertionsort also besonders.

„Fast sortiert“ ist ohne genauere Erklärung ungenau. Eine Folge kann entstehen, indem aus einer sortierten Folge die kleinste Zahl ans rechte Ende versetzt wird. Dann muss diese Zahl an allen anderen Zahlen vorbei. Bei unserem Bubblesort von links nach rechts kommt sie pro Durchlauf nur eine Stelle nach links. Solange sie noch falsch steht, gibt es einen Tausch und der Frühabbruch greift nicht.

Für eine solche Folge mit n verschiedenen Zahlen braucht Bubblesort n-1 Durchläufe mit insgesamt n(n-1)/2 Vergleichen. Der Bedarf wächst damit quadratisch, obwohl nur die kleinste Zahl aus der sortierten Folge ans Ende versetzt wurde. Insertionsort verschiebt hier die anderen n-1 Zahlen jeweils einmal und arbeitet insgesamt linear. Selectionsort bleibt auch bei dieser Vorordnung quadratisch, weil es seine Suche nach dem kleinsten verbleibenden Wert wiederholt.