Comb Sort

Sorting is one of the must known and well-used techniques in programming world. There are different sorting types with various run-time and space complexity. One of the initial sort technique is bubble sort. Today we will learn about Comb Sort which is not very popular. It is basically improvement of bubble sort.

Comb Sort

As I told above, Comb Sort is mainly an improvement over Bubble Sort. In bubble sort, when any two elements are compared, they always have a gap from each other of 1. The inner loop of bubble sort, which does the actual swap, is modified such that gap between swapped elements goes down in steps of a "shrink factor" Comb Sort improves on Bubble Sort by using gap of size more than 1. The gap starts with a large value and shrinks by a factor of 1.3 in every iteration until it reaches the value 1. Thus Comb Sort removes more than one inversion counts with one swap and performs better than Bublle Sort.The shrink factor has been empirically found to be 1.3. Although, it works better than Bubble Sort on average, worst case remains O(n2).

The pattern of repeated sorting passes with decreasing gaps is similar to Shellsort, but in Shellsort the array is sorted completely each pass before going on to the next-smallest gap. Comb sort's passes do not completely sort the elements. This is the reason that Shellsort gap sequences have a larger optimal shrink factor of about 2.2.

Algorithm

The mechanism of comb sort is as follows:

• Initialize gap with number of elements in array
• In a loop, check the next gap.
• find next gap with 1.3
• If the gap is less than or equal to 1 break the current loop
• otherwise swap elements in current gap

Lets see with example. Suppose our unsorted array is

A = (-22, 12, 4, 0, 25, -35)

So we can see the number of elements in this array is 6. So we start our inialize gap with 6.

First Gap

After shrinking with 1.3, our new gap value will be 6/1.3 = 4. So lets check in our array. start with the initial index 0. so the index to compare will be 0+4 = 4. We can see index 0, the value is -22 and at index 4, the value is 25. so no need to do any swap, in this case.

# compare index 0 and 4
before: A = (-22, 12, 4, 0, 25, -35)
after:  A = (-22, 12, 4, 0, 25, -35)

Now we increment our next index by 1. So the first index is now 1. And the index to compare will be 1 + 4 = 5. In the array, we can find out that at index 1, the value is 12 and at 5, the value is -35. here we need to swap there place as A(1) > A(5)

# compare index 1 and 5
before: A = (-22, 12, 4, 0, 25, -35)
after:  A = (-22, -35, 4, 0, 25, 12)

We will now move on by going to the next index. So like before, the first index will be 1 + 1 = 2. So the index to compare will be 2 + 4 = 6. But 5 is out of bound for our sorting array. So we will continue our sorting by finding the next gap.

Second Gap

In previous step our gap value was 4. We worked on that and then we needed to find new gap value. Now our next gap value will be 4/1.3 = 3. So lets start our business now. For first index 0, the camparable index will be 0+ 3 = 3. There is no need to do any swap because A(0) = -22 < A(3) = 0

# compare index 0 and 3
before: A = (-22, 12, 4, 0, 25, -35)
after:  A = (-22, -35, 4, 0, 25, 12)

In the second pass, the first index will be 1 and so the compared index will be 1+3 = 4. In this case also there is no need do any swap as A(1) = -35 < A(4) = 25

# compare index 1 and 4
before: A = (-22, 12, 4, 0, 25, -35)
after:  A = (-22, -35, 4, 0, 25, 12)

For nex compare, the first value is 2 and the comparable value is 2+3 = 5. And we need to keep it as it is because A(2) = 4 < A(5) = 12.

# compare index 2 and 5
before: A = (-22, 12, 4, 0, 25, -35)
after:  A = (-22, -35, 4, 0, 25, 12)

We now will go to the third gap as the next campared index(3+3 = 6) will be out of bound.

Third Gap

For this step our gap value will be 3/1.3 = 2. So starting with index 0, the comparable value will be 0+ 2= 2. And for this gap value we dont need any swap as A(0)<A(2), A(1)<A(3), A(2)<A(4) and A(3)<A(5). So we will go to our next gap value

# for gap value 2
before: A = (-22, -35, 4, 0, 25, 12)
after:  A = (-22, -35, 4, 0, 25, 12)

Fourth Gap

For this step the gap value will be 2/1.3 = 1. So this will be our last step and after this step we will get our desired sorted array. We can demonstrate this in below snippet

## for gap value 1

# for first index 0 and second index 1; A(0) > A(1), swap needed
before: A = (-22, -35, 4, 0, 25, 12)
after:  A = (-35, -22, 4, 0, 25, 12)

# for first index 1 and second index 2; A(1) < A(2), no swap needed
before: A = (-35, -22, 4, 0, 25, 12)
after:  A = (-35, -22, 4, 0, 25, 12)

# for first index 2 and second index 3; A(2) > A(3), swap needed
before: A = (-35, -22, 4, 0, 25, 12)
after:  A = (-35, -22, 0, 4, 25, 12)

# for first index 3 and second index 4; A(3) < A(4), no swap needed
before: A = (-35, -22, 0, 4, 25, 12)
after:  A = (-35, -22, 0, 4, 25, 12)

# for first index 4 and second index 5; A(4) > A(5), swap needed
before: A = (-35, -22, 0, 4, 25, 12)
after:  A = (-35, -22, 0, 4, 12, 25)

Thus we get our sorted array after doing comb sort which is A = (-35, -22, 0, 4, 12, 25)

Ruby Implementation

Following is the ruby implementation of comb sort

def comb_sort a
    gap = a.size
    while gap != 1 do
        gap = gap/1.3
        (0...a.size).each.do |n|
            break if n + gap >= a.size - 1
            a[n], a[n+gap] = a[n + gap], a[n] if a[n] > a[n+gap]
        end
    end
    a
end

I hope this general information will inspire you to more about comb sorting. I will come out with more in next. Thank you