Comb sort is an improvement of the bubble sort algorithm.In the comb sort,the items are sorted in a specific gap. After completing each phase,the gap decreased.
With compared to the bubble sort this sorting algorithm remove the worst-case scenario and improved on the time complexity of Bubble sort.
Example
Let's arrange the numbers in ascending order using Comb sort.
Unsorted List
- Iteration 1
Gap = 8 (number of elements in the array/ 1.3)
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.Then the second element compared with the last element,they are not in the order so again swap is required.
- Iteration 2
New Gap Value = 8/1.3 = 6
- Iteration 3
New Gap Value = 6/1.3 = 4
- Iteration 4
New Gap Value = 4/1.3 = 3
- Iteration 5
New Gap value = 3/1.3 = 2
- Iteration 6
New Gap Value = 2/1.3 = 1
Algorithm
- Calculate the Gap value.
- Iterate over dataset and compare each element with the gap element then move to swapping.
- if the gap value has reached one then terminating the loop.
Pseudocode
function comboSort( array : list of sortable items)
length = length(array)
gap = length / 1.3
loop while(gap >= 1)
for i = 0 to i <= n-1 do
if ( i + gap > n-1 )
continue
end if
if ( array[i] > array[i+gap] )
swap( array, i , i+gap )
end if
end for
gap /= 1.3
end loop
end function
function swap(a : list of sortable items,input x, input y)
temp = a[x]
a[x] = a[y]
a[y] = temp
end function
Time complexity
Best Case complexity = O(n)
Worst case complexity = O(n*n)