**Comb Sort** is a relatively simple yet efficient comparison-based sorting algorithm that improves upon Bubble Sort by eliminating turtles (small values near the end of the list) early in the sorting process. It introduces a gap between compared elements, gradually shrinking as the sorting progresses. This blog post will explain how Comb Sort works, provide a C++ implementation, and discuss its advantages and limitations compared to algorithms like Bubble Sort and Quick Sort.

## What is Comb Sort?

**Comb Sort** is a comparison-based sorting algorithm that improves Bubble Sort’s performance by introducing a larger gap between compared elements. It reduces this gap progressively until it converges to one, at which point it operates like Bubble Sort. This technique helps eliminate small values at the end of the list more quickly.

### Key Points about Comb Sort:

**Shrinking Factor**: Typically 1.3, controls how the gap between elements decreases.**Initial Gap**: Set to the size of the array.**Final Phase**: Acts as Bubble Sort when the gap shrinks to 1.

## Comb Sort Pseudocode

function combSort(arr): n = length of arr gap = n shrinkFactor = 1.3 sorted = false while gap > 1 or sorted is false: gap = max(1, int(gap / shrinkFactor)) sorted = true for i = 0 to n - gap: if arr[i] > arr[i + gap]: swap(arr[i], arr[i + gap]) sorted = false

**Initialize the Gap**: Start with the array size and shrink it.**Iteration**: Continue until the gap becomes one and the array is sorted.

## Time Complexity of Comb Sort

**Best Case**: O(n log n)**Average Case**: O(n² / 2^{p}), where*p*is the number of gaps.**Worst Case**: O(n²)

## Space Complexity of Comb Sort

Comb Sort uses **constant space** as it operates in place, resulting in a space complexity of **O(1)**.

## C++ Implementation of Comb Sort

Here’s a simple implementation of Comb Sort in C++:

#include <iostream> #include <vector> void combSort(std::vector<int>& arr) { int n = arr.size(); int gap = n; const float shrinkFactor = 1.3; bool sorted = false; while (gap > 1 || !sorted) { gap = std::max(1, int(gap / shrinkFactor)); sorted = true; for (int i = 0; i < n - gap; ++i) { if (arr[i] > arr[i + gap]) { std::swap(arr[i], arr[i + gap]); sorted = false; } } } } int main() { std::vector<int> arr = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0}; combSort(arr); for (int num : arr) { std::cout << num << " "; } return 0; }

## Step-by-Step Explanation of Comb Sort

Let’s break down how Comb Sort works for the array `[8, 4, 1, 56, 3, -44, 23, -6, 28, 0]`

.

### Step 1: Initialize the Gap

The initial gap is set to the length of the array, which is 10. We shrink the gap using the shrink factor (1.3), but no comparisons have been made.

**Initial array**:`[8, 4, 1, 56, 3, -44, 23, -6, 28, 0]`

### Step 2: Shrink the Gap

We reduce the gap: `int(10 / 1.3) = 7`

. Now, compare elements that are 7 positions apart:

- Compare
`arr[0] (8)`

and`arr[7] (-6)`

:**Swap**. - Compare
`arr[1] (4)`

and`arr[8] (28)`

: No swap. - Compare
`arr[2] (1)`

and`arr[9] (0)`

:**Swap**.

**Array after pass**:`[-6, 4, 0, 56, 3, -44, 23, 8, 28, 1]`

### Step 3: Shrink the Gap Again

New gap: `int(7 / 1.3) = 5`

.

Compare elements that are five positions apart:

- Compare
`arr[0] (-6)`

and`arr[5] (-44)`

:**Swap**. - Compare
`arr[1] (4)`

and`arr[6] (23)`

: No swap. - Compare
`arr[3] (56)`

and`arr[8] (28)`

:**Swap**.

**Array after the second pass**:`[-44, 4, 0, 28, 1, -6, 23, 8, 56, 3]`

### Step 4: Shrink the Gap Again

New gap: `int(5 / 1.3) = 3`

.

Compare elements that are three positions apart:

- Compare
`arr[0] (-44)`

and`arr[3] (28)`

: No swap. - Compare
`arr[1] (4)`

and`arr[4] (1)`

:**Swap**.

**Array after the third pass**:`[-44, 1, -6, 23, 4, 0, 3, 8, 56, 28]`

### Step 5: Shrink the Gap to 1

Final gap: 1. Perform adjacent comparisons like Bubble Sort:

- Compare
`arr[0] (-44)`

and`arr[1] (1)`

