In this chapter we shall learn about below topics:
14.1 Introduction and Steps for performing Comb Sort
14.2 Understanding Comb Sort with an example
14.3 Implementation of Comb Sort in C++
14.4 Time complexity of Comb Sort
14.1 Introduction and Steps for performing Comb Sort:
Comb sort is an improvement on b ubble sort.
As you know bubble sort will sort adjacent elements, comb sort will use the gap to sort the element.
At each pass the gap will be reduced by 1.3 until it reaches to 1.
Thus sorting the array.
14.2 Understanding Comb Sort with an example
Initially the array will be as shown below:
Initially gap will be 10.
Hence we compare first and last element. If the last element is less than that of the first element, we swap the elements.
Form the above image, we can see that 1 is smaller than 8. Hence swap:
Now reduce the gap by 1.3. So 10/1.3 = 7. This will be pass 2. In pass 2, we compare all the elements which has gap of 7 and perform similar check as shown below.
The below image will show you the sequence of steps performed form pass 2:
Now the final array at the end of pass 2, will be as below:
Now reduce the gap by 1.3. So 7/1.3 = 5
The sequence of steps for pass 3 will be as below:
for pass 4 again reduce the gap by 1.3. i.e 5/1.3 = 3
we need to perform similar operation at the end of pass 4. the array will be as below:
again reduce the gap by 1.3 i.e 3/1.3 = 2. At the end of pass 5, the result will be:
Again reduce the gap by 1.3 i.e 2/1.3 = 1.
at the end of pass 6, the result will be as below:
This is the final result.
14.3 Implementation of Comb Sort in C++
#include<iostream>
using namespace std;
void combSort(int *array, int length)
{
int gap = length;
bool flag = true;
while(gap != 1 || flag == true)
{
//reduce the gap by 1.3
gap = (gap)/1.3;
if(gap<1)
gap = 1;
flag = false;
//check the elements that are "gap" distance
for(int i = 0; i< length - gap; i++)
{
if(array[i] > array[ i + gap ])
{
swap(array[i], array[ i + gap ]);
flag = true;
}
}
}
}
int main()
{
int arr[] = {5, 4, 3, 2, 1, 9, 8, 7, 6, 10};
combSort(arr, 10);
cout<<"The sorted order is \n";
for (int i = 0; i < 10; ++i)
{
cout<<" "<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
14.4 Output:
The sorted order is
1 2 3 4 5 6 7 8 9 10