Odd-even sort
Odd-even sort is an O(n^2) variation of the bubble sort sorting algorithm.
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.