## Comb Sort

Back to Programming

### Description

Comb sort is a comparison based sorting technique almost similar to Bubble Sort. We can say that comb sort is a modified version of bubble sort. In bubble sort, an adjacent pairs of elements are compared and swapped (if needed), unlike the bubble sort in comb sort the elements are compared with a particular gap.

The gap is decreased after each pass of sorting. The decreasing factor is 1.3 i.e. after each pass the gap is divided by 1.3 to get the new gap. It is an in-place sorting technique as it does not require any extra space to sort the data. The gapping of elements increases the efficiency of the sorting over bubble sort.

PROCEDURE WITH EXAMPLE:

Let take a 5 element array as follows:

The array is to be sorted in ascending order. For the first time, the gap is set to 5 i.e. the number of elements of the array.

Pass 1:

Before the first pass the array is:

In the first pass, the gap will be divided by 1.3.

So, the gap = 5/1.3 = 3. The elements at gap 3 will be compared with each other and will be swapped (if necessary).

Firstly, the starting index is 0 and it will be compared with the index (0 + 3) = 3.

So, here, 89 will be compared with 9, as 9 is lesser than 89 they will be swapped and we will get the array as:

After this, the element of index 1 will be compared with index (1 + 3) = 4, as -12 and 21 will be compared again but as -12 is already lesser than 21 then there will be no swap and the array will remain unchanged.

Next, index 2 should be compared with index (2 + 3) = 5 but as index 5 does not exist so the iteration will be ended and it will go for the next iteration.

Pass 2:

In the 2nd pass, the gap will be again divided by 1.3.

So, in this pass the gap = 3/1.3 = 2, so in a similar way, the elements at gap 2 will be compared with each other and will be swapped (if necessary).

At first, the element of starting index 0 will be compared with the element of the index (0 + 2) = 2. Here 9 is lesser than 17 so there will be no change.

After this the elements of index 1 and index (1 + 2) = 3 will be compared. In that case, -12 is already lesser than 89, so there will be no swapping

Next index 2 will be compared with index (2 + 2) = 4. Here now, 17 will be compared with 21, as 17 is lesser than 21 so there will be no swapping.

Next, index 3 should be compared with index (3 + 2) = 5 but as index 5 does not exist so the iteration will be ended and it will go for the next iteration.

Pass 3:

In the 3rd pass, the gap will be again divided by 1.3.

So, in this pass the gap = 2/1.3 = 1, so in a similar way, the elements at gap 1 will be compared with each other and will be swapped (if necessary).

For the first time index 0 will be compared with index (0 + 1) = 1. For this iteration, each pair of adjacent elements will be compared. Here is compared with -12, as -12 is lesser than 9, so it will be swapped.

Here, the next two adjacent elements and 17 will be compared and will not be swapped as they are already in sorted order

The next two adjacent elements are 17 and 89, they will be compared with each other but there will be no swapping

The last adjacent pair is 89 and 21, they will be compared with each other but as 89 is greater than 21 then there will be swapping and the array will be:

The array is already sorted after this pass.

For implementing the comb sort one flag is used in the loop to check whether any swapping has done or not. If there is any swapping then only the loop will go for the next pass.

Hence, though the array is sorted we have to go for the next pass.

Pass 4:

Here the gap is 1/1.3 = 0.

That means each element of the array will be compared to itself only. There will be no swapping. So, the loop will stop executing. So, the final sorted array is:

### Algorithm

``````INPUT: An unsorted array a[6,2,4,1,…………….,n]
OUTPUT: An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)

PROCESS:
Step 1: [Taking the inputs from the user]
for i=0 to n repeat
Step 2: [Sorting the elements using comb sort]
Set g<-n
Set f<-1
While g≠1 or f=1 repeat
Set g<-(g*10)/13
If g<1 then
Set g <- 1
[End of ‘If’]
Set f<-0
For i = 0 to n-g repeat
If arr[i] > arr[i+g] then
Set t<-arr[i]
Set arr[i]<-arr[i+g]
Set arr[i+g]<-t
Set f <- 1
[End of If]
[End of for loop]
[End of while loop]
Step 3: [Displaying the array elements]
For i=0 to n repeat
Print arr[i]

Step 4: Stop.
``````

### Code

CHARACTERISTICS:

1. It is a comparison based sorting technique.

2. It is an in-place sorting algorithm as it does not require any extra storage space for sorting.

3. It is similar to bubble sort but efficiency is better than bubble sort.

4. The sorting is done by swapping the elements at a particular gap if they are not incorrect order. After each pass, the gap is reduced.

TIME COMPLEXITY:

The best case will occur if the array is already sorted, then at the first pass, there will be no swapping. The loop is written such that if there is no swapping the loop will be ended and will not be executed from the next iteration.

The worst-case will occur if the array is in descending order.

SPACE COMPLEXITY:

The space complexity of the comb sort algorithm is O(1) as it does not require any extra space to sort the data.

1. It does not require extra spaces to sort the elements.

2. It works better than bubble sort though both are similar.

3. The logic is simple and it is reliable.

1. Worst-case complexity is the same as the complexity of bubble sort.

2. Does not work well for a large number of data.

3. It is not a stable sort.

APPLICATION:

It is an improved version of bubble sort so it is applied in some applications for sorting instead of bubble sort.

Related