Cocktail Sort Implementation in Python

Cocktail Sort, also known as Bidirectional Bubble Sort, Cocktail Shaker Sort, Shaker Sort, or Shuttle Sort, is a sorting algorithm that is a variation of Bubble Sort. It is a simple algorithm that works by sorting the array in both directions, i.e., from the beginning to the end and from the end to the beginning.

How Algorithm Works

The algorithm works by comparing adjacent elements of the array and swapping them if they are in the wrong order. It starts from the beginning of the array and moves toward the end, swapping elements if necessary. Once it reaches the end, it starts moving toward the beginning of the array, again swapping elements if necessary. It continues this way until no more swaps are needed, at which point the array is sorted.

The algorithm gets its name from the way it works, as it is similar to a bartender mixing a cocktail by shaking it back and forth.

Algorithm Implementation

Here is the implementation of Cocktail Sort in Python:

def cocktail_sort(arr):
    n = len(arr)
    swapped = True
    start = 0
    end = n - 1
    while swapped == True:
        swapped = False
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        if swapped == False:
            break
        swapped = False
        end = end - 1
        for i in range(end - 1, start - 1, -1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        start = start + 1

The above implementation takes an array as input and sorts it using Cocktail Sort. The algorithm works by setting a boolean variable ‘swapped’ to True and two variables ‘start’ and ‘end’ to the first and last indices of the array, respectively. It then enters a while loop that continues until no more swaps are needed.

Inside the loop, it first sets the ‘swapped’ variable to False and enters a for loop that iterates over the array from the ‘start’ index to the ‘end’ index. For each pair of adjacent elements, it checks if they are in the wrong order and swaps them if necessary. If any swaps are made, it sets the ‘swapped’ variable to True.

After the first for loop completes, it checks if the ‘swapped’ variable is still False. If it is, it means that no more swaps are needed and the array is already sorted, so it breaks out of the while loop. If the ‘swapped’ variable is True, it sets it back to False and continues to the second for loop.

The second for loop is similar to the first, but it iterates over the array from the ‘end’ index to the ‘start’ index, swapping adjacent elements if necessary. After the second for loop completes, it increments the ‘start’ index by 1 and decrements the ‘end’ index by 1, and the while loop repeats.

Time and Space Complexity

The time complexity of Cocktail Sort is O(n^2), where n is the number of elements in the array. This is because the algorithm performs two passes over the array, each taking O(n) time, and potentially many swaps are made in each pass. However, in the best case scenario, when the array is already sorted, the time complexity reduces to O(n).

The space complexity of Cocktail Sort is O(1), as the algorithm only requires a constant amount of extra space to perform the sorting. It does not create any new arrays or data structures, and only swaps the elements in the input array in place.

Example Run

Let’s see an example run of Cocktail Sort on an array of integers:

arr = [4, 2, 7, 1, 3, 6, 5]
cocktail_sort(arr)

print(arr)

The above code creates an array of integers and calls the ‘cocktail_sort’ function on it. It then prints the sorted array.

Here is the output:

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

As we can see, the Cocktail Sort algorithm has successfully sorted the array in ascending order.

Conclusion

Cocktail Sort is a simple and easy-to-implement sorting algorithm that can be used to sort arrays of any size. It is a variation of Bubble Sort that sorts the array in both directions, from the beginning to the end and from the end to the beginning. Although it has a worst-case time complexity of O(n^2), it can perform well on small arrays and has a best-case time complexity of O(n) when the array is already sorted.