: No swap. - Compare
`arr[1] (1)`

and`arr[2] (-6)`

:**Swap**.

**Final sorted array**:`[-44, -6, 0, 1, 3, 4, 8, 23, 28, 56]`

## Comb Sort vs. Bubble Sort

Bubble Sort is well-known for its simplicity but performs poorly due to its O(n²) time complexity. Comb Sort, on the other hand, addresses one of Bubble Sort’s main inefficiencies—turtles (small values at the end of the list)—by introducing a shrinking gap between compared elements. This early elimination of turtles significantly improves sorting time, especially for larger datasets.

Now, let’s analyze the performance of these two algorithms on arrays of varying sizes and types (random, sorted, and reverse sorted).

The following code defines the functions for Comb Sort and Bubble Sort, then generates arrays of varying lengths (1000, 5000, 10000, and 100000) for testing the performance of the two algorithms. The arrays will be filled with random, sorted, and reverse sorted data for each size.

#include <iostream> #include <vector> #include <algorithm> // for std::swap and std::sort #include <chrono> // for performance measurement #include <cstdlib> // for rand and srand #include <ctime> // for seeding rand // Comb Sort function void combSort(std::vector<int>& arr) { int n = arr.size(); int gap = n; const float shrinkFactor = 1.3; bool sorted = false; while (gap > 1 || !sorted) { gap = std::max(1, int(gap / shrinkFactor)); sorted = true; for (int i = 0; i < n - gap; ++i) { if (arr[i] > arr[i + gap]) { std::swap(arr[i], arr[i + gap]); sorted = false; } } } } // Bubble Sort function void bubbleSort(std::vector<int>& arr) { int n = arr.size(); bool swapped; for (int i = 0; i < n - 1; i++) { swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); swapped = true; } } // If no elements were swapped in this iteration, break if (!swapped) break; } } // Function to generate random array std::vector<int> generateRandomArray(int size) { std::vector<int> arr(size); for (int i = 0; i < size; ++i) { arr[i] = rand() % 10000 - 5000; // random values between -5000 and 5000 } return arr; } // Function to generate sorted array std::vector<int> generateSortedArray(int size) { std::vector<int> arr = generateRandomArray(size); std::sort(arr.begin(), arr.end()); return arr; } // Function to generate reverse sorted array std::vector<int> generateReverseSortedArray(int size) { std::vector<int> arr = generateSortedArray(size); std::reverse(arr.begin(), arr.end()); return arr; } // Function to measure the time taken by a sorting algorithm and return the time in microseconds template <typename T> double measureSortingTime(void (*sortFunc)(std::vector<T>&), std::vector<T> arr) { auto start = std::chrono::high_resolution_clock::now(); sortFunc(arr); auto end = std::chrono::high_resolution_clock::now(); std::chrono::duration<double, std::micro> duration = end - start; return duration.count(); } int main() { // Seed the random number generator srand(static_cast<unsigned int>(time(0))); // Array sizes to test std::vector<int> sizes = {1000, 5000, 10000, 100000}; std::cout << "Array Size\tType\t\tComb Sort (μs)\tBubble Sort (μs)\n"; std::cout << "---------------------------------------------------------------\n"; for (int size : sizes) { // Generate random, sorted, and reverse sorted arrays std::vector<int> randomArr = generateRandomArray(size); std::vector<int> sortedArr = generateSortedArray(size); std::vector<int> reverseArr = generateReverseSortedArray(size); // Measure sorting times and print in tabular format double combRandomTime = measureSortingTime(combSort, randomArr); double bubbleRandomTime = measureSortingTime(bubbleSort, randomArr); std::cout << size << "\t\tRandom\t\t" << combRandomTime << "\t\t" << bubbleRandomTime << "\n"; double combSortedTime = measureSortingTime(combSort, sortedArr); double bubbleSortedTime = measureSortingTime(bubbleSort, sortedArr); std::cout << size << "\t\tSorted\t\t" << combSortedTime << "\t\t" << bubbleSortedTime << "\n"; double combReverseTime = measureSortingTime(combSort, reverseArr); double bubbleReverseTime = measureSortingTime(bubbleSort, reverseArr); std::cout << size << "\t\tReverse\t\t" << combReverseTime << "\t\t" << bubbleReverseTime << "\n"; } return 0; }

The following table summarizes the execution time for each case:

Array Size | Type | Comb Sort (μs) | Bubble Sort (μs) |
---|---|---|---|

1000 | Random | 227.344 | 5861.27 |

