Combsort
Comb sort (of English comb , comb) is a in April 1991 in BYTE magazine of S. Lacey and R. Box imagined, from bubblesort derived, non-stable in-place - sort algorithm ., Which for a series of linearly arranged elements (B. Numbers, alphabets) according to a comparison criterion (e.g. size).
principle
In contrast to Bubblesort, which only compares neighboring elements and, if necessary, swaps them, Combsort starts with elements that are far apart ( gap = gap). This means that elements that are roughly incorrectly sorted find their target position more quickly. After each run, the gap is reduced by dividing by 1.3 and the process is repeated. This empirically found crooked divisor ensures that adjacent areas always overlap in successive runs and do not form clusters that would only be resolved in later runs.
The algorithm ends when at least one pass with Gap = 1 takes place and no more interchanges have taken place.
With this final value Gap = 1, it is practically identical to the bubble sort in the end, and the correctness of the sorting has been proven.
To name: the field to be sorted is quasi with a comb (such as English comb ) with increasingly dense teeth combed.
Comb sort is similar to that on the insertion site based Shellsort .
complexity
The complexity lies between ( worst case ) and (best case) depending on the initial situation . In the best case, the list of items to be sorted is ordered as soon as the step length is 1. In the worst case, all neighboring elements must be exchanged again (several passes with a step length of 1). In this case Combsort is no faster than Bubblesort .
Formal algorithm
In the pseudocode , the CombSort algorithm looks like this:
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 ) solange (vertauscht == wahr oder schritt > 1) prozedur ende
literature
- Stephen Lacey, Richard Box: A Fast Easy Sort . In: Byte Magazine . April 1991 ( cs.clackamas.cc.or.us ).
- Wlodzimierz Dobosiewicz: An efficient variation of bubble sort . In: Information Processing Letters . tape 11 , no. 1 , 1980, p. 5-6 , doi : 10.1016 / 0020-0190 (80) 90022-8 .
Web links
- Combsort ( Memento from April 19, 2005 in the Internet Archive ) at Computer Science for the COBOL Community
- Combsort at sortieralgorithmen.de