Bubble sort

Bubble sort is a simple sorting algorithm. It takes a lot of passes through the list to be sorted, comparing two items at a time, swapping these two items in the correct order if necessary. Bubble sort gets its name from the fact that the items that belong at the top of the list gradually "float" up there.

Bubble sort needs Θ(n²) comparisons to sort n items and can sort in place. It is one of the simplest sorting algorithms to understand but is generally 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. Naive implementations of bubble sort (like those below) usually perform badly on already-sorted lists (Θ(n²)), while insertion sort needs only Θ(n) operations in this case. Hence most modern algorithm textbooks strongly discourage use of the algorithm, or even avoid mentioning it, and prefer insertion sort instead. It is possible to reduce the best case complexity to Θ(n) if a flag is used to denote whether any swaps were necessary during the first run of the inner loop. In this case, no swaps would indicate an already sorted list.

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.
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):
    # Values for i from len(array)-1 down to 1 inclusive.
    for i in range(len(array)-1, 0, -1):
        # Values for j from 0 to i-1 inclusive.
        for j in range(i):
            if 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;
      }
}

Note: You do not need the temp variable in the C programming language example. Using the Xor swap algorithm, the swapping can be done by:

       array[j]   = array[j] ^ array[j+1];
       array[j+1] = array[j] ^ array[j+1];
       array[j]   = array[j] ^ array[j+1];