1000 | Sorted | 100.249 | 5.327 |

1000 | Reverse | 129.085 | 6008.39 |

5000 | Random | 1341.66 | 130816 |

5000 | Sorted | 509.407 | 20.312 |

5000 | Reverse | 624.603 | 126417 |

10000 | Random | 2665.8 | 500080 |

10000 | Sorted | 1115.49 | 39.742 |

10000 | Reverse | 1608.59 | 487396 |

100000 | Random | 28973.9 | 4.96512e+07 |

100000 | Sorted | 15659.4 | 406.929 |

100000 | Reverse | 17915.8 | 5.04223e+07 |

**Table 1: Performance comparison of Comb Sort and Bubble Sort across different array sizes and types (random, sorted, and reverse sorted)**

**Analysis of Results**

From the performance test results, it’s clear that **Comb Sort** significantly outperforms **Bubble Sort** on larger datasets, especially in cases where the data is randomly shuffled or reverse-sorted. Let’s break down the observations:

**Small Datasets (1000 elements)**:- For
**random arrays**, Comb Sort took**227.344 μs**, while Bubble Sort took a significantly higher**5861.27 μs**. - Comb Sort took
**100.249 μs for sorted arrays**, whereas Bubble Sort took only**5.327 μs**. Bubble Sort shines when the array is sorted because it can terminate early. - For
**reverse-sorted arrays**, Comb Sort took**129.085 μs**, while Bubble Sort struggled at**6008.39 μs**due to its O(n²) complexity in the worst case.

- For
**Medium Datasets (5000 elements)**:- For
**random arrays**, Comb Sort took**1341.66 μs**, whereas Bubble Sort took a massive**130816 μs**. The gap between the two algorithms widens significantly as the dataset size grows. - Comb Sort took
**509.407 μs for sorted arrays**, and Bubble Sort performed extremely well at**20.312 μs**due to early termination. - Comb Sort took
**624.603 μs for reverse sorted arrays**, whereas Bubble Sort took**126417 μs**, once again struggling with the reverse order.

- For
**Larger Datasets (10,000 and 100,000 elements)**:- For
**random arrays**with 10,000 elements, Comb Sort took**2665.8 μs**, while Bubble Sort took**500080 μs**. Similarly, for**100,000 elements**, Comb Sort took**28973.9 μs**, whereas Bubble Sort reached**49.6512 seconds**. - For
**sorted arrays**, Comb Sort’s performance remains higher than Bubble Sort’s for larger datasets, with Comb Sort taking**15659.4 μs**for 100,000 elements and Bubble Sort taking**406.929 μs**due to early termination. - Comb Sort consistently performed better for reverse sorted arrays, taking
**17915.8 μs**compared to Bubble Sort’s**50.4223 seconds**for 100,000 elements.

- For

**Key Takeaways**:

**Comb Sort’s efficiency**: Comb Sort is highly efficient for larger datasets, especially when the data is randomly shuffled or reverse sorted. It consistently outperforms Bubble Sort due to its gap-based element comparison, which reduces the number of comparisons needed early on.**Bubble Sort’s limitation**: Bubble Sort’s performance degrades significantly as the dataset grows, particularly with random or reverse-sorted data. In the worst case, its O(n²) complexity becomes very apparent with larger datasets.**Performance on Sorted Arrays**: Bubble Sort performs exceptionally well on sorted arrays due to its early termination after detecting no swaps in the first pass. While still efficient, Comb Sort does not benefit from early termination to the same extent as Bubble Sort.**Scalability**: As the size of the dataset increases, Comb Sort’s performance scales much better compared to Bubble Sort. For example, on a 100,000-element random array, Comb Sort took under 30 ms, whereas Bubble Sort took almost 50 seconds.

**Why and How Performance Testing Numbers Can Change for Comb Sort**

Performance testing numbers for **Comb Sort** can vary depending on several factors. Understanding these influences can help explain fluctuations in execution times:

**Hardware Specifications**:- The CPU’s architecture, clock speed, and available memory can greatly impact sorting times. A more powerful CPU with a higher clock speed or multiple cores will generally result in faster execution for Comb Sort, especially with larger datasets. Systems with faster memory access also improve sorting performance.

**System Load**:- The overall system load can affect Comb Sort’s performance. If other applications or background processes are running during the test, they may consume CPU or memory resources, leading to slower execution. Running tests on a lightly loaded system helps ensure more consistent and reliable results.

