Like bubble sort, cocktail sort works by iterating through the list, comparing adjacent elements and swapping them if they’re in the wrong order. The only real difference is that it alternates directions instead of only going from left to right. Because of this, cocktail sort manages to get around the “turtles problem” of bubble sort, however it still retains the same worst case computational complexity.

Much like bubble sort, cocktail sort has very little relevance in the real world and is mainly used to teach algorithms.

Complexity

Time			Space
Worst case	Best case	Average case	Worst case
O(n^2)	O(n)	O(n^2)	O(1) auxiliary

When it’s fast

Cocktail sort is at its fastest when it can reach a sorted list with a minimal number of passes. Since only adjacent elements are swapped, this means that cocktail sort performs best when elements are physically nearby their sorted positions.

Visualisation

Use the controls to playback cocktail sort on the data set.

See the Sorting Visualiser page for more visualisations.

Code

public class CocktailSort<T> : IGenericSortingAlgorithm<T> where T : IComparable
{
    public void Sort(IList<T> list)
    {
        int start = -1;
        int end = list.Count - 2;
        bool swapped;
            
        do {
            swapped = false;
            for (int i = ++start; i <= end; i++) {
                if (list[i].CompareTo(list[i + 1]) > 0) {
                    Swap(list, i, i + 1);
                    swapped = true;
                }
            }

            if (!swapped) {
                break;
            }

            swapped = false;
            for (int i = --end; i >= start; i--) {
                if (list[i].CompareTo(list[i + 1]) > 0) {
                    Swap(list, i, i + 1);
                    swapped = true;
                }
            }
        } while (swapped);
    }

    private void Swap(IList<T> list, int a, int b)
    {
        T temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }
}

public class CocktailSort {
    public static void sort(Integer[] array) {
        int start = -1;
        int end = array.length - 2;
        boolean swapped;
        
        do {
            swapped = false;
            for (int i = ++start; i <= end; i++) {
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    swapped = true;
                }
            }

            if (!swapped) {
                break;
            }

            swapped = false;
            for (int i = --end; i >= start; i--) {
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    swapped = true;
                }
            }
        } while (swapped);
    }

    private static void swap(Integer[] array, int a, int b) {
        Integer temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

/**
 * Sorts an array using cocktail sort.
 * @param {Array} array The array to sort.
 * @param {function} compare The compare function.
 * @param {function} swap A function to call when the swap operation is
 * performed. This can be used to listen in on internals of the algorithm.
 * @returns The sorted array.
 */
function sort(array, compare, swap) {
  var start = -1;
  var end = array.length - 2;
  var swapped;
  var i;

  do {
    swapped = false;
    for (i = ++start; i <= end; i++) {
      if (compare(array, i, i + 1) > 0) {
        swap(array, i, i + 1);
        swapped = true;
      }
    }

    if (!swapped) {
      break;
    }

    swapped = false;
    for (i = --end; i >= start; i--) {
      if (compare(array, i, i + 1) > 0) {
        swap(array, i, i + 1);
        swapped = true;
      }
    }
  } while (swapped);

  return array;
}

def default_compare(a, b):
  if a < b:
    return -1
  elif a > b:
    return 1
  return 0

def sort(array, compare=default_compare):
  start = -1
  end = len(array) - 2
  swapped = True
  while swapped:
    swapped = False
    for i in range(start + 1, end):
      if compare(array[i], array[i + 1]) > 0:
        array[i], array[i + 1] = array[i + 1], array[i]
        swapped = True
    if not swapped:
      break
    swapped = False
    for i in range(end, start, -1):
      if compare(array[i], array[i + 1]) > 0:
        array[i], array[i + 1] = array[i + 1], array[i]
        swapped = True
  return array

module CocktailSort
  # Sorts an array using cocktail sort.
  def self.sort(array, compare = lambda { |a, b| a <=> b })
    loop do
      swapped = false
      0.upto(array.length - 2) do |i|
        if compare.call(array[i], array[i + 1]) > 0
          array[i], array[i + 1] = array[i + 1], array[i]
          swapped = true
        end
      end
      break unless swapped

      swapped = false
      (array.length - 2).downto(0) do |i|
        if compare.call(array[i], array[i + 1]) > 0
          array[i], array[i + 1] = array[i + 1], array[i]
          swapped = true
        end
      end
      break unless swapped
    end
  end
end

Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.

 

More posts tagged Sorting