Cocktail Sort Algorithm

Introduction to Cocktail Sort

Cocktail sort is a variation of bubble sort that sorts in both directions on each pass through the list. This bidirectional approach helps to move elements more quickly to their correct positions, potentially improving performance over bubble sort. It is also known as bidirectional bubble sort or shaker sort. The time complexity of cocktail sort is O(n^2) in the worst case.

Step-by-Step Process

Consider an array with the following elements:


[5, 1, 4, 2, 8, 0, 2]

To sort this array using cocktail sort, follow these steps:

  1. Initialize Variables: Set the starting and ending points for the unsorted portion of the array.
  2. Forward Pass: Iterate through the array from left to right, comparing and swapping adjacent elements if they are in the wrong order.
  3. Backward Pass: Iterate through the array from right to left, comparing and swapping adjacent elements if they are in the wrong order.
  4. Repeat: Continue the forward and backward passes until no swaps are needed, indicating that the array is sorted.

Let's apply these steps to the example array:

  • Initial array: [5, 1, 4, 2, 8, 0, 2]
  • Forward pass: [1, 4, 2, 5, 0, 2, 8]
  • Backward pass: [1, 2, 0, 4, 2, 5, 8]
  • Forward pass: [1, 0, 2, 2, 4, 5, 8]
  • Backward pass: [0, 1, 2, 2, 4, 5, 8]
  • Array is sorted.

Pseudo Code for Cocktail Sort

Below is the pseudo code for the cocktail sort algorithm:


function cocktailSort(array)
    n = length(array)
    swapped = true
    start = 0
    end = n - 1
    while swapped do
        swapped = false
        for i = start to end - 1 do
            if array[i] > array[i + 1] then
                swap(array[i], array[i + 1])
                swapped = true
            end if
        end for
        if not swapped then
            break
        end if
        swapped = false
        end = end - 1
        for i = end - 1 to start do
            if array[i] > array[i + 1] then
                swap(array[i], array[i + 1])
                swapped = true
            end if
        end for
        start = start + 1
    end while
end function

Explanation:

  • Initialize: The cocktailSort function initializes variables for the start and end points of the unsorted portion of the array and a flag to indicate if a swap has occurred.
  • Forward Pass: The algorithm performs a forward pass through the array, comparing and swapping adjacent elements if needed.
  • Check Swap: If no swaps occurred during the forward pass, the array is already sorted, and the algorithm breaks out of the loop.
  • Backward Pass: If a swap occurred, the algorithm performs a backward pass through the array, comparing and swapping adjacent elements if needed.
  • Repeat: The process repeats until no swaps are needed in both forward and backward passes.

Python Program to Implement Cocktail Sort

def cocktail_sort(arr):
    n = len(arr)
    swapped = True
    start = 0
    end = n - 1
    while swapped:
        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 not swapped:
            break
        swapped = False
        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 += 1
    return arr

# Example usage:
array = [5, 1, 4, 2, 8, 0, 2]
print("Original array:", array)
sorted_array = cocktail_sort(array)
print("Sorted array:", sorted_array)  # Output: [0, 1, 2, 2, 4, 5, 8]

This Python program defines a function to perform cocktail sort on an array. The function iterates through the array in both directions, comparing and swapping elements as needed, until the array is sorted.