The Comb Sort algorithm is a variation of the Bubble Sort algorithm designed to improve its performance. It works by comparing and swapping elements that are separated by a gap, gradually reducing the gap size until it becomes 1, at which point the algorithm behaves like a simple Bubble Sort.
Here’s how the Comb Sort algorithm works
Step 1: Start with an initial gap value. Common choices for the initial gap include the size of the input array or a fraction of it, such as 1.3.
Step 2: Compare elements that are separated by the current gap value and swap them if they are in the wrong order. Continue this process for the entire array.
Step 3: Reduce the gap value by a shrink factor (usually around 1.3) until it becomes 1.
Step 4: Repeat the comparisons and swaps with a gap of 1 until the entire array is sorted.
Step 1: Start with an initial gap value. Common choices for the initial gap include the size of the input array or a fraction of it, such as 1.3.
Step 2: Compare elements that are separated by the current gap value and swap them if they are in the wrong order. Continue this process for the entire array.
Step 3: Reduce the gap value by a shrink factor (usually around 1.3) until it becomes 1.
Step 4: Repeat the comparisons and swaps with a gap of 1 until the entire array is sorted.
combSort(array, n)
// n is the size of array
gap = n
// Initialize gap size equal to the size of array
shrink = 1.3 // gap shrink factor
swapped = true
while (gap ! = 1 || swapped = true)
gap = floor(gap/1.3);
if gap ≤ 1
gap = 1
end if
swapped = false
for every element range from
0 to n-gap, do the following -
if array[i] > array[i+gap]
swap(array[i], array[i+gap])
swapped = true
end if
end for loop
end while loop
end combSort
Example 1.
illustrate how Comb Sort works on this
Array: [8, 4, 1, 6, 2, 9, 5, 3, 7]
1.Initial gap = 9 (size of the array)
2. Compare and swap elements separated by the gap:
Gap = 9: [8, 4, 1, 6, 2, 9, 5, 3, 7]
Gap = 6: [8, 4, 1, 6, 2, 5, 9, 3, 7]
Gap = 4: [8, 4, 1, 5, 2, 6, 9, 3, 7]
Gap = 3: [8, 4, 1, 5, 2, 6, 3, 9, 7]
Gap = 2: [8, 4, 1, 5, 2, 6, 3, 7, 9]
3. Reduce the gap: 2 / 1.3 ≈ 1 (minimum gap is 1)
4. Continue sorting with gap = 1 using a standard Bubble Sort:
[4, 8, 1, 5, 2, 6, 3, 7, 9]
[4, 1, 8, 5, 2, 6, 3, 7, 9]
[1, 4, 5, 2, 6, 3, 7, 8, 9]
[1, 4, 2, 5, 3, 6, 7, 8, 9]
[1, 2, 4, 3, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
illustrate how Comb Sort works on this
Array: [8, 4, 1, 6, 2, 9, 5, 3, 7]
1.Initial gap = 9 (size of the array)
2. Compare and swap elements separated by the gap:
Gap = 9: [8, 4, 1, 6, 2, 9, 5, 3, 7]
Gap = 6: [8, 4, 1, 6, 2, 5, 9, 3, 7]
Gap = 4: [8, 4, 1, 5, 2, 6, 9, 3, 7]
Gap = 3: [8, 4, 1, 5, 2, 6, 3, 9, 7]
Gap = 2: [8, 4, 1, 5, 2, 6, 3, 7, 9]
3. Reduce the gap: 2 / 1.3 ≈ 1 (minimum gap is 1)
4. Continue sorting with gap = 1 using a standard Bubble Sort:
[4, 8, 1, 5, 2, 6, 3, 7, 9]
[4, 1, 8, 5, 2, 6, 3, 7, 9]
[1, 4, 5, 2, 6, 3, 7, 8, 9]
[1, 4, 2, 5, 3, 6, 7, 8, 9]
[1, 2, 4, 3, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Advantages Of Comb Sorting In Data Structure
Comb Sort is relatively easy to understand and implement. It shares similarities with Bubble Sort, making it accessible for those who are familiar with basic sorting algorithms.
Comb Sort improves on the basic Bubble Sort algorithm by eliminating small values faster. The “comb” technique gradually reduces the gap between elements, making it perform better than Bubble Sort on average.
Unlike some advanced sorting algorithms, Comb Sort doesn’t require external libraries or complex data structures to work effectively. It relies on basic comparisons and swaps.
Comb Sort’s performance can be adaptive to some extent. It works well for data that is partially ordered or nearly sorted. In such cases, it can approach linear time complexity.
The gap-shrinking factor can be adjusted based on the specific dataset and size. This adaptability allows you to fine-tune the algorithm for your particular use case.
