Bubble sort needs &Theta(*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 already-sorted 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. Also, reversing the order in which the list is traversed for each pass improves the efficiency somewhat.

The bubble sort algorithm is:

- Compare adjacent elements. If the first is greater than the second, swap them.
- 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.
- Repeat the steps for all elements except the last one.
- 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 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];