Comb Sort
 Comb Sort Algorithm
 Comb Sort Example
 Comb Sort Algorithm Implementation
 Comb Sort Algorithm Complexity
Comb sort is a simple comparisonbased 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 variableswapped
astrue
. 
Declare the constant variable
SHRINK_FACTOR
as1.3
. 
While the
gap
is not 1 orswapped
is set totrue
do the following:
Set
swapped
asfalse
. 
Set
gap
as(int)gap/SHRINK_FACTOR
. 
For every element in the range
0
ton  gap
do the following  ifA[i]
>A[i+gap]
,swap(A[i], A[i+gap])
and setswapped
totrue
.

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
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
= 6/1.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
= 4/1.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
= 3/1.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
= 2/1.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(n^{2}/2^{p}) where p
is the number of increments.
 Worst Case
The worstcase time complexity is [Big O]: O(n^{2}).
 Best Case
The bestcase occurs when the array is already sorted or nearly sorted. The bestcase time complexity is [Big Omega]: O(nlogn)
. It is a significant improvement over the bestcase 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.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn