C++ Program To Perform Comb Sort On Array Of Integers

Sorting algorithms are fundamental in computer science, optimizing how data is arranged for efficient processing. In this article, you will learn how to implement the Comb Sort algorithm in C++ to efficiently sort an array of integers.

Problem Statement

Efficiently sorting large datasets is a common challenge in programming. While simple algorithms like Bubble Sort are easy to understand, their performance degrades significantly with larger inputs due to their high time complexity (O(N^2)). This inefficiency often leads to bottlenecks in applications requiring fast data retrieval or ordered processing.

Example

Consider an unsorted array: [8, 4, 1, 5, 9, 2] After applying Comb Sort, the array will be sorted as: [1, 2, 4, 5, 8, 9]

Background & Knowledge Prerequisites

To understand and implement Comb Sort, you should have a basic grasp of:

• C++ Fundamentals: Variables, data types, loops (for, while), conditional statements (if-else).
• Arrays: Declaring, initializing, and accessing elements in one-dimensional arrays.
• Functions: Defining and calling functions in C++.
• Swapping Elements: The mechanism to exchange values between two variables.

Use Cases or Case Studies

Comb Sort offers an improvement over simpler quadratic sorting algorithms, making it suitable for certain scenarios:

• Improving on Bubble Sort: When an existing system uses Bubble Sort, replacing it with Comb Sort can provide a significant performance boost without dramatically altering the algorithm's core "comparison and swap" logic.
• Nearly Sorted Data with Outliers: Comb Sort is particularly effective at "combing out" small values at the end of a list or large values at the beginning, which often cripple algorithms like Bubble Sort (the "turtle" problem).
• Educational Context: It serves as an excellent example of how a simple modification (introducing a shrinking gap) can dramatically improve an algorithm's efficiency, bridging the gap between basic sorts and more complex ones like Quick Sort.
• Smaller Datasets: For moderately sized arrays where simplicity is preferred over the absolute fastest algorithm (like Merge Sort or Quick Sort), Comb Sort provides a good balance of performance and ease of implementation.

Solution Approaches

The core idea of Comb Sort is to eliminate "turtles" — small values near the end of the list that move very slowly towards the beginning during a Bubble Sort. It achieves this by using a "gap" that shrinks over time, allowing elements to be compared and swapped over larger distances initially.

Implementing Comb Sort

Comb Sort improves Bubble Sort by using a gap greater than 1. This gap is reduced by a "shrink factor" (typically 1.3) in each pass until it becomes 1, at which point it behaves like a Bubble Sort, ensuring full sorting.

// Comb Sort on Array of Integers
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

// Function to perform Comb Sort
void combSort(std::vector<int>& arr) {
    int n = arr.size();
    
    // Initialize gap
    int gap = n;
    
    // Initialize swapped flag for the outer loop (to check if any swaps happened)
    bool swapped = true;

    // Loop until gap becomes 1 and no more swaps occur
    while (gap != 1 || swapped == true) {
        // Update gap for the next pass
        // A common shrink factor is 1.3
        gap = (int)(gap / 1.3);
        if (gap < 1) {
            gap = 1; // Ensure gap is at least 1
        }
        
        swapped = false; // Reset swapped flag for this pass
        
        // Perform a "bubble sort" pass with the current gap
        for (int i = 0; i < n - gap; ++i) {
            if (arr[i] > arr[i + gap]) {
                std::swap(arr[i], arr[i + gap]);
                swapped = true; // Indicate that a swap occurred
            }
        }
    }
}

int main() {
    // Step 1: Define an array of integers to be sorted
    std::vector<int> numbers = {8, 4, 1, 5, 9, 2, 7, 3, 6};

    // Step 2: Print the original array
    std::cout << "Original array: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Step 3: Call the combSort function to sort the array
    combSort(numbers);

    // Step 4: Print the sorted array
    std::cout << "Sorted array (Comb Sort): ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Original array: 8 4 1 5 9 2 7 3 6 
Sorted array (Comb Sort): 1 2 3 4 5 6 7 8 9

Stepwise Explanation:

1. combSort Function: This function takes a std::vector by reference, allowing it to modify the original array.
2. Initialize gap: The gap is initially set to the size of the array (n). This means the first comparisons will be between elements far apart.
3. Initialize swapped: A boolean swapped flag is used to track if any swaps occurred in a pass. This is crucial for the final phase when gap becomes 1; if no swaps occur, the array is sorted.
4. Outer while Loop: This loop continues as long as the gap is greater than 1 or if swaps were made in the previous pass (even if gap is 1).
5. Shrink Gap: In each iteration of the outer loop, the gap is reduced by dividing it by a shrink factor (1.3). If the calculated gap becomes less than 1, it's set to 1 to ensure that elements are compared directly.
6. Inner for Loop: This loop iterates through the array, comparing arr[i] with arr[i + gap].
7. Comparison and Swap: If arr[i] is greater than arr[i + gap], their positions are swapped using std::swap, and the swapped flag is set to true.
8. Termination: The process continues until the gap is 1 and a full pass occurs without any swaps, indicating the array is completely sorted.

Conclusion

Comb Sort is an efficient comparison-based sorting algorithm that addresses the "turtle" problem of Bubble Sort by using a decreasing gap. It offers a good balance between simplicity and performance, particularly for arrays where Bubble Sort struggles. Its average-case time complexity is approximately O(N log N), making it a viable option for many sorting tasks.

Summary

• Comb Sort is an improvement over Bubble Sort, primarily by eliminating "turtles" (small elements at the end, large elements at the start).
• It uses a gap that shrinks over time, typically by a factor of 1.3, allowing comparisons over longer distances initially.
• The algorithm ends with a gap of 1, effectively becoming a Bubble Sort for the final passes to ensure complete sorting.
• Its average-case performance is significantly better than Bubble Sort, approaching O(N log N) but with a simpler implementation than more advanced sorts.
• Suitable for situations requiring a moderately efficient sort that is easy to understand and implement.