Combsort

from Wikipedia, the free encyclopedia
Sorting a field of 33 elements using 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

Commons : Sorting algorithms  - collection of images, videos and audio files
Wikibooks: Combsort  - implementations in the algorithm collection