Comb sort is a comparison sorting algorithm. It is an exchange sort, similar to bubble sort.
In comb sort, gaps (distance of two items from each other) are introduced. The gap in bubble sort is 1. The gap starts out as a large value, and, after each traversal, the gap is lessened, until it becomes 1, where the algorithm basically degrades to a bubble sort. This idea can practically kill turtles because some of them would "jump" to the beginning of the list early on.
The shrink factor determines how much the gap is lessened. This value is crucial because a small value means that it would be slower for the gap to degrade to 1, slowing down the process, while a large value will not effectively kill turtles. An ideal shrink factor is 1.3.
Algorithm[]
comb_sort(list of t) gap = list.count temp as t swapped = false while gap > 1 or not swapped swapped = false if gap > 1 then gap = floor(gap/1.3) i = 0 while i + gap < list.count if list(i) > list(i + gap) temp = list(i) // swap list(i) = list(i + gap) list(i + gap) = temp i += 1
Example[]
Sorting the list: 5, 7, 9, 10, 3, 1, 4, 8, 2, 6. Shrink factor: 1.24:
- 57910314826
- Iteration 1. Gap = 8
- 27910314856
- 26910314857
- Iteration 2. Gap = 6
- 26910314857
- 26910314857
- 26510314897
- 26573148910
- Iteration 3. Gap = 4
- 26573148910
- 21573648910
- 21473658910
- 21473658910
- 21473658910
- 21473658910
- Iteration 4. Gap = 3
- 21473658910
- 21473658910
- 21473658910
- 21453678910
- 21453678910
- 21453678910
- 21453678910
- Iteration 5. Gap = 2
- 21453678910
- 21453678910
- 21354678910
- 21354678910
- 21354678910
- 21354678910
- 21354678910
- 21354678910
- Iteration 6. Gap = 1
- 12354678910
- 12354678910
- 12345678910
- 12345678910
- 12345678910
- 12345678910
- 12345678910
- 12345678910
- Iteration 7
Since the items are already sorted, no swaps will be made in this iteration and the algorithm ends.