imported>SchlurcherBot: Bot: http → https

2025-10-26T12:52:24Z

Bot: http → https

Neue Seite

[[Datei:Comb sort demo.gif|mini|300px|Sortierung eines Feldes von 33 Elementen mittels Combsort.]]
'''Combsort''' (von {{enS|comb}}, Kamm) ist ein im April 1991 im ''BYTE magazine'' von S. Lacey und R. Box vorgestellter, vom [[Bubblesort]] abgeleiteter, [[Stabilität (Sortierverfahren)|nicht-stabiler]] [[In-place]]-[[Sortierverfahren|Sortieralgorithmus]], der eine Folge linear angeordneter Elemente (z. B. Zahlen, Alphabete) einem Vergleichskriterium (z. B. der Größe) nach anordnet.

== 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 mit Division durch 1,3 verkleinert und der Vorgang wiederholt.
Durch diesen [[Empirie|empirisch]] gefundenen krummen Divisor wird erreicht, dass sich angrenzende Bereiche in aufeinanderfolgenden Durchläufen stets überlappen und keine [[Cluster (Datenanalyse)|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 ({{enS|comb}}) mit immer dichter werdenden Zähnen durchgekämmt.

Combsort ähnelt dem auf [[Insertionsort]] basierenden [[Shellsort]].

== Komplexität ==
Die Komplexität liegt je nach Ausgangssituation zwischen <math> \mathcal{O}(n^2) </math> ([[Zeitkomplexität|Worst-Case]]) und <math> \mathcal{O}(n \log (n)) </math> (Best-Case).

Im Best-Case ist die Liste der zu sortierenden Elemente geordnet, sobald die Schrittlänge 1 beträgt.

Im Worst-Case müssen alle benachbarten Elemente nochmals getauscht werden (mehrere Durchgänge mit Schrittlänge 1). In diesem Fall ist Combsort nicht schneller als [[Bubblesort]].

Der Avg. Case ist <math> \mathcal{O}(n^2) </math>, analog zu Bubblesort.

== Formaler Algorithmus ==
Im [[Pseudocode]] sieht der CombSort-[[Algorithmus]] so aus:

'''prozedur''' combSort ( A: Liste sortierbarer Elemente )
schritt:= Länge ( A )
'''wiederhole'''
vertauscht:= falsch
'''für jedes''' i '''von''' 0 '''bis''' (Länge ( A ) - schritt) '''wiederhole'''
'''falls''' ( A[ i ] > A[i + schritt]) '''dann'''
vertausche ( A [ i ], A [ i + schritt ] )
vertauscht:= wahr
'''falls ende'''
'''für ende'''
'''falls''' (schritt > 1) '''dann'''
schritt:= Ganzzahl ( schritt/1.3 )
vertauscht := wahr
'''falls ende'''
'''solange''' (vertauscht == wahr '''oder''' schritt > 1)
'''prozedur ende'''

== Literatur ==
* {{Literatur
|Autor=Stephen Lacey, Richard Box
|Titel=A Fast Easy Sort
|Sammelwerk=Byte Magazine
|Datum=1991-04
|Online=[http://cs.clackamas.cc.or.us/molatore/cs260Spr03/combsort.htm cs.clackamas.cc.or.us]}}
* {{Literatur
|Autor=Wlodzimierz Dobosiewicz
|Titel=An efficient variation of bubble sort
|Sammelwerk=Information Processing Letters
|Band=11
|Nummer=1
|Datum=1980
|Seiten=5–6
|DOI=10.1016/0020-0190(80)90022-8}}

== Weblinks ==
{{Commonscat|Sort algorithms|Sortieralgorithmen}}
{{Wikibooks|Algorithmensammlung: Sortierverfahren: Combsort|Combsort|suffix=Implementierungen in der Algorithmensammlung}}
* {{Webarchiv |url=http://objectz.com/columnists/leif/07242000.htm |text=Combsort |wayback=20050419014554}} bei ''Computer Science for the COBOL Community''
* [https://www.sortieralgorithmen.de/combsort Combsort] bei sortieralgorithmen.de

[[Kategorie:Sortieralgorithmus]]

Combsort - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https