Combsort
aus Wikipedia, der freien Enzyklopädie
Combsort ist ein im April 1991 im BYTE magazine von S. Lacey und R. Box vorgestellter, vom Bubblesort abgeleiteter, nicht-stabiler In-place-Sortieralgorithmus, der eine Reihe von linear angeordneten Elementen (z. B. Zahlen) der Größe nach anordnet.
Der Name leitet sich von engl. comb = Kamm ab, s. u.
Inhaltsverzeichnis |
[Bearbeiten] Prinzip
Anders als Bubblesort, der nur jeweils benachbarte Elemente vergleicht und ggf. vertauscht, beginnt Combsort zunächst mit weit auseinanderliegenden Elementen (engl. Gap=Lücke). Dadurch finden grob falsch sortierte Elemente schneller ihre Zielposition. Nach jedem Durchlauf wird die Lücke durch Division mit 1.3 verkleinert und der Vorgang wiederholt. Durch diesen empirisch gefundenen krummen Divisor wird erreicht, dass sich angrenzende Bereiche in aufeinanderfolgenden Durchläufen stets überlappen und keine Cluster bilden, die erst in späteren Durchläufen aufgelöst würden.
Der Algorithmus endet, wenn mindestens ein Durchlauf mit Gap=1 erfolgt und keine Vertauschung mehr stattgefunden hat.
Bei diesem Endwert Gap=1 ist er am Ende praktisch identisch mit dem Bubblesort, und die Richtigkeit der Sortierung ist bewiesen.
Zum Namen: Das zu sortierende Feld wird quasi wie mit einem Kamm mit immer dichter werdenden Zähnen durchgekämmt.
Shellsort funktioniert ähnlich wie Combsort: Dort wird die Lücke halbiert, wenn keine Vertauschung mehr stattgefunden hat, Combsort hingegen verkleinert die Lücke nach jedem Durchlauf.
[Bearbeiten] Komplexität
Die Komplexität liegt je nach Ausgangssituation zwischen O(n2) (Worst-Case) und O(n·log(n)) (Best-Case)
[Bearbeiten] Implementierungsbeispiel in BASIC
'" Nach Byte 4/1991, S. 315, S. Lacey, R. Box
'" Combsort im Array H$(1)...H$(H)
'" Außerdem verwendete Variablen: HG,HF,HI,HJ,HX$
HG = H: HF = -1: REM H ist Anzahl, HG ist Gap, HF ist Flag: -1 == TRUE
WHILE HF OR HG <> 1
HG = INT(HG / 1.3): IF HG < 1 THEN HG = 1: REM verkleinern von Gap
IF HG = 9 OR HG = 10 THEN HG = 11: REM Sonderfallbehandlung
HF = 0: HE = H - HG
FOR HI = 1 TO HE
HJ = HI + HG
IF H$(HI) > H$(HJ) THEN SWAP H$(HI), H$(HJ): HF = -1: REM SWAP vertauscht Variableninhalte
NEXT
WEND
[Bearbeiten] Weblinks
- Computer Science for the COBOL Community – Sorting Algorithms (Seite offline, per Wayback Machine verfügbar)
- Asymptotisch gute Sortieralgorithmen
- An Improved Comb Sort with Pre-Defined Gap Table
Siehe auch: Liste von Algorithmen
