Comb sort is a simple sorting algorithm which improves on bubble sort. The main idea for this type of algorithm is to eliminate the small values near the end of the list, as these slow down the sorting process.
How it works:
In comb sort, the main usage is of gaps. For example, in bubble sort the gap between two elements was 1 whilst here the gap starts out as a large value and shrinks until it reaches the value 1, when it practically becomes bubble sort. The shrink factor determines how much the gap is lessened. The value is crucial, so an ideal value would be 1.3.
Step by step example :
Having the following list, let’s try to use comb sort to arrange the numbers from lowest to greatest:
Unsorted list:
| 5 | 7 | 9 | 10 | 3 | 1 | 4 | 8 | 2 | 6 |
Iteration 1, gap = 8. The distance of 8 from the first element 5 to the next element, leads to the element of 2, these numbers are not in the right order so they have to swap. Also, the same distance is between 7 and 6 which also are not in the right order, so again a swap is required:
| 2 | 7 | 9 | 10 | 3 | 1 | 4 | 8 | 5 | 6 |
| 2 | 6 | 9 | 10 | 3 | 1 | 4 | 8 | 5 | 7 |
Iteration 2, gap =6, the elements that were compare on each line are 2 with 4, 6 with 8, 5 with 9 and 7 with 10:
| 2 | 7 | 9 | 10 | 3 | 1 | 4 | 8 | 5 | 7 |
| 2 | 6 | 9 | 10 | 3 | 1 | 4 | 8 | 5 | 7 |
| 2 | 6 | 5 | 10 | 3 | 1 | 4 | 8 | 9 | 7 |
| 2 | 6 | 5 | 7 | 2 | 1 | 4 | 8 | 9 | 10 |
Iteration 3, gap = 4:
| 2 | 7 | 9 | 10 | 3 | 1 | 4 | 8 | 5 | 10 |
| 2 | 1 | 9 | 10 | 3 | 6 | 4 | 8 | 5 | 10 |
| 2 | 1 | 4 | 10 | 3 | 6 | 5 | 8 | 9 | 10 |
| 2 | 1 | 4 | 7 | 3 | 6 | 5 | 8 | 9 | 10 |
| 2 | 1 | 4 | 7 | 3 | 6 | 5 | 8 | 9 | 10 |
| 2 | 1 | 4 | 7 | 3 | 6 | 5 | 8 | 9 | 10 |
Iteration 4, gap = 3:
| 2 | 1 | 4 | 7 | 3 | 6 | 5 | 8 | 9 | 10 |
| 2 | 1 | 4 | 7 | 3 | 6 | 5 | 8 | 9 | 10 |
| 2 | 1 | 4 | 7 | 3 | 6 | 5 | 8 | 9 | 10 |
| 2 | 1 | 4 | 5 | 3 | 6 | 7 | 8 | 9 | 10 |
| 2 | 1 | 4 | 5 | 3 | 6 | 5 | 8 | 9 | 10 |
| 2 | 1 | 4 | 5 | 3 | 6 | 5 | 8 | 9 | 10 |
| 2 | 1 | 4 | 5 | 3 | 6 | 7 | 8 | 9 | 10 |
Iteration 5, gap =2:
| 2 | 1 | 4 | 5 | 3 | 6 | 7 | 8 | 9 | 10 |
| 2 | 1 | 4 | 5 | 3 | 6 | 7 | 8 | 9 | 10 |
| 2 | 1 | 3 | 5 | 4 | 6 | 7 | 8 | 9 | 10 |
| 2 | 1 | 3 | 5 | 4 | 6 | 7 | 8 | 9 | 10 |
| 2 | 1 | 3 | 5 | 4 | 6 | 7 | 8 | 9 | 10 |
| 2 | 1 | 3 | 5 | 4 | 6 | 7 | 8 | 9 | 10 |
| 2 | 1 | 3 | 5 | 4 | 6 | 7 | 8 | 9 | 10 |
| 2 | 1 | 3 | 5 | 4 | 6 | 7 | 8 | 9 | 10 |
Iteration 6, gap =1:
| 1 | 2 | 3 | 5 | 4 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 5 | 4 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Iteration 7 : since the items are sorted, no swaps will be made and the algorithm ends its execution.
Sample code:
#include < iostream >using namespace std;
int newGap(int gap) {
gap = (gap * 10) / 13;
if (gap == 9 || gap == 10)
gap = 11;
if (gap < 1)
gap = 1;
return gap;
}void combsort(int a[], int aSize) {
int gap = aSize;
for (;;) {
gap = newGap(gap);
bool swapped = false;
for (int i = 0; i < aSize - gap; i++) {
int j = i + gap;
if (a[i] > a[j]) {
std::swap(a[i], a[j]);
swapped = true;
}}if (gap == 1 && !swapped)
break;
}}int main ()
{int n;
int *a;
cout << "Please insert the number of elements to be sorted: ";
cin >> n; // The total number of elements
a = (int *)calloc(n, sizeof(int));
for(int i=0;i< n;i++)
{cout << "Input " << i << " element: ";
cin >>a[i]; // Adding the elements to the array
}cout << "Unsorted list:" << endl; // Displaying the unsorted array
for(int i=0;i< n;i++)
{cout << a[i] << " ";
}combsort(a,n);
cout << "nSorted list:" << endl; // Display the sorted array
for(int i=0;i < n;i++)
{cout << a[i] << " ";
}return 0;
}
Output:
Code explanation:
At first, the method newGap calculates the size of the gap, based on the number of elements to be sorted. The combsort method is the one who sorts the numbers from the array, at first with the highest gap, which is calculated by calling the newGap method, then it passes through the array and checks the proper elements if they are in the right order, and if not, the library function swap is executed. This continues until the gap reaches the value 1 and no more swaps have been executed.
Complexity:
This is quite surprising. Despite being based on the idea of a Bubble Sort the time complexity is just O(n log n), and space complexity for in-place sorting is O(1).
Advantages:
- is proper for data sets composed of either numbers or strings;
- time complexity very good, could be compared to quick sort.
- no recursive function-calls
- in-place-sorting, no extra memory needed
- no worst-case-situation like in Quicksort .
Disadvantages:
- you have to resize the gap with a division by 1.3, which is a fraction;
Conclusion:
Comb sort is a good sorting algorithm, almost as good as quick sort. It is very easy to implement in other programming languages like java or python. The best thing about this is that there are no recursive function calls or there is no worst case situation. Unfortunately, it is not as knows to programmers as other algorithms like quick sort or merge sort are.
