The Comb Sort Algorithm is very similar to Bubble Sort. It is used to sort an array, by comparing values. The difference is that Count Sort uses different gaps between the compared elements. This gap in the first iteration is large, and then it gets divided by 1.3 at every iteration, until it reaches 1. The elements are compared to each other, and if the elements on the right is smaller than the one on the left, then they are swapped.
// Comb sort
#include <iostream>
using namespace std;
void combSort(int arrayOfNumbers[], int numberOfElements)
{
int gap = numberOfElements;
bool continueSort = true;
while(gap != 1 || continueSort == true)
{
// Change the gap at every loop
gap = gap / 1.3;
if(gap < 1)
{
gap = 1;
}
continueSort = false;
// Compare the values separated by the gap
for(int i = 0; i < numberOfElements - gap; i++)
{
if(arrayOfNumbers[i] > arrayOfNumbers[i + gap])
{
swap(arrayOfNumbers[i], arrayOfNumbers[i + gap]);
continueSort = true;
}
}
}
}
void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
for (int i = 0; i < numberOfElements; i++)
{
cout << arrayOfNumbers[i] << " ";
}
cout << endl;
}
int main()
{
int arrayOfNumbers[] = {1, 15, 9, 6, 17, 99, 48, 30, 61, 21};
int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
combSort(arrayOfNumbers, numberOfElements);
cout<<"The sorted array is: \n";
printElementsOfArray(arrayOfNumbers, numberOfElements);
return 0;
}
Comments