comb sort Algorithm
Comb sort is an improvement over the Bubble sort algorithm that tends to eliminate small values at the end of the list by introducing a gap between the elements being compared. It was developed by Wlodzimierz Dobosiewicz and Artur Borowy in 1980 as an optimization over the slow Bubble sort and is based on the idea of the "shrinking factor." Comb sort works by comparing elements at a certain gap, and if they are found to be unordered, they are swapped. This gap is continuously reduced until it becomes 1, and the algorithm ends when the gap is 1, and no swaps are made.
The shrinking factor used in Comb sort is usually 1.3, which has been experimentally proven to yield good results. The algorithm starts by setting the initial gap equal to the length of the list divided by the shrinking factor. In each iteration, the gap is reduced by dividing it again by the shrinking factor and rounding down. Elements at the current gap distance are then compared and swapped if they are in the wrong order. This process continues until the gap becomes 1, and a final pass is made to ensure the list is sorted. Comb sort's performance is significantly better than Bubble sort, with an average-case time complexity of O(n^2/2^p) for a fixed number of increments. It is easy to implement and can be a suitable alternative to other inefficient sorting algorithms.
#include <stdio.h>
#include <stdlib.h>
#define SHRINK 1.3 //suggested shrink factor value
void sort (int *numbers, int size)
{
int gap = size;
while (gap > 1) //gap = 1 means that the array is sorted
{
gap = gap/SHRINK;
int i = 0;
while ((i + gap) < size)
{ //similiar to the Shell Sort
if (numbers[i] > numbers[i + gap])
{
int tmp = numbers[i];
numbers[i] = numbers[i + gap];
numbers[i + gap] = tmp;
}
i++;
}
}
}
void display(int *array, int n)
{
int i;
for (i = 0; i < n; ++i)
printf("%d ", array[i]);
printf("\n");
}
int main()
{
int size = 6;
int *numbers = malloc(size*sizeof(int));
printf("Insert %d unsorted numbers: \n", size);
int i;
for (i = 0; i < size; ++i)
scanf("%d", &numbers[i]);
printf("Initial array: ");
display(numbers, size);
sort(numbers, size);
printf("Sorted array: ");
display(numbers, size);
free(numbers);
return 0;
}
