Python Program for Cocktail Sort

Cocktail sort is a variation of bubble sort with a few tweaks. It is distinguished by the fact that instead of continually traversing the list from bottom to top, it alternates from bottom to top and top to bottom.

In this tutorial, we are going to perform a cocktail sort operation to sort an array.

Cocktail Sort - Basic Introduction

The algorithm uses the conventional Bubble Sort method in the forward pass, moving the biggest member to the end of the array. The Bubble Sort function is usually implemented in the backward pass, but in reverse, to shift the smallest element to the beginning of the array.

• The elements are bubbled from both the side alternatively.
• Another improvement is that the program remembers the location of the last real swap. There will be no swaps beyond this limit in the future iteration, and the algorithm will have shorter passes.
• Because cocktail sort is bidirectional, the number of potential swaps, which is the range to be checked, decreases with each pass, decreasing the total running time significantly.
• To make the method more efficient, the swapped variable is kept. If no swaps are performed in either pass, the array is sorted, and the program exits the loop.

Let us now look at the figure for better understanding:

Algorithm

As of now, we have a rough understanding of how to cocktail sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Create a function create_sort
2. Initialize two parameters array and len
3. Declare swap, start, and end
4. The element from the left side is compared to each neighboring element in the first iteration, and if necessary, exchanged.
5. The element from the right side which is recently is taken in the second iteration and compared to each element to its right and switched if necessary
6. Now the array is sorted
7. Print the sorted array

Program for Cocktail Sort

As discussed above in the algorithm, let us now dive into the programming part of the cocktail sort operation influenced by the algorithm.

def cocktail_sort(array, len):
    swap = True
    start = 0 #first
    end = len - 1 #last
    while (swap == True):
        swap = False
        for a in range(start, end):
            if (array[a] > array[a+1]):
                array[a], array[a+1] = array[a+1], array[a]
                swap = True
        if(swap == False):
            end = end-1
        for a in range(end-1, start-1, -1):
            if(array[a] > array[a+1]):
                array[a], array[a+1] = array[a+1], array[a]
                swap = True
        start = start+1
       
# driver program
array = [9, 6, 2, 9, 1]
print("The original array is: ", array)
cocktail_sort(array, len(array))
print("The sorted array is ", array)

The original array is: [9, 6, 2, 9, 1]
The sorted array is [1, 2, 6, 9, 9]

Conclusion

In this tutorial, we have performed a comb sort operation in python to sort an array. It is a stable program having the time complexity of the cocktail sort is O(n²) and the space complexity of the cocktail sort is O(1).