How to implement comb sort in C++

Comb sort is a comparison-based algorithm that uses a gap of more than 1 to compare adjacent elements and move smaller values (turtles). It is an improved version of bubble sort. It was developed in 1980 by Włodzimierz Dobosiewicz and Artur Borowy, and named “comb sort” in 1991 by Stephen Lacey and Richard Box. The algorithm is called comb sort because it exhibits similarities to how a comb’s teeth align and separate hair strands.

The basic working of comb sort is to compare and swap elements at a certain gap and then decrease the gap gradually by a shrink factor. The authors of the comb sort algorithm found the value of shrink factor by testing their algorithm over 200,000 random arrays. The ideal value of the shrink factor is 1.3, which performs the best.

How to differentiate comb sort from bubble sort?

The comb sort will become a bubble sort if we set the gap to a fixed value of 1. The idea of a larger gap value is to remove the turtles (the smaller elements at the end of the array). The bubble sort only deals with rabbits (the larger elements at the start of the array). The gap in comb sort starts from the length of the array and decreases gradually. The gap value eventually becomes 1, which means that the algorithms perform similarly to the bubble sort, but by this point, the comb sort has sorted most of the turtles. So at the gap value of 1, the bubble sort performs efficiently.

Let’s visualize the working of the comb sort:

Algorithm

Let's go over the sequence of steps in the algorithm:

When to use comb sort?

Comb sort is a simple sorting algorithm that can be used in the following scenarios:

• When the array size is small.

• When stability is not important.

• When the array is partially sorted.

Implementation code

Let’s implement the comb sort in the following playground:

Code explanation

Let’s discuss the above code:

• Lines 5–7: We define some variables: gap, shrink, and swapped.

• Lines 9–20: We use the while loop to implement sorting. The loop will keep iterating until the gap value is not 1 or swapped is true.

  • Line 10: We update the gap value by dividing it by shrink. If the resultant value is less than 1, we set the value to 1.

  • Line 11: We set the swapped flag to false.

  • Lines 13–18: We use the for loop to iterate from 0 to n - gap to avoid the out-of-index error. We compare the i-th and i+gap values and swap them if required. We also set the swapped flag to true after the swapping of elements.

• Lines 23–28: We create an unsorted array and print it before sorting.

• Lines 30–34: We call the comb_sort() function and print the array after sorting.

Complexity

The time complexity of the comb sort algorithm is as follows:

• Best-case: The best-case time complexity of the comb sort is O(nlog⁡n)O(nlog⁡n).

• Worst-case: The worst-case time complexity of the comb sort is O(n2)O(n^2).

• Average-case: The average-case time complexity of the comb sort is Ω(n22p)\Omega(\frac{n^2}{2^p}), where p is the number of increments or passes. This means the average-case time complexity of the comb sort is asymptomatically lower than O(n2)O(n^2).

The comb sort performs the in-place sorting and does not require any extra space. Therefore, the space complexity of the comb sort is O(1)O(1).

Benefits and limitations

Let’s discuss some benefits and limitations of the comb sort algorithm.

Benefits

• Comb sort frequently outpaces alternative sorting algorithms with O(n2)O(n^2) time complexity, such as bubble and insertion sort.

• It is a space-efficient algorithm because it requires no extra space to sort.

• Its algorithm is simple and easy to implement.

Limitations

• Comb sort is not a stable sorting algorithm, which means that the order of equal elements is not guaranteed to be in the same order after sorting.

• The worst-case time complexity is O(n2)O(n^2), which means it can be slow for large arrays.

• The comb sort algorithm is sensitive to the shrink factor and performs differently on different values. If the shrink factor is a smaller number, the comb sort may be slow. If the shrink factor is too large, it will increase the comparisons.