Comb Sort

  1. Comb Sort Algorithm
  2. Comb Sort Example
  3. Comb Sort Algorithm Implementation
  4. Comb Sort Algorithm Complexity

Comb sort is a simple comparison-based sorting algorithm. It is an improved form of bubble sort. In bubble sort, adjacent elements are compared in each pass/phase and remove inversions one by one. On the other hand, comb sort starts by using a large gap and reduce it every time by a shrink factor of 1.3. Comb Sort can remove multiple inversions with only one swap. It is based on the idea of killing the turtles. Turtles are the small elements toward the end of the list, which reduces the efficiency of bubble sort and killing them improves sorting performance significantly.

Comb Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements. We will take the shrink factor as 1.3 because it has been empirically found to give the best results.

  • Initialize variable gap as the size of the array and variable swapped as true.
  • Declare the constant variable SHRINK_FACTOR as 1.3.
  • While the gap is not 1 or swapped is set to true do the following:
    • Set swapped as false.
    • Set gap as (int)gap/SHRINK_FACTOR.
    • For every element in the range 0 to n - gap do the following - if A[i] > A[i+gap], swap(A[i], A[i+gap]) and set swapped to true.

Comb Sort Example

Suppose we have the array: (3, 5, 2, 8, 1, 7, 6, 4). We will sort it using the Comb sort algorithm.

Initialize gap=8 , swapped=true and SHRINK_FACTOR = 1.3.

  • The First Pass

gap = 81.3 = 6 , swapped = false

Iteration (3, 5, 2, 8, 1, 7, 6, 4) Action
i = 0 (3, 5, 2, 8, 3, 7, 6, 4) 3 < 6, No swap
i = 1 (3, 4, 2, 8, 1, 7, 6, 5) 5 > 4, Swapped
  • The Second Pass

gap = 61.3 = 4 , swapped = false

Iteration (3, 4, 2, 8, 1, 7, 6, 5) Action
i = 0 (1, 4, 2, 8, 3, 7, 6, 5) 3 > 1, Swapped
i = 1 (1, 4, 2, 8, 3, 7, 6, 5) 4 < 7, No swap
i = 2 (1, 4, 2, 8, 3, 7, 6, 5) 2 < 6, No swap
i = 3 (1, 4, 2, 5, 3, 7, 6, 8) 8 > 5, Swapped
  • The Third Pass

gap= 41.3 = 3 , swapped = false

Iteration (1, 4, 2, 5, 3, 7, 6, 8) Action
i = 0 (1, 4, 2, 5, 3, 7, 6, 8) 1 < 5, No swap
i = 1 (1, 3, 2, 5, 4, 7, 6, 8) 4 > 3, Swapped
i = 2 (1, 3, 2, 5, 4, 7, 6, 8) 2 < 7, No swap
i = 3 (1, 3, 2, 5, 4, 7, 6, 8) 5 < 6, No swap
i = 4 (1, 3, 2, 5, 4, 7, 6, 8) 4 < 8, No swap
  • The Fourth Pass

gap = 31.3 = 2 , swapped = false

Iteration (1, 3, 2, 5, 4, 7, 6, 8) Action
i = 0 (1, 3, 2, 5, 4, 7, 6, 8) 1 < 2, No swap
i = 1 (1, 3, 2, 5, 4, 7, 6, 8) 3 < 5, No swap
i = 2 (1, 3, 2, 5, 4, 7, 6, 8) 2 < 4, No swap
i = 3 (1, 3, 2, 5, 4, 7, 6, 8) 5 < 7, No swap
i = 4 (1, 3, 2, 5, 4, 7, 6, 8) 4 < 6, No swap
i = 5 (1, 3, 2, 5, 4, 7, 6, 8) 7 < 8, No swap
  • The Fifth Pass

gap = 21.3 = 1 , swapped = false

Iteration (1, 3, 2, 5, 4, 7, 6, 8) Action
i = 0 (1, 3, 2, 5, 4, 7, 6, 8) 1 < 3, No swap
i = 1 (1, 2, 3, 5, 4, 7, 6, 8) 3 > 2, Swapped
i = 2 (1, 2, 3, 5, 4, 7, 6, 8) 3 < 5, No swap
i = 3 (1, 2, 3, 4, 5, 7, 6, 8) 5 > 4, Swapped
i = 4 (1, 2, 3, 4, 5, 7, 6, 8) 5 < 7, No swap
i = 5 (1, 2, 3, 5, 4, 6, 7, 8) 7 > 6, Swapped
i = 6 (1, 2, 3, 4, 5, 6, 7, 8) 7 < 8, No swap

We get the final sorted array as: (1, 2, 3, 4, 5, 6, 7, 8).

Comb Sort Algorithm Implementation

#include <iostream>
using namespace std;

int updateGap(int gap)
{
    gap = (gap * 10) / 13;
    if (gap < 1)
        return 1;
    else
        return gap;
}

void combSort(int arr[], int n)
{
    int gap = n;
    bool swapped = true;
    while (gap > 1 || swapped == true)
    {
        gap = updateGap(gap);
        swapped = false;
        for (int i = 0; i < (n - gap); i++)
        {
            int temp;
            if (arr[i] > arr[i + gap])
            {
                temp = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = temp;
                swapped = true;
            }
        }
    }
}

int main() {

    int n = 6;
    int arr[6] = {5, 3, 4, 2, 1, 6};
    cout << "Input array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    combSort(arr, n);
    cout << "Output array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

Comb Sort Algorithm Complexity

Time Complexity

  • Average Case

The time complexity is of the order of [Big Theta]: O(n2/2p) where p is the number of increments.

  • Worst Case

The worst-case time complexity is [Big O]: O(n2).

  • Best Case

The best-case occurs when the array is already sorted or nearly sorted. The best-case time complexity is [Big Omega]: O(nlogn). It is a significant improvement over the best-case time complexity of bubble sort.

Space Complexity

Space Complexity for this algorithm is O(n) because the comb sort algorithm requires no additional space other than temporary variables.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Sort Algorithm

  • Tree Sort
  • Heap Sort