*52*

# Comb Sort Algorithm

In this article, we will discuss the comb sort Algorithm. Comb Sort is the advanced form of bubble Sort. Bubble Sort compares all the adjacent values while comb sort removes all the turtle values or small values near the end of the list.

It is a comparison-based sorting algorithm that is mainly an improvement in bubble sort. In bubble sort, there is a comparison between the adjacent elements to sort the given array. So, in bubble sort, the gap size between the elements that are compared is 1. Comb sort improves the bubble sort by using a gap of size more than 1. The gap in the comb sort starts with the larger value and then shrinks by a factor of 1.3. It means that after the completion of each phase, the gap is divided by the shrink factor 1.3. The iteration continues until the gap is 1.

The shrink factor is found to be 1.3 by testing comb sort on 200,000 random lists. Comb sort works better than the bubble sort, but its time complexity in average case and worst case remains O(n^{2}).

The process of performing the comb sort is given as follows –

**STEP 1** START

**STEP 2** Calculate the gap value if gap value==1 goto step 5 else goto step 3

**STEP 3** Iterate over data set and compare each item with gap item then goto step 4.

**STEP 4** Swap the element if require else goto step 2

**STEP 5** Print the sorted array.

**STEP 6** STOP

Now, let’s see the algorithm of comb sort.

### Algorithm

## Working of comb Sort Algorithm

Now, let’s see the working of the comb sort Algorithm.

To understand the working of the comb sort algorithm, let’s take an unsorted array. It will be easier to understand the comb sort via an example.

Let the elements of array are –

Now, initialize

**n** = 8 // size of array

**gap** = n

**shrink** = 1.3

**swapped** = true

### First iteration

**gap** = floor(gap/shrink) = floor(8/1.3) = 6

**swapped** = false

This iteration ends here, because at i =2, the value of i + gap = 2 + 6 = 8, and there is no element at 8^{th} position of the array. So, after first iteration, the elements of array will be –

Now, move to iteration 2.

### Second iteration

**gap** = floor(gap/shrink) = floor(6/1.3) = 4

**swapped** = false

This iteration ends here, because at i =4, the value of i + gap = 4 + 4 = 8, and there is no element at 8^{th} position of the array. So, after second iteration, the elements of array will be –

Now, move to iteration 3.

### Third iteration

**gap** = floor(gap/shrink) = floor(4/1.3) = 3

**swapped** = false

This iteration ends here, because at i =5, the value of i + gap = 5 + 3 = 8, and there is no element at 8^{th} position of the array. So, after third iteration, the elements of array will be –

Now, move to iteration 4.

### Fourth iteration

**gap** = floor(gap/shrink) = floor(3/1.3) = 2

**swapped** = false

This iteration ends here, because at i =6, the value of i + gap = 6 + 2 = 8, and there is no element at 8^{th} position of the array. So, after fourth iteration, the elements of array will be –

Now, move to iteration 5.

### Fifth iteration

**gap** = floor(gap/shrink) = floor(2/1.3) = 1

**swapped** = false

After the fifth iteration, the sorted array is –

Hence, the iterations end here, and now the sorting is completed. Now, the final sorted array is –

## Comb sort complexity

Now, let’s see the time complexity of Comb sort in the best case, average case, and worst case. We will also see the space complexity of Comb sort.

### 1. Time Complexity

Case | Time Complexity |
---|---|

Best Case | θ(n log n) |

Average Case | Ω(n^{2}/2^{p}) where p is a number of increments. |

Worst Case | O(n^{2}) |

**Best Case Complexity –**It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of comb sort is**θ(n log n)**.**Average Case Complexity –**It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of comb sort is**Ω(n**.^{2}/2^{p}), where p is a number of increments.**Worst Case Complexity –**It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of comb sort is**O(n**.^{2})

### 2. Space Complexity

Space Complexity | O(1) |

Stable | YES |

- The space complexity of comb sort is O(1).

## Implementation of Comb sort

Now, let’s see the programs of Comb sort in different programming languages.

**Program:** Write a program to implement comb sort in C language.

**Output**

**Program:** Write a program to implement comb sort in C++.

**Output**

**Program:** Write a program to implement comb sort in C#.

**Output**

**Program:** Write a program to implement comb sort in Java.

**Output**

**Program:** Write a program to implement comb sort in PHP.

**Output**

So, that’s all about the article. Hope the article will be helpful and informative to you.

This article was not only limited to the algorithm. Along with the algorithm, we have also discussed the Comb Sort’s complexity, working, and implementation in different programming languages.