Python Program for Comb Sort

A variation of the Bubble Sort is called Comb Sort. The Comb Sort is just like the Shell sort which widens the distance utilized in comparisons and exchanges.

In this tutorial, we are going to perform Comb sort in python programming to sort an array.

Comb Sort - A Basic Introduction

The principle behind the comb sort operation is that the distance between elements is considerably larger than one. While bubble sort compares adjacent values with a gap of one, comb sort compares values with a gap of more than one.

• The gap is initially equal to the length of the array, but it shrinks by a factor of 1.3 with each iteration until it approaches the number 1.
• The comb sort technique removes several inversion counts with a single swap, it outperforms Bubble Sort on average.
• The main concept is to get rid of tiny values at the end of the list because they slow down the sorting process considerably in a bubble sort. Large values towards the beginning of the list are not an issue with bubble sort. When two components are compared in bubble sort, there is always a gap of one. The essential principle behind comb sorting is that the distance between items might be considerably larger than one.

Let us have a look at the diagram given below for a better understanding:

Algorithm

As of now, we have a rough understanding of how to comb sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Create a function comb_sort()

2. Pass the number as a parameter

3. Initialize distance or gap as dist

4. Declare swap as TRUE

5. Compare the value of gaps

6. Run the program until the dist! = 1

7. Print out the resultant array.

Program for Comb Sort

As discussed above in the algorithm, let us now dive into the programming part of the comb sort operation influenced by the algorithm.

def comb_sort(number):
    dist = len(number)
    swap = True
    while dist > 1 or swap:
        dist = max(1, int(dist / 1.25)) 
        swap = False
        for a in range(len(number) - dist):
            b = a+dist
            if number[a] > number[b]:
                number[a], number[b] = number[b], number[a]
                swap = True
 
array = [3, 1, 2, 5, 4]
print("The original array is: ", array)
comb_sort(array)
print("The sorted array is:  ", array)

The original array is: [3, 1, 2, 5, 4]
The sorted array is: [1, 2, 3, 4, 5]

Conclusion

In this tutorial, we have performed a comb sort operation in python to sort an array. The best-case time complexity of comb sort is O(n log n), the worst-case time complexity is O(n2) and the space complexity of comb sort is O(1).