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:

#include <iostream>
using namespace std;
void comb_sort(int arr[], int n){
  int gap = n;
  float shrink = 1.3;
  bool swapped = true;
  while (gap != 1 || swapped){
    gap = (gap/shrink < 1.0) ? 1 : gap/shrink;
    swapped = false;
    for(int i = 0; i < n - gap; i++){
      if(arr[i] > arr[i+gap]){
        std::swap(arr[i], arr[i+gap]);
        swapped = true;
      }
    }
  }
}
int main() {
  int arr[] = {15, 13, 24, 7, 18, 3, 22, 9};
  int n = sizeof(arr) / sizeof(arr[0]);
  std::cout << "Unsorted Array: ";
  for (int i = 0; i < n; ++i) {
    std::cout << arr[i] << " ";
  }
  
  comb_sort(arr, n);
  std::cout << "\nSorted Array: ";
  for (int i = 0; i < n; ++i) {
    std::cout << arr[i] << " ";
  }
  return 0;
}

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)$ .
Worst-case: The worst-case time complexity of the comb sort is $O(n^2)$ .
Average-case: The average-case time complexity of the comb sort is $\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(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)$ .

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(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(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.

Unlock your potential: Sorting algorithms series – all in one place!

To continue your exploration of sorting algorithms, check out our series of Answers below:

What are sorting algorithms?
Understand the fundamentals of sorting algorithms and their role in organizing data efficiently.
What is tree sort?
Learn how tree-based structures can be used to sort elements efficiently.
What is Bitonic sort?
Discover Bitonic Sort, a parallel sorting algorithm ideal for hardware implementations.
What is Flash Sort?
Explore Flash Sort, a hybrid sorting technique designed for fast performance on large datasets.
How to implement the pigeonhole sorting algorithm in Python
A step-by-step guide to implementing Pigeonhole Sort in Python for efficient data sorting.
How to implement comb sort in C++
Learn how to implement Comb Sort in C++ to improve sorting efficiency over Bubble Sort.
Implementation of the cocktail sort in C++
Understand how Cocktail Sort refines Bubble Sort for bidirectional sorting in C++.
How to implement cocktail sort in Python
Implement Cocktail Sort in Python to enhance sorting performance with a two-way pass.
How to implement Gnome sort in C++
Explore the simplicity of Gnome Sort and its implementation in C++.
How to implement pancake sort in Java?
Learn how to implement Pancake Sort in Java, inspired by flipping pancakes to sort stacks.
Comparison of linear-time sorting algorithms
Analyze and compare different linear-time sorting algorithms to understand their efficiency.

Free Resources