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.

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 = 8/1.3 = 6 , swapped = false

• The Second Pass

gap = 6/1.3 = 4 , swapped = false

• The Third Pass

gap= 4/1.3 = 3 , swapped = false

• The Fourth Pass

gap = 3/1.3 = 2 , swapped = false

• The Fifth Pass

gap = 2/1.3 = 1 , swapped = false

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(n²/2^p) where p is the number of increments.

• Worst Case

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

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