Explore
Placement Prep

Edit

Edit

# Comb Sort

Published on 07 Mar 2020

Comb Sort is an improvised version of bubble sort. The basic idea in comb sort is to eliminate the relatively smaller values situated to the end of the list. This is done as applying bubble sort on such an array would highly slow down the process. In bubble sort, adjacent elements are compared and swapped if necessary to state them in a sorted order. The gap between elements being compared in bubble sort is 1. However, comb sort aims to improvise in this stage by allowing to compare elements with a gap much more than 1. The internal program in bubble sort which swaps the elements is modified such that gap between the swapped elements goes down on each iteration of the outer loop with respect to a shrink factor 'k'. The value of k is generally set to 1.3 for better performance of comb sort.

Once the shrink factor is applied, the list is sorted with the new gap and further the process of reducing the gap is continued. The final stage obtained through this have most of their smaller elements towards the end of the list eliminated. Therefore, at this stage bubble sort can be implemented to reach the final sorted matrix.

The worst-case scenario of comb sort is similar to bubble sort having O(n^2). Below is C++, Java and Python implementation of comb sort.

## C++ implementation of Comb Sort

// C++ implementation of Comb Sort
#include<bits/stdc++.h>
using namespace std;

// To find gap between elements
int getNextGap(int gap)
{
// Shrink gap by Shrink factor
gap = (gap*10)/13;

if (gap < 1)
return 1;
return gap;
}

// Function to sort a[0..n-1] using Comb Sort
void combSort(int a[], int n)
{
// Initialize gap
int gap = n;

// Initialize swapped as true to make sure that loop runs
bool swapped = true;

// Keep running while gap is more than 1 and last iteration caused a swap
while (gap != 1 || swapped == true)
{
// Find next gap
gap = getNextGap(gap);

// Initialize swapped as false so that we can check if swap happened or not
swapped = false;

// Compare all elements with current gap
for (int i=0; i<n-gap; i++)
{
if (a[i] > a[i+gap])
{
swap(a[i], a[i+gap]);
swapped = true;
}
}
}
}

int main()
{
int a[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
int n = sizeof(a)/sizeof(a[0]);

combSort(a, n);

printf("Sorted array: \n");
for (int i=0; i<n; i++)
printf("%d ", a[i]);

return 0;
}


## Java implementation of Comb sort

// Java program for implementation of Comb Sort
class CombSort
{
// To find gap between elements
int getNextGap(int gap)
{
// Shrink gap by Shrink factor
gap = (gap*10)/13;
if (gap < 1)
return 1;
return gap;
}

// Function to sort arr[] using Comb Sortvoid sort(int arr[])
{
int n = arr.length;

// initialize gap
int gap = n;

// Initialize swapped as true to make sure that loop runs
boolean swapped = true;

// Keep running while gap is more than 1 and last iteration caused a swapwhile (gap != 1 || swapped == true)
{
// Find next gap
gap = getNextGap(gap);

// Initialize swapped as false so that we can check if swap happened or not
swapped = false;

// Compare all elements with current gapfor (int i=0; i<n-gap; i++)
{
if (arr[i] > arr[i+gap])
{
// Swap arr[i] and arr[i+gap]
int temp = arr[i];
arr[i] = arr[i+gap];
arr[i+gap] = temp;

// Set swapped
swapped = true;
}
}
}
}

public static void main(String args[])
{
CombSort ob = new CombSort();
int arr[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
ob.sort(arr);

System.out.println("sorted array");
for (int i=0; i<arr.length; ++i)
System.out.print(arr[i] + " ");

}
}


## Python implementation of Comb sort

# To find next gap from current
def getNextGap(gap):

# Shrink gap by Shrink factor
gap = (gap * 10)/13if gap < 1:
return 1return gap

# Function to sort arr[] using Comb Sort
def combSort(arr):
n = len(arr)

# Initialize gap
gap = n

# Initialize swapped as true to make sure that loop runs
swapped = True

# Keep running while gap is more than 1 and last iteration caused a swapwhile gap !=1 or swapped == 1:

# Find next gap
gap = getNextGap(gap)

# Initialize swapped as false so that we can check if swap happened or not
swapped = False

# Compare all elements with current gapfor i in range(0, n-gap):if arr[i] > arr[i + gap]:
arr[i], arr[i + gap]=arr[i + gap], arr[i]
swapped = True

# Driver code to test above
arr = [ 8, 4, 1, 3, -44, 23, -6, 28, 0]
combSort(arr)

print ("Sorted array:")
for i in range(len(arr)):
print (arr[i])


Output :

 Sorted array: -44 -6 0 1 3 4 8 23 28 56


Illustration:

Let the array elements be

8, 4, 1, 56, 3, -44, 23, -6, 28, 0


Initially gap value = 10

After shrinking gap value => 10/1.3 = 7;

 8 4 1 56 3 -44 23 -6 28 0-6 4 1 56 3 -44 23  8 28 0-6 4 0 56 3 -44 23  8 28 1


New gap value => 7/1.3 = 5;

-44 4 0 56 3 -6 23 8 28 1-44 4 0 28 3 -6 23 8 56 1-44 4 0 28 1 -6 23 8 56 3


New gap value => 5/1.3 = 3;

-44 1  0 28 4 -6 23 8 56 3-44 1 -6 28 4  0 23 8 56 3-44 1 -6 23 4  0 28 8 56 3-44 1 -6 23 4  0  3 8 56 28


New gap value => 3/1.3 = 2;

-44 1 -6 0 4 23 3 8 56 28-44 1 -6 0 3 23 4 8 56 28-44 1 -6 0 3 8 4 23 56 28


New gap value => 2/1.3 = 1;

-44 -6 1 0 3 8 4 23 56 28-44 -6 0 1 3 8 4 23 56 28-44 -6 0 1 3 4 8 23 56 28-44 -6 0 1 3 4 8 23 28 56 no more swaps required (Array sorted)


Time complexity is O(n^2) in the worst case and O(n) in the best case scenario.

Auxiliary Space: O(1).