cocktail shaker sort Algorithm
Cocktail shaker sort, also known as bidirectional bubble sort, shaker sort, ripple sort, or cocktail sort, is a variation of the bubble sort algorithm in which the list is sorted by comparing and swapping adjacent elements in both directions, rather than just one. This means that during each pass through the list, the algorithm first sorts the list in one direction, typically from left to right, and then reverses direction and sorts the list from right to left. This bidirectional approach can be more efficient than the traditional bubble sort algorithm, as it can move smaller and larger elements to their correct positions more quickly.
The primary advantage of the cocktail shaker sort algorithm is that it can handle cases where small elements are located towards the end of the list and large elements are located towards the beginning of the list more effectively than the standard bubble sort. This is because the algorithm moves both small and large elements towards their appropriate positions during each pass through the list, which reduces the number of comparisons and swaps needed to fully sort the list. However, despite its improvements over the traditional bubble sort, cocktail shaker sort still has an average-case and worst-case time complexity of O(n^2), making it inefficient for large datasets. In practice, more advanced sorting algorithms such as quicksort or merge sort are typically used instead of cocktail shaker sort due to their superior performance.
""" https://en.wikipedia.org/wiki/Cocktail_shaker_sort """
def cocktail_shaker_sort(unsorted: list) -> list:
"""
Pure implementation of the cocktail shaker sort algorithm in Python.
>>> cocktail_shaker_sort([4, 5, 2, 1, 2])
[1, 2, 2, 4, 5]
>>> cocktail_shaker_sort([-4, 5, 0, 1, 2, 11])
[-4, 0, 1, 2, 5, 11]
>>> cocktail_shaker_sort([0.1, -2.4, 4.4, 2.2])
[-2.4, 0.1, 2.2, 4.4]
>>> cocktail_shaker_sort([1, 2, 3, 4, 5])
[1, 2, 3, 4, 5]
>>> cocktail_shaker_sort([-4, -5, -24, -7, -11])
[-24, -11, -7, -5, -4]
"""
for i in range(len(unsorted) - 1, 0, -1):
swapped = False
for j in range(i, 0, -1):
if unsorted[j] < unsorted[j - 1]:
unsorted[j], unsorted[j - 1] = unsorted[j - 1], unsorted[j]
swapped = True
for j in range(i):
if unsorted[j] > unsorted[j + 1]:
unsorted[j], unsorted[j + 1] = unsorted[j + 1], unsorted[j]
swapped = True
if not swapped:
return unsorted
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(f"{cocktail_shaker_sort(unsorted) = }")
