Grundprinzip
Ein Sortierdurchgang
Autor: Ulrich Helmich 09/2023, Lizenz: siehe Seitenende
A, B: Zunächst werden die beiden ersten Elemente der Queue in zwei Hilfsvariablen tmp1 und tmp2 gespeichert und aus der Queue gelöscht. Dazu sollte die Queue natürlich mindestens aus zwei Elementen bestehen.
C: Nun werden die beiden Hilfsvariablen verglichen. Falls tmp2 kleiner ist als tmp1, wird getauscht, so dass tmp2 stets den größeren Wert enthält. Dann wird tmp1 in der Hilfsqueue gespeichert. Der Wert von tmp2 bleibt erhalten, der Wert von tmp1 kann neu belegt werden.
D: Jetzt wird das nächste Element aus der Queue ausgelesen und in tmp1 gespeichert, anschließend wird das Element aus der Queue gelöscht.
E: Wieder werden die beiden Hilfsvariablen verglichen und eventuell getauscht, so dass tmp2 das größere der beiden Elemente enthält. Dann wird tmp1 wieder in die Hilfsqueue eingefügt.
F - L: Anschließend wird das nächste Element aus der Queue in tmp1 gespeichert und so weiter, bis die Queue keine Elemente mehr enthält.
Wie man leicht sieht, kann man das Ganze in eine Schleife packen; hier empfiehlt sich eine while-Schleife.
Nach dem letzten Schleifendurchgang ist die Hilfsqueue noch nicht sortiert, aber zumindest sollte sich die größte Zahl der alten Queue ganz am Ende der Hilfsschlange befinden.
Der Sortiervorgang ist jetzt allerdings noch nicht beendet, weil sich ja erst eine Zahl an der korrekten Position der Hilfsschlange befindet.
Die Hilfsschlange wird jetzt zurück in die nunmehr leere Originalschlange kopiert (auch noch ein kleiner Algorithmus), und dann geht das Ganze von vorne los. Die oben beschriebenen Aktionen packt man am besten in eine for-Schleife, die so oft durchlaufen wird, wie die Queue Elemente hat. Dann sollte -ähnlich wie beim Bubblesort - die Hilfsqueue sortiert sein. Das größte Element befindet sich hinten, das kleinste vorne.
Durch Abänderung der if-Anweisungen kann man das Verfahren auch so gestalten, dass sich die kleinste Zahl vorne und die größte hinten befindet.
Man könnte auch abwechselnd die Hilfsqueue und die Hauptqueue zum Zwischenspeichern benutzen, dann würde das Umkopieren der Hilfsqueue in die Hauptqueue entfallen. Am Ende muss man nur dafür sorgen, dass die Hauptqueue die sortierten Zahlen enthält.