Comb sort — code

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

26510314897

26573148910

Iteration 3. Gap = 4

26573148910

21573648910

21473658910

Iteration 4. Gap = 3

21473658910

21453678910

Iteration 5. Gap = 2

21453678910

21354678910

Iteration 6. Gap = 1

12354678910

12345678910

Iteration 7

Since the items are already sorted, no swaps will be made in this iteration and the algorithm ends.