Combsort

Combsort (of English. Comb, comb ) is a site presented in April 1991 in BYTE magazine by S. Lacey and R. Box, derived from Bubblesort, non- stable in-place sorting algorithm, a sequence of linearly arranged elements (eg. figures ) a comparison criterion (eg, the size ) of orders.

Principle

Unlike Bubblesort, the only compares each adjacent elements and possibly reversed, Combsort begins first with widely spaced elements ( engl. Gap = gap). This find grossly incorrect sized items faster its target position. After each pass through the gap is reduced by dividing by 1.3, and the process repeated. This empirically crooked divisor is achieved that adjacent regions always overlap in successive passes and do not form clusters, which would only resolved in later runs.

The algorithm ends when at least one run with Gap = 1, and there has been no more swapping.

In this final value Gap = 1, it is at the end of virtually identical to the bubblesort, and the accuracy of sorting is proved.

About the name: The field to be sorted is almost like a comb ( comb engl. ) combed through with increasingly dense teeth.

Combsort similar to the insertion site based on Shellsort.

Complexity

The complexity, depending on the initial situation between ( worst-case ), and ( best-case ). In the best case, the list of elements to be sorted is sorted as soon as the step length is 1. In the worst case all adjacent elements need to be replaced again ( several steps with step length 1). In this case Combsort is not faster than bubblesort.

Formal algorithm

In pseudo-code the CombSort algorithm looks like this:

Procedure combSort (A: list of sortable items )    step: = length (A)    repeat       swapped: = false       if ( step > 1) then step: = integer ( schritt/1.3 )       for each i from 0 to ( length (a) - step ) repeat          if (A [i ]> A [i step ] ) then             Swap (A [i ], A ​​[i step ] )             swapped: = true          if the end       for the end of    while ( swapped == true or step > 1) procedure end literature

• Stephen Lacey and Richard Box: A Fast Easy Collate In: Byte Magazine. April 1991 (HTML).
• Wlodzimierz Dobosiewicz: An efficient variation of bubble sort. In: Information Processing Letters. 11, No. 1, 1980, pp. 5-6, doi: 10.1016/0020-0190 (80 ) 90022-8.