# 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:

**Initialize Variables**: Set the starting and ending points for the unsorted portion of the array.**Forward Pass**: Iterate through the array from left to right, comparing and swapping adjacent elements if they are in the wrong order.**Backward Pass**: Iterate through the array from right to left, comparing and swapping adjacent elements if they are in the wrong order.**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.