Sorting algorithm 14: Comb Sort

Introduction:

Comb sort is an improvement on bubble 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.

Let us understand comb sort will help of example:

Initially the array will be as shown below:

comb_sort

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.

comb_sort

Form the above image, we can see that 1 is smaller than 8. Hence swap:

comb_sort

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:

comb_sort

Now the final array at the end of pass 2, will be as below:

comb_sort

Now reduce the gap by 1.3. So 7/1.3 = 5

The sequence of steps for pass 3 will be as below:

comb_sort

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:

comb_sort

again reduce the gap by 1.3 i.e 3/1.3 = 2. At the end of pass 5, the result will be:

comb_sort

Again reduce the gap by 1.3 i.e 2/1.3 = 1.

at the end of pass 6, the the result will be as below:

comb_sort

This is the final result.

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;
}

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

}

Output:

The sorted order is
 1  2  3  4  5  6  7  8  9  10

1 2	The sorted order is 1 2 3 4 5 6 7 8 9 10

Introduction:

Let us understand comb sort will help of example:

Implementation of Comb Sort in C++

Output:

Further Reading:

Leave a Reply

Introduction:

Let us understand comb sort will help of example:

Implementation of Comb Sort in C++

Output:

Further Reading:

About The Author

prodevelopertutorial

Leave a Reply