FANDOM


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.

AlgorithmEdit

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

ExampleEdit

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.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.