Comb Sort Algorithm

Introduction to Comb Sort

Comb sort is an improvement over bubble sort. It eliminates small values near the end of the list that slow down the sorting process. Comb sort works by comparing and swapping elements separated by a gap, which reduces progressively until the list is sorted. The algorithm aims to reduce the number of comparisons by jumping over multiple elements in each pass.

---

Step-by-Step Process

Consider an array with the following elements:

[8, 4, 1, 56, 3, -44, 23, -6, 28, 0]

To sort this array using comb sort, follow these steps:

1. Initialize Gap: Set the initial gap to the length of the array divided by 1.3 (Shrink factor). Continue until the gap is 1.
2. Compare and Swap: Compare elements that are a gap distance apart. If they are out of order, swap them.
3. Reduce Gap: Reduce the gap for the next pass. Typically, the gap is divided by 1.3.
4. Repeat: Repeat the process until the gap is 1 and the array is sorted.

Let's apply these steps to the example array:

• Initial gap: 10 / 1.3 = 7
• First Pass with gap 7: [8, 4, 1, 56, 3, -44, 23, -6, 28, 0] -> [8, 4, 1, -6, 3, -44, 23, 56, 28, 0]
• Second Pass with gap 5: [8, 4, 1, -6, 3, -44, 23, 56, 28, 0] -> [8, 4, 1, -6, 0, -44, 23, 56, 28, 3]
• Third Pass with gap 3: [8, 4, 1, -6, 0, -44, 23, 56, 28, 3] -> [8, 4, -44, -6, 0, 1, 23, 56, 28, 3]
• Fourth Pass with gap 2: [8, 4, -44, -6, 0, 1, 23, 56, 28, 3] -> [8, -6, -44, 0, 4, 1, 23, 3, 28, 56]
• Fifth Pass with gap 1: [8, -6, -44, 0, 4, 1, 23, 3, 28, 56] -> [-6, -44, 0, 1, 3, 4, 8, 23, 28, 56]

---

Pseudo Code for Comb Sort

Below is the pseudo code for the comb sort algorithm:

function combSort(array)
    n = length(array)
    gap = n
    shrink = 1.3
    sorted = false
    while not sorted do
        gap = floor(gap / shrink)
        if gap <= 1 then
            gap = 1
            sorted = true
        end if
        i = 0
        while i + gap < n do
            if array[i] > array[i + gap] then
                swap(array[i], array[i + gap])
                sorted = false
            end if
            i = i + 1
        end while
    end while
end function

Explanation:

• Initialize: The function starts by determining the length of the array and setting the initial gap to n. The shrink factor is typically set to 1.3.
• Gap Reduction: The gap is reduced by dividing it by the shrink factor. If the gap becomes less than or equal to 1, it is set to 1, and the sorted flag is set to true.
• Comparison and Swap: Elements separated by the current gap are compared and swapped if they are out of order. If a swap occurs, the sorted flag is set to false.
• Repeat: The process repeats until the gap is 1 and the array is sorted.

---

Python Program to Implement Comb Sort

def comb_sort(arr):
    n = len(arr)
    gap = n
    shrink = 1.3
    sorted = False

    while not sorted:
        gap = int(gap / shrink)
        if gap <= 1:
            gap = 1
            sorted = True
        i = 0
        while i + gap < n:
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                sorted = False
            i += 1
    return arr

# Example usage:
array = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0]
print("Original array:", array)
sorted_array = comb_sort(array)
print("Sorted array:", sorted_array)  # Output: [-44, -6, 0, 1, 3, 4, 8, 23, 28, 56]

This Python program defines a function to perform comb sort on an array. The function initializes the gap and progressively reduces it while comparing and swapping elements until the array is sorted.