# Python Program to Implement Cock Tail Sort

Cocktail Sort, also known as Bidirectional Bubble Sort or Shaker Sort, is a simple sorting algorithm that shares similarities with the Bubble Sort algorithm. Like Bubble Sort, Cocktail Sort repeatedly steps through the list of elements to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. The key difference is that Cocktail Sort sorts the list in both directions: from left to right and then from right to left.

## Problem Statement

You are given an array of integers. Your task is to implement the Cocktail Sort algorithm to sort the given array in ascending order.

## Python Program to Implement Cock Tail Sort

```def cocktail_sort(arr):
n = len(arr)
swapped = True
start = 0
end = n - 1

while swapped:
swapped = False

# Move the largest element to the right
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

# Decrement the end pointer
end -= 1

# Move the smallest element to the left
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

# Increment the start pointer
start += 1

# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
cocktail_sort(arr)
print("Sorted array is:", arr)
```

## How it Works

1. Initialization:
• Start with the leftmost and rightmost pointers, `start` and `end`, respectively. These pointers define the range of the array that is currently being considered for sorting.
• Initialize a boolean variable `swapped` as `True` to indicate that at least one swap has occurred in the current pass.
2. First Pass (Left to Right):
• Begin by iterating from the element at index `start` to the element at index `end - 1`.
• Compare each element with its adjacent element to the right.
• If the current element is greater than the next element, swap them and set `swapped` to `True`.
• This pass moves the largest element to the rightmost position within the current range.
3. Second Pass (Right to Left):
• Decrement the `end` pointer by one. This effectively reduces the range of elements that need to be considered for sorting in the next pass.
• Begin iterating from the element at index `end - 1` to the element at index `start`.
• Compare each element with its adjacent element to the left.
• If the current element is greater than the next element, swap them and set `swapped` to `True`.
• This pass moves the smallest element to the leftmost position within the reduced range.
4. Repeat:
• The algorithm alternates between the left-to-right and right-to-left passes until no swaps are made during a complete pass.
• This means that the elements have been rearranged such that the entire array is sorted, and no more swaps are needed.
5. Optimization:
• During each pass, the largest and smallest elements gradually “bubble up” to their correct positions.
• As a result, the range of elements that need to be considered for sorting in subsequent passes can be reduced.
• After each successful pass, the `start` and `end` pointers are adjusted to reflect the new range of unsorted elements.
6. Termination:
• The algorithm terminates when a complete pass is made without any swaps. This indicates that the array is fully sorted.
• At this point, the `swapped` flag remains `False`, breaking the loop.

The algorithm’s bidirectional nature allows it to efficiently handle cases where smaller elements are at the end of the array (reducing the number of unnecessary swaps) and larger elements are at the beginning (reducing the number of comparisons).

Keep in mind that Cocktail Sort is not as efficient as some other sorting algorithms for larger datasets, but it provides insights into sorting logic and optimization techniques. Its simplicity makes it a valuable teaching tool for understanding sorting algorithms.