Table of Contents
Introduction
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.
Program
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])
Output
Explanation
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.
0 Comments