Solution: Bubbling in Both Directions

Let’s start from the chapter’s bubble sort with early termination, with the swap moved into a swap helper:

public static void bubbleSort(int[] arr) {
  int n = arr.length;
  for (int i = 0; i < n - 1; i++) {
    boolean swapped = false;
    for (int j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        swapped = true;
      }
    }
    if (!swapped) {
      break;
    }
  }
}

The inner loop runs over the unsorted portion, which is arr[0] through arr[n - 1 - i]. Its front is always index 0, and only its end moves. Once we add backward passes, the front will move too, so the first change is to name both ends. Let’s keep start and end as the first and last index of the unsorted portion, and let the outer loop run while the unsorted portion has at least two elements:

public static void cocktailShakerSort(int[] arr) {
  int start = 0;
  int end = arr.length - 1;
  boolean swapped = true;
  while (swapped && start < end) {
    swapped = false;
    for (int j = start; j < end; j++) {  // forward pass: largest to end
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        swapped = true;
      }
    }
    end--;
  }
}

This is still bubble sort.

Now add the backward pass. It runs from the new end down to start, comparing each element with the one to its left and swapping when they are out of order. After it, the smallest remaining element is at start, so start moves right by one:

public static void cocktailShakerSort(int[] arr) {
  int start = 0;
  int end = arr.length - 1;
  boolean swapped = true;
  while (swapped && start < end) {
    swapped = false;
    for (int j = start; j < end; j++) {  // forward pass: largest to end
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        swapped = true;
      }
    }
    end--;
    if (!swapped) {
      break;
    }
    swapped = false;
    for (int j = end; j > start; j--) {  // backward pass: smallest to start
      if (arr[j - 1] > arr[j]) {
        swap(arr, j - 1, j);
        swapped = true;
      }
    }
    start++;
  }
}

The if (!swapped) break; between the two passes is there so that a clean forward pass ends the sort right away. The loop condition catches a clean backward pass, so no check is needed after that one.

Let’s trace it on [2, 3, 4, 5, 1]. Here is the initial state, with start at index 0 and end at index 4:

┌───┬───┬───┬───┬───┐
│ 2 │ 3 │ 4 │ 5 │ 1 │
└───┴───┴───┴───┴───┘
  ↑               ↑
start            end

The forward pass compares (2, 3), (3, 4), and (4, 5), all in order, then (5, 1), which it swaps. That is four comparisons and one swap. Then end moves to 3:

┌───┬───┬───┬───┬───┐
│ 2 │ 3 │ 4 │ 1 │░5░│
└───┴───┴───┴───┴───┘
  ↑           ↑
start        end

The shaded cell is settled. The pass swapped something, so we go on to the backward pass. It compares (4, 1), (3, 1), and (2, 1), and swaps each time, moving the 1 to the front. That is three comparisons and three swaps. Then start moves to 1:

┌───┬───┬───┬───┬───┐
│░1░│ 2 │ 3 │ 4 │░5░│
└───┴───┴───┴───┴───┘
      ↑       ↑
    start    end

The next forward pass compares (2, 3) and (3, 4), finds both in order, and swaps nothing. That is two comparisons. end moves to 2, the check finds swapped still false, and the sort stops.

Does this handle the edge cases correctly?

  • If the array is empty, end is -1, so start < end is false and the loop never runs.
  • If the array has one element, start and end are both 0, so again the loop never runs.
  • If the array is already sorted, the forward pass swaps nothing, and the check between the passes ends the sort. That is comparisons, the same as bubble sort with early termination.
  • If the array has two elements, the forward pass compares them once, swaps if needed, and end becomes 0. If it swapped, the backward pass runs from 0 down to 0, which is no iterations, and start becomes 1. Either way the loop ends.

On [2, 3, 4, 5, 1] the sort made comparisons and swaps. Bubble sort with early termination made comparisons and swaps on the same array. The saving is small here because the array is small. On an array of a thousand elements that is sorted except that the smallest one is at the end, bubble sort needs about a thousand passes and about half a million comparisons. Cocktail shaker sort needs one forward pass, one backward pass, and one clean forward pass, about three thousand comparisons.

The swap count does not change. Every swap is still of an adjacent out-of-order pair, so each one removes exactly one inversion, and the total is the number of inversions in the input. That is the same as bubble sort and insertion sort.

The worst case does not change either. On a reverse-sorted array every comparison is followed by a swap, no pass is ever clean, and the sort makes all comparisons. It is still .

Stability does not change. Both passes swap only adjacent elements, and only when the left one is strictly greater than the right, so two equal elements are never swapped past each other.

What changes is which nearly sorted inputs the sort handles well. Bubble sort with early termination is fast when the out-of-place elements need to move right and slow when they need to move left. Cocktail shaker sort moves an element in either direction by any distance in one forward pass plus one backward pass, so an array with a few out-of-place elements costs a few passes whichever way they need to go.