|
The bubblesort algorithm is a simple and naïve approach to the sorting problem. Let  define a total ordering over a list  of  values. The bubblesort consists of advancing through  , swapping adjacent values ![$ A[i]$](http://images.planetmath.org:8080/cache/objects/2757/l2h/img5.png "$ A[i]$") and ![$ A[i+1]$](http://images.planetmath.org:8080/cache/objects/2757/l2h/img6.png "$ A[i+1]$") if
![$ A[i+1]\le A[i]$](http://images.planetmath.org:8080/cache/objects/2757/l2h/img7.png "$ A[i+1]\le A[i]$") holds. By going through all of  in this manner  times, one is guaranteed to achieve the proper ordering.
The following is pseudocode for the bubblesort algorithm. Note that it keeps track of whether or not any swaps occur during a traversal, so that it may terminate as soon as  is sorted.
![\begin{program} \mathrm{BubbleSort}(A, n, \le) \text{{\bf Input}: List $A$\ of $... ... \mathrm{swap}(A[i], A[i+1]) done \gets \mathbf{false} \FI \OD \OD \end{program}](http://images.planetmath.org:8080/cache/objects/2757/l2h/img11.png "\begin{program} \mathrm{BubbleSort}(A, n, \le) \text{{\bf Input}: List $A$\ of $... ... \mathrm{swap}(A[i], A[i+1]) done \gets \mathbf{false} \FI \OD \OD \end{program}")
The worst-case scenario is when  is given in reverse order. In this case, exactly one element can be put in order during each traversal, and thus all  traversals are required. Since each traversal consists of  comparisons, the worst-case complexity of bubblesort is
 .
Bubblesort is perhaps the simplest sorting algorithm to implement. Unfortunately, it is also the least efficient, even among
 algorithms. Bubblesort can be shown to be a stable sorting algorithm (since two items of equal keys are never swapped, initial relative ordering of items of equal keys is preserved), and it is clearly an in-place sorting algorithm.
| 
