Comb Sort is the variation of Bubble Sort algorithm. In Bubble sort, the element is compared to the adjacent elements, but in comb sort the array is divided into gaps and then sorted with the help of bubble sort algorithm. And After every iteration the gap is reduced by the shrink factor 1.3.
def get_gap(gap): gap = (gap * 10)/13 if gap < 1: return 1 gap = int(gap) return gap def sort(arr, length): gap = length is_swapped = True while gap != 1 or is_swapped == 1: gap = get_gap(gap) is_swapped = False for i in range(0, length - gap): if arr[i] > arr[i + gap]: arr[i], arr[i + gap] = arr[i + gap], arr[i] is_swapped = True ip_arr = [51, 2, -14, -6, 3] sort(ip_arr, len(ip_arr)) print("The sorted array is ") for i in range(len(ip_arr)): print(ip_arr[i])
In the above program we have created variables gap, swapped and a constant variable shrink_fac initialised with values gap/shrink factor, False and 1.3 respectively. Initial gap = size of array.
- For iteration 1, we have value of swapped = False and gap = gap/ shrink factor.
- Compare the value at index 0 with value at index = gap. If the value at index 0 is greater swap both the values and make swapped = True.
- Similarly compare the values at index = 1 and index = index + gap.
- If no element exists at the index, the iteration stopped here and next iteration will be followed.
- Repeat the above steps and return the sorted array.