Visualizing the Cocktail Sort in Flutter

1. What Is Cocktail Sort?

Cocktail Sort (also known as Bidirectional Bubble Sort or Shaker Sort) is a variation of Bubble Sort that sorts in both directions — left to right and then right to left — in each iteration.

This bi-directional approach helps move both the largest and smallest elements into place with each pass, making it slightly more efficient than regular Bubble Sort in certain cases.

2. How Cocktail Sort Works

Loop forward through the array:
- Swap adjacent values if they’re in the wrong order.
After reaching the end, loop backward:
- Swap in reverse direction if needed.
Repeat until no more swaps are needed.

This “shakes” the data from both ends — hence the name!

3. Cocktail Sort Pseudocode

start = 0
end = n - 1
swapped = true

while swapped:
    swapped = false

    // Forward pass
    for i from start to end - 1:
        if array[i] > array[i + 1]:
            swap(array[i], array[i + 1])
            swapped = true

    if not swapped:
        break

    swapped = false
    end = end - 1

    // Backward pass
    for i from end - 1 to start:
        if array[i] > array[i + 1]:
            swap(array[i], array[i + 1])
            swapped = true

    start = start + 1

4. Step-by-Step Example

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

Forward Pass 1:

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

Backward Pass 1:

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

Forward Pass 2:

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

Backward Pass 2:

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

Now the array is sorted!

5. Time and Space Complexity

Case	Time Complexity
Best	O(n) (with optimization)
Average	O(n²)
Worst	O(n²)

Space Complexity: O(1)
Stable Sort: Yes
In-place Sort: Yes

6. Cocktail Sort in Dart (Flutter-Friendly)

Future<void> cocktailSort(List<int> array, Function(List<int>) onUpdate) async {
  int start = 0;
  int end = array.length - 1;
  bool swapped = true;

  while (swapped) {
    swapped = false;

    // Forward pass
    for (int i = start; i < end; i++) {
      if (array[i] > array[i + 1]) {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        swapped = true;
      }
      onUpdate(List.from(array));
      await Future.delayed(Duration(milliseconds: 300));
    }

    if (!swapped) break;

    swapped = false;
    end--;

    // Backward pass
    for (int i = end - 1; i >= start; i--) {
      if (array[i] > array[i + 1]) {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        swapped = true;
      }
      onUpdate(List.from(array));
      await Future.delayed(Duration(milliseconds: 300));
    }

    start++;
  }
}

7. Visualization with Flutter + CustomPaint

To animate Cocktail Sort in Flutter:

Use CustomPaint to draw vertical bars for each element.
Highlight the current forward or backward movement direction (maybe change bar color or add arrow icons).
Redraw the canvas after each onUpdate() call.
Label the active indices being compared or swapped for better clarity.

This dynamic two-way movement offers a unique and engaging animation for learners.

8. When Should You Use Cocktail Sort?

Use Cocktail Sort when:

You’re visualizing sorting for education.
You want to slightly improve on Bubble Sort without adding complexity.
You care about stability and in-place sorting.

Avoid it for large datasets or performance-critical tasks — better algorithms like Merge Sort or QuickSort exist for those.

9. Summary

Cocktail Sort improves on Bubble Sort by sorting in both directions. It reduces unnecessary passes when small elements are near the end and large elements are near the start. Though still quadratic in performance, it provides better behavior in certain nearly-sorted cases — and it’s fantastic for visual learning.

👀 Next up: let’s go deeper into linear-time territory with Counting Sort!