**Compiler Optimizations**:- Compiler optimization levels (e.g.,
`-O2`

or`-O3`

in GCC or Clang) can influence how fast Comb Sort runs. Higher optimization levels allow the compiler to optimize memory access, loop unrolling, and CPU instruction usage, which can lead to more efficient sorting. Running Comb Sort without these optimizations will likely result in slower execution.

- Compiler optimization levels (e.g.,
**Input Variations**:**Randomness**in the input data can also cause slight variations in performance. While Comb Sort generally performs well on random and reverse sorted arrays, small differences in the order of elements within these datasets can slightly impact the execution time. For example, certain random inputs may require more iterations to sort than others.

**Cache Effects**:- The size of the input array and how well it fits into the CPU’s cache can influence performance. Comb Sort, with its shrinking gap mechanism, can benefit from better cache locality when accessing elements that are spaced closer together in memory. Conversely, if the dataset is too large to fit into the cache, performance may degrade as the algorithm incurs more cache misses.

**Gap Shrinking Behavior**:- Comb Sort’s performance is sensitive to the
**gap shrink factor**used (commonly set to 1.3). Small changes in this factor can affect how quickly the algorithm converges to a sorted state. A larger shrink factor may reduce the number of passes but could result in less effective element comparisons, while a smaller shrink factor may increase the number of passes but lead to better sorting in each pass.

- Comb Sort’s performance is sensitive to the
**Input Size Scaling**:- For smaller datasets, the performance difference between Comb Sort and more advanced algorithms may not be as pronounced. However, as the size of the dataset increases, the effects of Comb Sort’s time complexity (which is better than Bubble Sort but worse than Quick Sort) become more apparent, especially in terms of execution time for large arrays.

**External System Variations**:- Differences in
**operating systems**,**file system usage**, or even the environment in which the test is conducted (such as virtualized systems) can cause small variations in timing. These factors are often beyond the algorithm’s control but can still lead to measurable changes in performance.

- Differences in

**Advantages of Comb Sort**

**Faster than Bubble Sort**: Comb Sort eliminates far-out elements, or “turtles,” early in the sorting process by comparing elements farther apart using a progressively shrinking gap. This results in fewer overall comparisons and quicker movement of small elements, making Comb Sort significantly faster than Bubble Sort, especially on unsorted or reverse-sorted arrays.**Simple to Implement and Understand**: Comb Sort builds on the logic of Bubble Sort, making it easy to grasp and implement, even for beginner programmers. The main difference lies in the gap-shrinking mechanism, a straightforward addition that enhances performance without drastically complicating the algorithm.

**Limitations of Comb Sort**

**Less Efficient Than Advanced Algorithms**: While Comb Sort is a clear improvement over Bubble Sort, it still falls short of more advanced algorithms like Quick Sort and Merge Sort. These algorithms have better average and worst-case time complexities, making them more suitable for large datasets where performance is critical.**Performance Degrades on Nearly Sorted Arrays**: Comb Sort doesn’t benefit as much from early termination on already sorted or nearly sorted arrays compared to algorithms like Bubble Sort, which can terminate early when no swaps are needed. This makes Comb Sort less efficient in scenarios where the data is almost sorted.

**When to Use Comb Sort**

**Ideal for Simplicity and In-Place Sorting**: Comb Sort is a good choice when you need a simple, in-place sorting algorithm that improves on Bubble Sort but doesn’t require the efficiency of more advanced algorithms. It’s handy for medium-sized datasets where the overhead of implementing and maintaining more complex algorithms is unnecessary.**Not Suitable for Large Datasets Where Performance Is Critical**: For large datasets or applications requiring optimal performance, algorithms like Quick Sort or Merge Sort should be preferred, as they offer significantly better scalability and efficiency.

**Conclusion**

Comb Sort provides a practical improvement over Bubble Sort by introducing a gap-shrinking mechanism that accelerates the sorting of unsorted and reverse-sorted arrays. While it’s not as fast as more advanced algorithms like Quick Sort or Merge Sort, its simplicity, ease of implementation, and ability to perform in-place sorting make it a solid choice for smaller to medium-sized datasets where simplicity and ease of use are prioritized.

Congratulations on reading to the end of this tutorial!

To learn how to implement Comb Sort In Python, read the article: How To Do Comb Sort in Python.

For further reading on sorting algorithms in C++, go to the articles:

- Shell Sort in C++
- How To Do Selection Sort in C++
- How To Do Insertion Sort in C++
- How To Do Radix Sort in C++
- How To Do Bucket Sort in C++

Have fun and happy researching!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.