Bubble sort

Bubble sort is a simple sort algorithm that needs O(n²) comparisons to sort n items and can sort in place. It is one of the simplest sorting algorithms to understand, but is generally considered too inefficient for serious work sorting large numbers of elements. It is essentially equivalent to insertion sort --- it compares and swaps the same pairs of elements, just in a different order. Since the insertion sort and bubble sort are so simple, though, they tend to be the most efficient sorting algorithms for sorting small numbers of elements.

The bubble sort algorithm is:

1. compare adjacent elements. If the first is greater than the second, swap them.
2. do this for each pair of adjacent elements, starting with the first two and ending with the last two. At this point the last element should be the greatest (it has "bubbled" to the top).
3. repeat the steps for all elements except the last one.
4. keep repeating for one fewer element each time, until you have no more pairs to compare.

A simple implementation of bubble sort in Python:

def bubblesort(array, cmp = lambda x, y: x > y):
    for i in range( len(array) ):
        for j in range( len(array)-1-i ):
            if cmp(array[j], array[j+1]):
                ( array[j], array[j+1] ) = ( array[j+1], array[j] )

Or in the C programming language:

void bubbleSort(int *array, int length)
{
  int i, j;
  for(i = length - 1; i > 0; i--)
    for(j = 0; j < i; j++)
      if(array[j] > array[j+1]) /* compare neighboring elements */
      {
        int temp;

        temp = array[j];    /* swap array[j] and array[j+1] */
        array[j] = array[j+1];
        array[j+1] = temp;
      }
}

---

/Talk