How To Do Comb Sort in C++

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, which gradually shrinks as the sorting progresses. In this blog post, we 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 upon the performance of Bubble Sort 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 size of the array and shrink it.
• Iteration: Continue the process until the gap becomes 1 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 are made yet.

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 5 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 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 3 positions apart:

• Compare arr[0] (-44) and arr[3] (28): No swap.
• Compare arr[1] (4) and arr[4] (1): Swap.

Array after 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

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:

1. Small Datasets (1000 elements):
   • For random arrays, Comb Sort took 227.344 μs, while Bubble Sort took a significantly higher 5861.27 μs.
   • For sorted arrays, Comb Sort took 100.249 μs, whereas Bubble Sort took only 5.327 μs. Bubble Sort shines when the array is already 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.
2. 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.
   • For sorted arrays, Comb Sort took 509.407 μs, and Bubble Sort performed extremely well at 20.312 μs due to early termination.
   • For reverse sorted arrays, Comb Sort took 624.603 μs, whereas Bubble Sort took 126417 μs, once again struggling with the reverse order.
3. 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, the performance of Comb Sort remains higher than Bubble Sort 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.
   • For reverse sorted arrays, Comb Sort consistently performed better, taking 17915.8 μs compared to Bubble Sort’s 50.4223 seconds for 100,000 elements.

Key Takeaways:

1. 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.
2. Bubble Sort’s limitation: Bubble Sort’s performance degrades significantly as the dataset grows, particularly with random or reverse sorted data. Its O(n²) complexity in the worst case becomes very apparent with larger datasets.
3. Sorted Arrays Performance: Bubble Sort performs exceptionally well on sorted arrays due to early termination after detecting no swaps in the first pass. Comb Sort, while still efficient, does not benefit from early termination to the same extent as Bubble Sort.
4. 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:

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.

---

Advantages of Comb Sort

• Faster than Bubble Sort: Comb Sort eliminates far-out elements, or “turtles,” early in the sorting process by comparing elements that are 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, which is 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 don’t require the efficiency of more advanced algorithms. It’s particularly useful 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 very 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, go to 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++

Have fun and happy researching!