Python Program to Implement Cock Tail Sort

Python 1 View 5 Min Read

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.

Input/ Output

Tags: