Program for Comb Sort using Python

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

Program for Comb Sort using Python

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.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.