Sortierverfahren
Darstellung in Struktogrammen
by Dr. M. Halfpap
Zurück zur Hauptseite
Bubblesort :
Auswahlsort :
Einfügesort :
Shakersort :
Verbessertes Sortieren durch Vertauschen (Shakersort)
Der Bubblesort-Algorithmus läßt sich recht einfach erheblich verbessern. So werden z.B. bei den letzten Durchläufen überhaupt keine Elemente mehr vertauscht, die Folge ist bereits
sortiert. Nun ließe sich ein Flag einführen, das TRUE wird, wenn kein Austausch mehr erfolgt. Der Algorithmus könnte dann abbrechen. Genauso gut wäre es möglich, sich zusätzlich
noch den Index zu merken, wo die letzte Vertauschung durchgeführt wurde, und dann beim nächsten Mal nur bis dorthin laufen zu lassen. Es muß sich bei diesem Index nämlich nicht
unbedingt um i handeln.
Diese kleinen Änderungen sind nicht sonderlich aufwendig, bringen aber einiges. Es gibt allerdings noch ein Problem: Eine kleinste Blase, die ganz am unteren/rechten Ende steht,
kommt mit einem Durchlauf an die richtige Stelle.
20 33 41 53 59 66 84 13
wird in einem Durchlauf sortiert. Eine zu große Blase wird allerdings pro Durchlauf nur ein Element nach unten/rechts geschoben.
84 13 20 33 41 53 59 66 benötigt acht Durchläufe, obwohl die Folge fast vollständig geordnet ist. Um diesem Umstand abzuhelfen, wird bei Shakersort mal wie bei Bubblesort, mal
umgekehrt sortiert, immer abwechselnd. Dabei merkt sich das Programm bei der Bubblesort-Richtung den kleinsten Vertauschindex, bei der anderen den größten, so daß die zu
untersuchende Folge zusätzlich schneller kleiner werden kann als beim normalen Bubblesort. Außerdem läßt sich leicht feststellen, wann die Folge sortiert ist, wenn nämlich der linke
Index größer oder gleich dem rechten ist.
Wir betrachten auch hier die Beispielfolge, um den Unterschied zum normalen Bubblesort zu erkennen. Dabei ist l der linke und r der rechte Index.
Startfolge 53 59 20 41 84 33 13 66
l=2 r=8 13 53 59 20 41 84 33 66
l=3 r=8 13 53 20 41 59 33 66 84
l=4 r=7 13 20 53 33 41 59 66 84
l=4 r=4 13 20 33 41 53 59 66 84 sortiert
