Comb Sort Implementation in Python

Comb sort is a simple sorting algorithm that is an improvement over bubble sort. It was invented by Włodzimierz Dobosiewicz in 1980. The algorithm works by comparing and swapping adjacent elements that are not in the correct order. It then reduces the gap between adjacent elements and repeats the process until the gap becomes 1. At this point, the algorithm performs a final pass using the bubble sort algorithm to ensure that the list is completely sorted. Comb sort has a better worst-case time complexity than bubble sort and can be faster in some cases.

How Comb Sort Algorithm Works?

The Comb sort algorithm can be summarized in the following steps:

1. Start with a gap value of n, where n is the length of the input list.
2. Compare and swap adjacent elements that are not in the correct order.
3. Reduce the gap value by a shrink factor (usually 1.3) until it becomes 1.
4. Perform a final pass using the bubble sort algorithm to ensure that the list is completely sorted.

The algorithm works by using a gap value to determine how far apart adjacent elements are compared. The gap value is reduced in each iteration by a shrink factor, which is usually set to 1.3. This allows the algorithm to quickly compare and swap elements that are far apart while also taking advantage of the benefits of bubble sort for small gap values.

Comb Sort Algorithm Implementation in Python

Here’s an implementation of the Comb sort algorithm in Python:

def comb_sort(arr):
    gap = len(arr)
    shrink_factor = 1.3
    swapped = True
    while gap > 1 or swapped:
        gap = int(gap / shrink_factor)
    
        if gap < 1: gap = 1 swapped = False for i in range(len(arr) - gap): if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                swapped = True
    
    return arr

The above code implements the Comb sort algorithm in Python. The algorithm uses a gap value that starts at the length of the input list and is reduced by a shrink factor of 1.3 in each iteration until it becomes 1. The algorithm then performs a final pass using the bubble sort algorithm to ensure that the list is completely sorted.

Time and Space Complexity

The time complexity of the Comb sort algorithm is O(n^2) in the worst case and O(nlogn) in the best case. The space complexity is O(1) because the algorithm sorts the input list in-place without using any additional memory.

One Run of Comb Sort Algorithm

Let’s run the Comb sort algorithm on an input list of integers to see how it works:

arr = [3, 1, 7, 5, 9, 2, 8, 6, 4]
sorted_arr = comb_sort(arr)
print(sorted_arr)

The output of the above code should be:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

The input list is sorted using the Comb sort algorithm and the output shows that the algorithm has successfully sorted the list in ascending order.

Conclusion

Comb sort is a simple and efficient sorting algorithm that is an improvement over bubble sort. It works by using a gap value to determine how far apart adjacent elements are compared and reduces the gap value in each iteration until it becomes 1. The algorithm then performs a final pass using the bubble sort algorithm to ensure that the list is completely sorted. The Comb sort algorithm has a better worst-case time complexity than bubble sort and can be faster in some cases. It also has a space complexity of O(1), making it a good choice for sorting large lists in-place.

In this article, we have covered how the Comb sort algorithm works, implemented it in Python, analyzed its time and space complexity, and provided a sample run of the algorithm on an input list of integers. With this information, you should now have a better understanding of the Comb sort algorithm and be able to implement it in your own projects as needed.