Like bubble sort, odd-even sort works by iterating through the list, comparing adjacent elements and swapping them if they’re in the wrong order. The unique characteristic of odd-even sort, and also how it got its name, is how the sort’s iterations alternate between sorting odd/even and even/odd indexed pairs.

Much like bubble sort, odd-even 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)	Θ(n)	O(n^2)	O(1) auxiliary

When it’s fast

Odd-even sort is fast when all elements in the input array are close to their sorted indexes. Since odd-even sort must perform both an odd and an even iteration, it’s possible to sort an input array where some elements are 2 indexes off their sorted position in this odd and even iteration.

When it’s slow

Unlike other bubble sort derivatives like cocktail sort and comb sort, odd-even sort struggles to handle the “turtles problem” where indexes that are originally way off their sorted position push the number of iterations out significantly. If the largest item in the array was at the start then odd-even sort would perform at its worst in terms of iterations and comparisons.

Visualisation

Use the controls to playback odd even sort on the data set.

See the Sorting Visualiser page for more visualisations.

Code

public class OddEvenSort<T> : IGenericSortingAlgorithm<T> where T : IComparable
{
    public void Sort(IList<T> list)
    {
        var sorted = false;
        while (!sorted) {
            sorted = InnerSort(list, 1);
            sorted = InnerSort(list, 0) && sorted;
        }
    }

    private bool InnerSort(IList<T> list, int i)
    {
        var sorted = true;
        for (; i < list.Count - 1; i += 2)
        {
            if (list[i].CompareTo(list[i + 1]) > 0)
            {
                Swap(list, i, i + 1);
                sorted = false;
            }
        }
        return sorted;
    }

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

public class OddEvenSort {
    public static <T extends Comparable<T>> void sort(T[] array) {
        boolean sorted = false;
        while (!sorted) {
            sorted = innerSort(array, 1);
            sorted = innerSort(array, 0) && sorted;
        }
    }

    private static <T extends Comparable<T>> boolean innerSort(T[] array, Integer i) {
        boolean sorted = true;
        for (; i < array.length - 1; i += 2)
        {
            if (array[i].compareTo(array[i + 1]) > 0)
            {
                swap(array, i, i + 1);
                sorted = false;
            }
        }
        return sorted;
    }

    private static <T extends Comparable<T>> void swap(
            T[] array, int a, int b) {
        T temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

/**
 * Sorts an array using odd even 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 sorted = false;
  while (!sorted) {
    sorted = innerSort(array, 1, compare, swap);
    sorted = innerSort(array, 0, compare, swap) && sorted;
  }
  return array;
}

/**
 * Compares every second element of an array with its following element and
 * swaps it if not in order using a compare function.
 * @param {Array} array The array to sort.
 * @param {number} i The index to start at, should be either 0 or 1.
 * @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 innerSort(array, i, compare, swap) {
  var sorted = true;
  for (; i < array.length - 1; i += 2) {
    if (compare(array, i, i + 1) > 0) {
      swap(array, i, i + 1);
      sorted = false;
    }
  }
  return sorted;
}

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

def sort(array, compare=default_compare):
  sorted = False
  while not sorted:
    sorted = inner_sort(array, 1, compare)
    sorted = inner_sort(array, 0, compare) and sorted
  return array

def inner_sort(array, start_i, compare):
  sorted = True
  for i in range(start_i, len(array) - 1, 2):
    if compare(array[i], array[i + 1]) > 0:
      array[i], array[i + 1] = array[i + 1], array[i]
      sorted = False
  return sorted

module OddEvenSort
  # Sorts an array using odd-even sort.
  def self.sort(array, compare = lambda { |a, b| a <=> b })
    sorted = false
    while !sorted
      sorted = self.innerSort(array, 1, compare)
      sorted = self.innerSort(array, 0, compare) && sorted
    end
  end

private

  # Compares every second element of an array with its following element and
  # swaps it if not in order using a compare function
  def self.innerSort(array, start, compare)
    sorted = true
    (start..array.length - 2).step(2) do |i|
      if compare.call(array[i], array[i + 1]) > 0
        array[i], array[i + 1] = array[i + 1], array[i]
        sorted = false
      end
    end
    return sorted
  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