Comb Sort


Reading time: 30 minutes | Coding time: 12 minutes

Comb sort is a comparison based sorting algorithm and is an improvement to Bubble Sort by using the idea of killing the turtles. Turtle is a name given to small numbers that appear towards the end of a list. When used in a Bubble Sort, these small numbers at the end take a very long time to get to the front of the list, and hence are called turtles because of the lack of speed. Turtles reduce the efficiency of the Bubble Sort tremendously and hence provide a scope for optimisation.

In Bubble Sort algorithm, the gap between the elements that are compared is always 1. Comb sort works on the same principles as Bubble Sort but uses a larger gap. The inner loop of bubble sort, where swaps happen, is modified such that gap between swapped elements decreases by a shrink factor k for each iteration of outer loop. This shrink factor is usually taken as 1.3. This constant has been found by the authors Stephen Lacey and Richard Box by testing Comb sort on over 200,000 random lists.The iteration continues till the gap becomes 1. So the last iteration of this algorithm is same as a bubble sort iteration.

Algorithm

The algorithm of Comb sort is as follows:

  1. Create and initialise variables gap and swapped and constant SHRINK_FACTOR
    a) gap = size of the array
    b) swapped = false
    c) SHRINK_FACTOR = 1.3
  2. Set swapped = false
  3. Set gap = gap/SHRINK_FACTOR
  4. Iterate over the array from i = 0 to i < n - gap:
    if array[i] > array[i + gap]
    a) swap the elements array[i] and array[i + gap]
    b) set swapped = true
  5. Repeat steps 2-4 while gap != 1 and swapped = true

Complexity

  • Worst case time complexity: O(N2)
  • Average case time complexity: Ω(N2/2p), where p is the number of increments
  • Best case time complexity: Θ(N log N)
  • Space complexity: Θ(1) auxillary space
In best case scenario, Comb Sort performs at O(n logn) time complexity. This creates a drastic improvement over Bubble Sort's performance.

Example


Initial array (7, 5, 1, 50, 3, -20, 25, -4, 30, 0)
Initial Gap value = 10
Constant k = 1.3

1st pass:
After update, gap value = 10/1.3 = 7
7 5 1 50 3 -20 25 -4 30 0
-4 5 1 50 3 -20 25 7 30 0
-4 5 0 50 3 -20 25 7 30 1

2nd pass:
After update, gap value = 7/1.3 = 5
-4 5 0 50 3 -20 25 7 30 1
-20 5 0 50 3 -4 25 7 30 1
-20 5 0 30 3 -4 25 7 50 1
-20 5 0 30 1 -4 35 7 50 3

3rd pass:
After update, gap value = 5/1.3 = 3
-20 5 0 50 3 -4 25 7 30 1
-20 3 0 50 5 -4 25 7 30 1
-20 3 -4 30 5 0 25 7 50 1
-20 3 -4 25 5 0 30 7 50 1
-20 3 -4 25 5 0 1 7 50 30

4th pass:
After update, gap value = 3/1.3 = 2
-20 3 -4 25 5 0 30 7 50 1
-20 3 -4 0 5 25 1 7 50 30
-20 3 -4 0 1 25 5 7 50 30
-20 3 -4 0 1 7 5 25 50 30

5th pass:
After update, gap value = 2/1.3 = 1
-20 3 -4 0 1 7 5 25 50 30
-20 -4 3 0 1 7 5 25 50 30
-20 -4 0 3 1 7 5 25 50 30
-20 -4 0 1 3 7 5 25 50 30
-20 -4 0 1 3 5 7 25 50 30
-20 -4 0 1 3 5 7 25 30 50 Array Sorted

Is Comb Sort an in-place sorting algorithm?

Yes
No
Comb Sort is an in-place sorting algorithm as it does not require any additional space for sorting the lists.

Implementations

Implementation of Comb sort algorithm in 4 languages that includes C++, Java, Python and Go.

  • C++
  • Java
  • Python
  • Go

C++


