Swap-Sort

Grundidee

Swap-Sort ist ein Sortieralgorithmus für ein Array aus paarweise verschiedenen Zahlen. Für jedes Element wird gezählt, wie viele im Array enthaltene Werte kleiner sind. Diese Anzahl sei m. Anschließend wird das Element mit dem Element an der Position A(m+1) vertauscht. Dadurch gelangt das vertauschte Element an seine endgültige, bereits sortierte Position.

Der Algorithmus setzt voraus, dass jedes Element nur einmal vorkommt. Bei gleichen Werten erfolgt keine Terminierung.

Ablauf

Für ein Array A mit n Elementen arbeitet Swap-Sort nach diesem Schema:

• Beginn mit i = 1.
• Zähle die Elemente, die kleiner als A(i) sind; ihre Anzahl sei m. Vertausche A(i) mit A(m+1).
• Falls i = m+1 gilt, erhöhe i um 1.
• Falls i = n gilt, ist die Sortierung beendet. Andernfalls wird mit dem Zählen für das aktuelle Element fortgefahren.

Der Index wird also erst weitergeschaltet, wenn das Element an der Stelle steht, die sich aus der Anzahl der kleineren Werte ergibt.

Beispiel

Das Array {7,8,5,2,4,9,3,1} wird sortiert. Zu Beginn steht der Index auf dem ersten Element. 7 hat fünf kleinere Werte und wird deshalb mit A(5+1) vertauscht. Danach steht das Array als 9 8 5 2 4 7 3 1.

Anschließend wird 9 mit A(7+1) vertauscht: 1 8 5 2 4 7 3 9. Da die Anzahl der kleineren Elemente von A(1) nun dem Index-1 entspricht, wird der Index erhöht. Durch weitere Vertauschungen entsteht schrittweise:

1 3 5 2 4 7 8 9 1 5 3 2 4 7 8 9 1 4 3 2 5 7 8 9 1 2 3 4 5 7 8 9

Danach werden die übrigen Positionen durchlaufen. Das Array bleibt unverändert, bis der Index n erreicht ist. Das vollständig sortierte Ergebnis lautet 1 2 3 4 5 7 8 9.

Komplexität und Implementierungen

Um die Anzahl der kleineren Einträge zu bestimmen, ist ein vollständiger Array-Durchlauf erforderlich. Dieser Vorgang wird für jedes Element durchgeführt. Daraus ergibt sich die Laufzeitkomplexität O(n²).

Der Artikel enthält Implementierungen in Ada, Haskell, Java und Python. Die Programme zählen jeweils die kleineren Werte, bestimmen daraus die Zielposition und vertauschen Elemente, bis das aktuelle Element an dieser Position steht. Anschließend wird zum nächsten Index gewechselt. Die Beispiele verwenden dabei die in Programmiersprachen üblichen nullbasierten Indizes.

Das Java-Beispiel sortiert ein Array und enthält als Testdaten {3, 7, 45, 1, 33, 5, 2, 9}. Die Python-Funktion arbeitet direkt auf der übergebenen Liste und verändert sie durch Vertauschungen.