51 lines
1.8 KiB
Plaintext
51 lines
1.8 KiB
Plaintext
{{Sorting Algorithm}}
|
|
|
|
;Task:
|
|
Implement a ''comb sort''.
|
|
|
|
|
|
The '''Comb Sort''' is a variant of the [[Bubble Sort]].
|
|
|
|
Like the [[Shell sort]], the Comb Sort increases the gap used in comparisons and exchanges.
|
|
|
|
Dividing the gap by <big><math>(1-e^{-\varphi})^{-1} \approx 1.247330950103979</math> </big> works best, but <big> 1.3</big> may be more practical.
|
|
|
|
|
|
Some implementations use the insertion sort once the gap is less than a certain amount.
|
|
|
|
|
|
;Also see:
|
|
* the Wikipedia article: [[wp:Comb sort|Comb sort]].
|
|
|
|
|
|
Variants:
|
|
* Combsort11 makes sure the gap ends in (11, 8, 6, 4, 3, 2, 1), which is significantly faster than the other two possible endings.
|
|
* Combsort with different endings changes to a more efficient sort when the data is almost sorted (when the gap is small). Comb sort with a low gap isn't much better than the Bubble Sort.
|
|
|
|
<br>
|
|
Pseudocode:
|
|
'''function''' combsort('''array''' input)
|
|
gap := input'''.size''' ''//initialize gap size''
|
|
'''loop until''' gap = 1 '''and''' swaps = 0
|
|
''//update the gap value for a next comb. Below is an example''
|
|
gap := int(gap / 1.25)
|
|
'''if''' gap < 1
|
|
''//minimum gap is 1''
|
|
gap := 1
|
|
'''end if'''
|
|
i := 0
|
|
swaps := 0 ''//see [[Bubble Sort]] for an explanation''
|
|
''//a single "comb" over the input list''
|
|
'''loop until''' i + gap >= input'''.size''' ''//see [[Shell sort]] for similar idea''
|
|
'''if''' input[i] > input[i+gap]
|
|
'''swap'''(input[i], input[i+gap])
|
|
swaps := 1 ''// Flag a swap has occurred, so the''
|
|
''// list is not guaranteed sorted''
|
|
'''end if'''
|
|
i := i + 1
|
|
'''end loop'''
|
|
'''end loop'''
|
|
'''end function'''
|
|
<br><br>
|
|
|