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 Bublle 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(n²).

[ad type=”banner”]

Below is C++ implementation.

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20implementation%20of%20Comb%20Sort%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20To%20find%20gap%20between%20elements%0Aint%20getNextGap(int%20gap)%0A%7B%0A%20%20%20%20%2F%2F%20Shrink%20gap%20by%20Shrink%20factor%0A%20%20%20%20gap%20%3D%20(gap*10)%2F13%3B%0A%20%0A%20%20%20%20if%20(gap%20%3C%201)%0A%20%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20return%20gap%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20sort%20a%5B0..n-1%5D%20using%20Comb%20Sort%0Avoid%20combSort(int%20a%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20gap%0A%20%20%20%20int%20gap%20%3D%20n%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20swapped%20as%20true%20to%20make%20sure%20that%0A%20%20%20%20%2F%2F%20loop%20runs%0A%20%20%20%20bool%20swapped%20%3D%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20Keep%20running%20while%20gap%20is%20more%20than%201%20and%20last%0A%20%20%20%20%2F%2F%20iteration%20caused%20a%20swap%0A%20%20%20%20while%20(gap%20!%3D%201%20%7C%7C%20swapped%20%3D%3D%20true)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20next%20gap%0A%20%20%20%20%20%20%20%20gap%20%3D%20getNextGap(gap)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20swapped%20as%20false%20so%20that%20we%20can%0A%20%20%20%20%20%20%20%20%2F%2F%20check%20if%20swap%20happened%20or%20not%0A%20%20%20%20%20%20%20%20swapped%20%3D%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Compare%20all%20elements%20with%20current%20gap%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn-gap%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(a%5Bi%5D%20%3E%20a%5Bi%2Bgap%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20swap(a%5Bi%5D%2C%20a%5Bi%2Bgap%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20swapped%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Driver%20program%0Aint%20main()%0A%7B%0A%20%20%20%20int%20a%5B%5D%20%3D%20%7B8%2C%204%2C%201%2C%2056%2C%203%2C%20-44%2C%2023%2C%20-6%2C%2028%2C%200%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(a)%2Fsizeof(a%5B0%5D)%3B%0A%20%0A%20%20%20%20combSort(a%2C%20n)%3B%0A%20%0A%20%20%20%20printf(%22Sorted%20array%3A%20%5Cn%22)%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20a%5Bi%5D)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D%0A%0A” message=”c++” highlight=”” provider=”manual”/]

JAVA

[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20for%20implementation%20of%20Comb%20Sort%0Aclass%20CombSort%0A%7B%0A%20%20%20%20%2F%2F%20To%20find%20gap%20between%20elements%0A%20%20%20%20int%20getNextGap(int%20gap)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Shrink%20gap%20by%20Shrink%20factor%0A%20%20%20%20%20%20%20%20gap%20%3D%20(gap*10)%2F13%3B%0A%20%20%20%20%20%20%20%20if%20(gap%20%3C%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20%20%20%20%20return%20gap%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20sort%20arr%5B%5D%20using%20Comb%20Sort%0A%20%20%20%20void%20sort(int%20arr%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20initialize%20gap%0A%20%20%20%20%20%20%20%20int%20gap%20%3D%20n%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20swapped%20as%20true%20to%20make%20sure%20that%0A%20%20%20%20%20%20%20%20%2F%2F%20loop%20runs%0A%20%20%20%20%20%20%20%20boolean%20swapped%20%3D%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Keep%20running%20while%20gap%20is%20more%20than%201%20and%20last%0A%20%20%20%20%20%20%20%20%2F%2F%20iteration%20caused%20a%20swap%0A%20%20%20%20%20%20%20%20while%20(gap%20!%3D%201%20%7C%7C%20swapped%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Find%20next%20gap%0A%20%20%20%20%20%20%20%20%20%20%20%20gap%20%3D%20getNextGap(gap)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20swapped%20as%20false%20so%20that%20we%20can%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20check%20if%20swap%20happened%20or%20not%0A%20%20%20%20%20%20%20%20%20%20%20%20swapped%20%3D%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Compare%20all%20elements%20with%20current%20gap%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn-gap%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3E%20arr%5Bi%2Bgap%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Swap%20arr%5Bi%5D%20and%20arr%5Bi%2Bgap%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20temp%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bi%5D%20%3D%20arr%5Bi%2Bgap%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bi%2Bgap%5D%20%3D%20temp%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Set%20swapped%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20swapped%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20CombSort%20ob%20%3D%20new%20CombSort()%3B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B8%2C%204%2C%201%2C%2056%2C%203%2C%20-44%2C%2023%2C%20-6%2C%2028%2C%200%7D%3B%0A%20%20%20%20%20%20%20%20ob.sort(arr)%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22sorted%20array%22)%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Carr.length%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(arr%5Bi%5D%20%2B%20%22%20%22)%3B%0A%20%0A%20%20%20%20%7D%0A%7D” message=”java” highlight=”” provider=”manual”/] [ad type=”banner”]

PTHYON

[pastacode lang=”python” manual=”%23%20Python%20program%20for%20implementation%20of%20CombSort%0A%20%0A%23%20To%20find%20next%20gap%20from%20current%0Adef%20getNextGap(gap)%3A%0A%20%0A%20%20%20%20%23%20Shrink%20gap%20by%20Shrink%20factor%0A%20%20%20%20gap%20%3D%20(gap%20*%2010)%2F13%0A%20%20%20%20if%20gap%20%3C%201%3A%0A%20%20%20%20%20%20%20%20return%201%0A%20%20%20%20return%20gap%0A%20%0A%23%20Function%20to%20sort%20arr%5B%5D%20using%20Comb%20Sort%0Adef%20combSort(arr)%3A%0A%20%20%20%20n%20%3D%20len(arr)%0A%20%0A%20%20%20%20%23%20Initialize%20gap%0A%20%20%20%20gap%20%3D%20n%0A%20%0A%20%20%20%20%23%20Initialize%20swapped%20as%20true%20to%20make%20sure%20that%0A%20%20%20%20%23%20loop%20runs%0A%20%20%20%20swapped%20%3D%20True%0A%20%0A%20%20%20%20%23%20Keep%20running%20while%20gap%20is%20more%20than%201%20and%20last%0A%20%20%20%20%23%20iteration%20caused%20a%20swap%0A%20%20%20%20while%20gap%20!%3D1%20or%20swapped%20%3D%3D%201%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20Find%20next%20gap%0A%20%20%20%20%20%20%20%20gap%20%3D%20getNextGap(gap)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Initialize%20swapped%20as%20false%20so%20that%20we%20can%0A%20%20%20%20%20%20%20%20%23%20check%20if%20swap%20happened%20or%20not%0A%20%20%20%20%20%20%20%20swapped%20%3D%20False%0A%20%0A%20%20%20%20%20%20%20%20%23%20Compare%20all%20elements%20with%20current%20gap%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(0%2C%20n-gap)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20arr%5Bi%5D%20%3E%20arr%5Bi%20%2B%20gap%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bi%5D%2C%20arr%5Bi%20%2B%20gap%5D%3Darr%5Bi%20%2B%20gap%5D%2C%20arr%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20swapped%20%3D%20True%0A%20%0A%20%0A%23%20Driver%20code%20to%20test%20above%0Aarr%20%3D%20%5B%208%2C%204%2C%201%2C%203%2C%20-44%2C%2023%2C%20-6%2C%2028%2C%200%5D%0AcombSort(arr)%0A%20%0Aprint%20(%22Sorted%20array%3A%22)%0Afor%20i%20in%20range(len(arr))%3A%0A%20%20%20%20print%20(arr%5Bi%5D)%2C%0A%20″ message=”python” highlight=”” provider=”manual”/]

Output :

Sorted array: 
-44 -6 0 1 3 4 8 23 28 56 

 

Illustration:
Let the array elements be

8, 4, 1, 56, 3, -44, 23, -6, 28, 0

Initially gap value = 10
After shrinking gap value => 10/1.3 = 7;

 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;

-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;

-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;

-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;

-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 : Worst case complexity of this algorithm is O(n²) and the Best Case complexity is O(n).

Auxiliary Space : O(1).

[ad type=”banner”]