Get this book -> Problems on Array: For Interviews and Competitive Programming

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(N**^{2}) - Average case time complexity:

, where p is the number of increments**Ω(N**^{2}/2^{p}) - Best case time complexity:
**Î˜(N log N)** - Space complexity:

auxillary space**Î˜(1)**

### Example

```
Initial array (7, 5, 1, 50, 3, -20, 25, -4, 30, 0)
Initial Gap value = 10
Constant k = 1.3
1
```^{st} 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
2^{nd} 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
3^{rd} 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
4^{th} 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
5^{th} 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?

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