comb sort Algorithm
Comb sort is an improvement over the Bubble sort algorithm that tends to eliminate small values at the end of the list by introducing a gap between the elements being compared. It was developed by Wlodzimierz Dobosiewicz and Artur Borowy in 1980 as an optimization over the slow Bubble sort and is based on the idea of the "shrinking factor." Comb sort works by comparing elements at a certain gap, and if they are found to be unordered, they are swapped. This gap is continuously reduced until it becomes 1, and the algorithm ends when the gap is 1, and no swaps are made.
The shrinking factor used in Comb sort is usually 1.3, which has been experimentally proven to yield good results. The algorithm starts by setting the initial gap equal to the length of the list divided by the shrinking factor. In each iteration, the gap is reduced by dividing it again by the shrinking factor and rounding down. Elements at the current gap distance are then compared and swapped if they are in the wrong order. This process continues until the gap becomes 1, and a final pass is made to ensure the list is sorted. Comb sort's performance is significantly better than Bubble sort, with an average-case time complexity of O(n^2/2^p) for a fixed number of increments. It is easy to implement and can be a suitable alternative to other inefficient sorting algorithms.
"""
This is pure Python implementation of comb sort algorithm.
Comb sort is a relatively simple sorting algorithm originally designed by Wlodzimierz Dobosiewicz in 1980.
It was rediscovered by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble sort algorithm.
In bubble sort, distance (or gap) between two compared elements is always one.
Comb sort improvement is that gap can be much more than 1, in order to prevent slowing down by small values
at the end of a list.
More info on: https://en.wikipedia.org/wiki/Comb_sort
For doctests run following command:
python -m doctest -v comb_sort.py
or
python3 -m doctest -v comb_sort.py
For manual testing run:
python comb_sort.py
"""
def comb_sort(data: list) -> list:
"""Pure implementation of comb sort algorithm in Python
:param data: mutable collection with comparable items
:return: the same collection in ascending order
Examples:
>>> comb_sort([0, 5, 3, 2, 2])
[0, 2, 2, 3, 5]
>>> comb_sort([])
[]
>>> comb_sort([99, 45, -7, 8, 2, 0, -15, 3])
[-15, -7, 0, 2, 3, 8, 45, 99]
"""
shrink_factor = 1.3
gap = len(data)
completed = False
while not completed:
# Update the gap value for a next comb
gap = int(gap / shrink_factor)
if gap <= 1:
completed = True
index = 0
while index + gap < len(data):
if data[index] > data[index + gap]:
# Swap values
data[index], data[index + gap] = data[index + gap], data[index]
completed = False
index += 1
return data
if __name__ == "__main__":
import doctest
doctest.testmod()
user_input = input("Enter numbers separated by a comma:\n").strip()
unsorted = [int(item) for item in user_input.split(",")]
print(comb_sort(unsorted))
