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^{2}) 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 alreadysorted lists (Θ(n^{2})), 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:
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 i1 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];
Search Encyclopedia

Featured Article
