cocktailShakerSort<E> function

void cocktailShakerSort<E>(
  1. List<E> list, {
  2. int? begin,
  3. int? end,
  4. Comparator<E>? compare,
})

Sorts the list of numbers using the Cocktail shaker sort with a few improvements over the base algorithm.

Parameters

  • list is any list of items to be sorted.
  • To perform partial sorting, you can specify the begin or end.
  • begin is the start index of the range to be sorted.
  • If begin is negative, range starts at the 0
  • If begin is not below the length of the list, range will be empty.
  • end is the final index if the range to be sorted. It is exclusive.
  • If end is above the length of the list, it will be ignored.
  • If end is negative, the absolute value of it will be subtracted from the length of the list to determine where the range ends.
  • If end is not greater than the begin, the range will be empty.
  • compare is a custom compare to order the list elements. If it is null and list items are not Comparable, TypeError is thrown.

Details

This algorithm is known by many other names, e.g.: bidirectional bubble sort, cocktail sort, shaker sort, ripple sort, shuffle sort, shuttle sort etc. It extends bubble sort by operating in two directions.

Although the original cocktail shaker sort is very slow, with a few optimization, it can work rather well. It can run in O(n) time in best case for already or partially sorted lists.

Optimizations

Here are the list of optimizations done in this implementation:

  1. Excludes the first and last end of the range after each iteration. (since they are already in proper place, no need to include them.)
  2. Keeping separate logic for when compare function is provided or not.

Complexity: Time O(n^2) | Space O(1)
Best Case: Time O(n) | Space O(1)

Implementation

void cocktailShakerSort<E>(
  List<E> list, {
  int? begin,
  int? end,
  Comparator<E>? compare,
}) {
  int b, e;
  int n = list.length;

  // Find the range given the parameters.
  b = 0;
  e = n;
  if (begin != null && b < begin) {
    b = begin;
  }
  if (end != null && end < e) {
    e = end;
    if (e < 0) e += n;
  }

  if (compare == null) {
    cocktailSortDefault(list, b, e);
  } else {
    cocktailSortCustom(list, b, e, compare);
  }
}