Comb Sort
Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
Algorithm
Complexity
Example
Implementations
Applications
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:
- 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 - Set swapped = false
- Set gap = gap/SHRINK_FACTOR
- 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 - 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
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.
Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.