Comb Sort
Comb Sort is mainly an improvement over Bubble Sort. Bubble sort always compares adjacent values. So all inversions are removed one by one. Comb Sort improves on Bubble Sort by using gap of size more than 1. The gap starts with a large value and shrinks by a factor of 1.3 in every iteration until it reaches the value 1. Thus Comb Sort removes more than one inversion counts with one swap and performs better than Bubble Sort.
The shrink factor has been empirically found to be 1.3 (by testing Combsort on over 200,000 random lists) [Source: Wiki]
Although, it works better than Bubble Sort on average, worst case remains O(n2).
Below is the implementation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// C++ implementation of Comb Sort
#include<bits/stdc++.h>
using namespace std;
// To find gap between elements
int getNextGap(int gap)
{
// Shrink gap by Shrink factor
gap = (gap*10)/13;
if (gap < 1)
return 1;
return gap;
}
// Function to sort a[0..n-1] using Comb Sort
void combSort(int a[], int n)
{
// Initialize gap
int gap = n;
// Initialize swapped as true to make sure that
// loop runs
bool swapped = true;
// Keep running while gap is more than 1 and last
// iteration caused a swap
while (gap != 1 || swapped == true)
{
// Find next gap
gap = getNextGap(gap);
// Initialize swapped as false so that we can
// check if swap happened or not
swapped = false;
// Compare all elements with current gap
for (int i=0; i<n-gap; i++)
{
if (a[i] > a[i+gap])
{
swap(a[i], a[i+gap]);
swapped = true;
}
}
}
}
// Driver program
int main()
{
int a[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
int n = sizeof(a)/sizeof(a[0]);
combSort(a, n);
printf("Sorted array: \n");
for (int i=0; i<n; i++)
printf("%d ", a[i]);
return 0;
}
Output :
1
2
Sorted array:
-44 -6 0 1 3 4 8 23 28 56
Illustration:
Let the array elements be
1
8, 4, 1, 56, 3, -44, 23, -6, 28, 0
Initially gap value = 10
After shrinking gap value => 10/1.3 = 7;
1
2
3
8 4 1 56 3 -44 23 -6 28 0
-6 4 1 56 3 -44 23 8 28 0
-6 4 0 56 3 -44 23 8 28 1
New gap value => 7/1.3 = 5;
1
2
3
-44 4 0 56 3 -6 23 8 28 1
-44 4 0 28 3 -6 23 8 56 1
-44 4 0 28 1 -6 23 8 56 3
New gap value => 5/1.3 = 3;
1
2
3
4
-44 1 0 28 4 -6 23 8 56 3
-44 1 -6 28 4 0 23 8 56 3
-44 1 -6 23 4 0 28 8 56 3
-44 1 -6 23 4 0 3 8 56 28
New gap value => 3/1.3 = 2;
1
2
3
-44 1 -6 0 4 23 3 8 56 28
-44 1 -6 0 3 23 4 8 56 28
-44 1 -6 0 3 8 4 23 56 28
New gap value => 2/1.3 = 1;
1
2
3
4
5
6
-44 -6 1 0 3 8 4 23 56 28
-44 -6 0 1 3 8 4 23 56 28
-44 -6 0 1 3 4 8 23 56 28
-44 -6 0 1 3 4 8 23 28 56
no more swaps required (Array sorted)
Time Complexity: Average case time complexity of the algorithm is Ω(N2/2p), where p is the number of increments. The worst-case complexity of this algorithm is O(n2) and the Best Case complexity is O(nlogn).
Auxiliary Space : O(1).
