what is COMB SORT?

COMB SORT

Comb Sort is the advance form of Bubble Sort. Bubble Sort compares all the adjacent values while comb sort removes all the turtle values or small values near the end of the list.

Factors affecting comb sort are:

• It improves on bubble sort by using gap of size more than 1.
• Gap starts with large value and shrinks by the factor of 1.3.
• Gap shrinks till value reaches 1.

Complexity

Algorithm	Complexity
Worst Case Complexity	O(n2)
Best Case Complexity	θ(n log n)
Average Case Complexity	Ω(n2/2p) where p is number of increments.
Worst Case Space Complexity	O(1)

Algorithm

• STEP 1 START
• STEP 2 Calculate the gap value if gap value==1 goto step 5 else goto step 3
• STEP 3 Iterate over data set and compare each item with gap item then goto step 4.
• STEP 4 Swap the element if require else goto step 2
• STEP 5 Print the sorted array.
• STEP 6 STOP

Program

1. #include <stdio.h>  
2. #include <stdlib.h>  
3.  int newgap(int gap)  
4. {  
5.     gap = (gap * 10) / 13;  
6.     if (gap == 9 || gap == 10)  
7.         gap = 11;  
8.     if (gap < 1)  
9.         gap = 1;  
10.     return gap;  
11. }  
12.    
13. void combsort(int a[], int aSize)  
14. {  
15.     int gap = aSize;  
16.     int temp, i;  
17.     for (;;)  
18.     {  
19.         gap = newgap(gap);  
20.         int swapped = 0;  
21.         for (i = 0; i < aSize - gap; i++)   
22.         {  
23.             int j = i + gap;  
24.             if (a[i] > a[j])  
25.             {  
26.                 temp = a[i];  
27.                 a[i] = a[j];  
28.                 a[j] = temp;  
29.                 swapped  =  1;  
30.             }  
31.         }  
32.         if (gap  ==  1 && !swapped)  
33.             break;  
34.     }  
35. }  
36. int main ()  
37. {  
38.     int n, i;  
39.     int *a;  
40.     printf("Please insert the number of elements to be sorted: ");  
41.     scanf("%d", &n);       // The total number of elements  
42.     a  =  (int *)calloc(n, sizeof(int));  
43.     for (i = 0;i< n;i++)  
44.     {  
45.         printf("Input element %d :", i);  
46.         scanf("%d", &a[i]); // Adding the elements to the array  
47.     }  
48.     printf("unsorted list");       // Displaying the unsorted array  
49.     for(i = 0;i < n;i++)  
50.     {  
51.          printf("%d", a[i]);  
52.     }  
53.     combsort(a, n);  
54.     printf("Sorted list:\n"); // Display the sorted array  
55.     for(i = 0;i < n;i++)  
56.     {  
57.         printf("%d ", (a[i]));  
58.     }  
59.     return 0;  
60. }