Bubble sort is an O(n^2) sorting algorithm that gets its name because it “bubbles up” elements to their correct positions. This is done by iterating through the list multiple times, swapping elements with their neighbours if they are not in the correct order.

Elements are only ever swapped with their neighbours and it is done in somewhat of an unorganised manner, this can lead to an obscene amount of swaps. This is why it’s so difficult to recommend bubble sort for anything, it even performs badly against other O(n^2) algorithms. Algorithms like insertion sort and selection sort in contrast perform considerably better in practise.

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

Bubble sort is fast when the list is either sorted or almost sorted, only requiring swapping adjacent elements, meaning only one or two iterations are needed respectively. This is providing the implementation is using an “optimised” version of the algorithm that tracks whether no swaps take place in an iteration and exits early (like sortWhile below).

Bubble sort also has no problem sorting large elements that are near the front of the list (known as rabbits), small elements near the end of the list (known as turtles) will considerably slow down the algorithm though. This is because elements are only moved closer to the start of the list once per iteration at most, elements can move closer to the end many times.

To better understand this point consider the list [5, 2, 3, 4, 1] where only the elements 1 and 5 are displaced. The 5 will be moved to the end of the list in the first iteration of bubble sort whereas the 1 will take all 4 (n-1) iterations to reach the start.

Visualisation

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

See the Sorting Visualiser page for more visualisations.

Code

for loop version

This is the most common implementation of bubble sort.

public class BubbleSort<T> : IGenericSortingAlgorithm<T> where T : IComparable
{
    public void Sort(IList<T> list)
    {
        for (int i = 0; i < list.Count - 1; i++)
        {
            for (int j = 1; j < list.Count - i; j++)
            {
                if (list[j - 1].CompareTo(list[j]) > 0)
                {
                    Swap(list, j, j - 1);
                }
            }
        }
    }

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

public class BubbleSort {
    public static void sort(Integer[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 1; j < array.length - i; j++) {
                if (array[j - 1] > array[j]) {
                    swap(array, j, j - 1);
                }
            }
        }
    }

    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 bubble 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) {
  for (var i = 0; i < array.length - 1; i++) {
    for (var j = 1; j < array.length - i; j++) {
      if (compare(array, j - 1, j) > 0) {
        swap(array, j, j - 1);
      }
    }
  }
  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):
  for i in range(0, len(array) - 1):
    for j in range(1, len(array) - i):
      if compare(array[j - 1], array[j]) > 0:
        array[j], array[j - 1] = array[j - 1], array[j]
  return array

module BubbleSort
  # Sorts an array using bubble sort.
  def self.sort(array, compare = lambda { |a, b| a <=> b })
    (0..array.length - 1).each do |i|
      (1..array.length - 1).each do |j|
        if compare.call(array[j - 1], array[j]) > 0
          array[j], array[j - 1] = array[j - 1], array[j]
        end
      end
    end
  end
end

while loop version

This is an optimised version of bubble sort using a while loop that will exit early when it can and doesn’t attempt to sort elements after the element that was swapped last in the previous iteration.

public class BubbleSortOptimised<T> : IGenericSortingAlgorithm<T> where T : IComparable
{
    public void Sort(IList<T> list)
    {
        int unsortedBelow = list.Count;
        while (unsortedBelow != 0) {
            int lastSwap = 0;
            for (int i = 1; i < unsortedBelow; i++) {
                if (list[i - 1].CompareTo(list[i]) > 0) {
                    Swap(list, i, i - 1);
                    lastSwap = i;
                }
            }
            unsortedBelow = lastSwap;
        }
    }

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

public class BubbleSortOptimised {
    public static void sort(Integer[] array) {
        int unsortedBelow = array.length;
        while (unsortedBelow != 0) {
            int lastSwap = 0;
            for (int i = 1; i < unsortedBelow; i++) {
                if (array[i - 1] > array[i]) {
                    swap(array, i, i - 1);
                    lastSwap = i;
                }
            }
            unsortedBelow = lastSwap;
        }
    }

    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 bubble 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 unsortedBelow = array.length;
  while (unsortedBelow !== 0) {
    var lastSwap = 0;
    for (var i = 1; i < unsortedBelow; i++) {
      if (compare(array, i - 1, i) > 0) {
        swap(array, i, i - 1);
        lastSwap = i;
      }
    }
    unsortedBelow = lastSwap;
  }
  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):
  unsorted_below = len(array)
  while unsorted_below != 0:
    last_swap = 0
    for i in range(1, unsorted_below):
      if compare(array[i - 1], array[i]) > 0:
        array[i], array[i - 1] = array[i - 1], array[i]
        last_swap = i
    unsorted_below = last_swap
  return array

module BubbleSortOptimised
  # Sorts an array using the optimised version of bubble sort.
  def self.sort(array, compare = lambda { |a, b| a <=> b })
    unsorted_below = array.length
    while unsorted_below != 0
      last_swap = 0
      (1..unsorted_below - 1).each do |i|
        if compare.call(array[i - 1], array[i]) > 0
          array[i], array[i - 1] = array[i - 1], array[i]
          last_swap = i
        end
      end
      unsorted_below = last_swap
    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