// C++ Code for Comb Sort 
#include <iostream>
using namespace std;
// function to update gap value
int updateGap(int gap)
{ 
// Shrink gap by the shrink factor 
  gap = (gap * 10) / 13;
  if (gap < 1)
    return 1;
  else
    return gap;
}
// Function to sort arr[] using Comb Sort 
void combSort(int arr[], int n) 
{
  // initialize gap 
  int gap = n;
  // Initialize swapped as true to make sure that the loop runs 
  bool swapped = true;
  while (gap > 1 || swapped == true)
  {
    // Update gap value
    gap = updateGap(gap);
    swapped = false;
    // Compare all elements with current gap 
    for (int i = 0; i < (n - gap); i++)
    {
      int temp;
      if (arr[i] > arr[i + gap])
      {
        // Swap arr[i] and arr[i+gap] 
        temp = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = temp;
        swapped = true;
      }
    }
  }
}
// Driver function
int main() {
  int arr[10] = {7, 5, 1, 50, 3, -20, 25, -4, 30, 0};
  int n = 10;
  combSort(arr, n);
  cout << "Sorted array" << endl;
  for (int i = 0; i < n; i++)
    cout << arr[i] << " ";
}        

Java


// Java Code for Comb Sort 
class CombSort 
{ 
    // function to update gap value
    int updateGap(int gap) 
    { 
        // Shrink gap by the shrink factor 
        gap = (gap*10)/13; 
        if (gap < 1) 
            return 1;
        else
            return gap; 
    } 
    // Function to sort arr[] using Comb Sort 
    void combSort(int arr[], int n) 
    { 
        // initialize gap 
        int gap = n; 
        // Initialize swapped as true to make sure that the loop runs 
        boolean swapped = true; 
        while (gap != 1 || swapped == true) 
        { 
            // Update gap value
            gap = updateGap(gap); 
            swapped = false; 
            // Compare all elements with current gap 
            for (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; 
                    swapped = true; 
                } 
            } 
        } 
    } 
    // Driver function
    public static void main(String args[]) 
    { 
        CombSort obj = new CombSort(); 
        int arr[] = {7, 5, 1, 50, 3, -20, 25, -4, 30, 0};
        int n=10;
        obj.combSort(arr,n);
        System.out.println("Sorted array"); 
        for (int i=0; i<arr.length; ++i) 
            System.out.print(arr[i] + " ");
    } 
}

Python

    
# Python Code for CombSort 
# function to update gap value
def updateGap(gap):
    # Shrink gap by Shrink factor 
    gap = int((gap * 10)/13)
    if gap < 1: 
        return 1
    else:
        return gap  
# Function to sort arr[] using Comb Sort 
def combSort(arr, n): 
    # Initialize gap 
    gap = n 
    # Initialize swapped as true to make sure that the loop runs 
    swapped = True
    # Keep running while gap is more than 1
    while gap !=1 or swapped == 1: 
        # Update gap value
        gap = updateGap(gap) 
        swapped = False
        # Compare all elements with current gap 
        for 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
arr = [ 7, 5, 1, 50, 3, -20, 25, -4, 30, 0]
n= len(arr)
combSort(arr, n)  
print ("Sorted array") 
for i in range(n): 
    print (arr[i],end=' ')       

Go


// Go Code for Comb Sort
package main
import "fmt"
// function to update gap value
func updateGap(gap int) int {
	// Shrink gap by Shrink factor 
    gap = (gap * 10) / 13
    if gap < 1 {
        return 1
    }
    return gap
}
// Function to sort arr[] using Comb Sort 
func combSort(arr []int, n int) {
	// Initialize gap 
    gap := n
	// Initialize swapped as true to make sure that the loop runs 
    swapped := false
	// Keep running while gap is more than 1
    for gap > 1 || swapped {
		// Update gap value
        gap = updateGap(gap)
        swapped = false
		// Compare all elements with current gap 
        for i := 0; i < (n - gap); i++ {
            if arr[i] > arr[i+gap] {
                arr[i], arr[i+gap] = arr[i+gap], arr[i]
                swapped = true
            }
        }
    }
}
// Driver Function
func main() {
    arr:=[]int{7, 5, 1, 50, 3, -20, 25, -4, 30, 0}
    n:=10
    combSort(arr, n)
    fmt.Println("Sorted Array")
    for i := 0; i < n; i++ {
        fmt.Printf("%d ", arr[i])
    }
}

Applications

  • Comb Sort is an improvement over Bubble Sort.
  • Comb Sort eliminates small values at the end of the list by using larger gap.
  • Comb Sort has best case time complexity of Θ(N log N) comparable to Quick Sort.
  • Comb Sort does not require any extra space and easy to implement sorting algorithm.