Python Program to Implement Comb Sort

«
»

This is a Python program to implement comb sort.

Problem Description

The program sorts a list by comb sort.

Problem Solution

1. Create a function comb_sort that takes a list as argument.
2. Set gap equal to the length of the list.
3. Choose an appropriate shrink factor. Here shrink = 1.3.
4. Create a while loop that runs as long as there was at least one swap performed in the previous iteration of the loop (or if this is the first iteration of the loop).
5. Set gap to the floor of gap/shrink.
6. If gap becomes less than 1, set it to 1.
7. Perform bubble sort on the list but only compare and swap elements that are at a distance of gap.
8. If gap was not one, then continue the loop even if there weren’t any swaps performed.

Program/Source Code

Here is the source code of a Python program to implement comb sort. The program output is shown below.

def comb_sort(alist):
    def swap(i, j):
        alist[i], alist[j] = alist[j], alist[i]
 
    gap = len(alist)
    shrink = 1.3
 
    no_swap = False
    while not no_swap:
        gap = int(gap/shrink)
 
        if gap < 1:
            gap = 1
            no_swap = True
        else:
            no_swap = False
 
        i = 0
        while i + gap < len(alist):
            if alist[i] > alist[i + gap]:
                swap(i, i + gap)
                no_swap = False
            i = i + 1
 
 
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
comb_sort(alist)
print('Sorted list: ', end='')
print(alist)
Program Explanation

1. The user is prompted to enter a list of numbers.
2. The list is passed to the comb_sort function.
3. The sorted list is displayed.

advertisement
advertisement
Runtime Test Cases
Case 1:
Enter the list of numbers: 2 8 4 3 7 10 23 4 5
Sorted list: [2, 3, 4, 4, 5, 7, 8, 10, 23]
 
Case 2:
Enter the list of numbers: 5 4 3 2 1
Sorted list: [1, 2, 3, 4, 5]
 
Case 3:
Enter the list of numbers: 3
Sorted list: [3]

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.