Bubble sort needs &Theta(n2) 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 (Θ(n2)), 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. Also, reversing the order in which the list is traversed for each pass improves the efficiency somewhat.
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 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 if using the xor swap algorithm. In C, the swapping can be done by:
\narray[j] = array[j] ^ array[j+1]; array[j+1] = array[j] ^ array[j+1]; array[j] = array[j] ^ array[j+1];