# bubblesort

The bubblesort algorithm is a simple and naïve approach to the sorting problem. Let $\leq$ define a total ordering over a list $A$ of $n$ values. The bubblesort consists of advancing through $A$, swapping adjacent values $A[i]$ and $A[i+1]$ if $A[i+1]\leq A[i]$ holds. By going through all of $A$ in this manner $n$ times, one is guaranteed to achieve the proper ordering.

## Pseudocode

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 $A$ is sorted.

• \@startfield

$\mathrm{BubbleSort}(A,n,\leq)$\@stopfield\@addfield\@startfieldInput: List $A$ of $n$ values.\@stopfield\@addfield\@startfieldOutput: $A$ sorted with respect to relation $\leq$.\@stopfield\@addfield\@startfieldProcedure:\@stopfield\@addfield\@startfield$done\leftarrow\mathbf{false}$\@stopfield\@addfield\@startfield$\mbox{\rm\bf\sf while}\$\=\+$(\text{not\ }done)$\@stopfield\@addfield\@startfield$\@ifatmargin\ \mbox{\rm\bf\sf do}\$\@stopfield\@addfield\@startfield$done\leftarrow\mathbf{true}$\@stopfield\@addfield\@startfield$\mbox{\rm\bf\sf for}\$\=\+$i\leftarrow 0$\@stopfield\@addfield\@startfield$\@ifatmargin\ \mbox{\rm\bf\sf to}\ n-1$\@stopfield\@addfield\@startfield$\@ifatmargin\ \mbox{\rm\bf\sf do}\$\@stopfield\@addfield\@startfield$\mbox{\rm\bf\sf if}\$\=\+$A[i+1]\leq A[i]$\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield$\@ifatmargin\ \mbox{\rm\bf\sf then}\$\=\+$\mathrm{swap}(A[i],A[i+1])$\@stopfield\@addfield\@startfield$done\leftarrow\mathbf{false}$\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield$\@ifatmargin\$\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-fi\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield$\@ifatmargin\$\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-od\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield$\@ifatmargin\$\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-od\@stopfield\@addfield\@startfield\@stopfield\@addfield

## Analysis

The worst-case scenario is when $A$ is given in reverse order. In this case, exactly one element can be put in order during each traversal, and thus all $n$ traversals are required. Since each traversal consists of $n-1$ comparisons, the worst-case complexity of bubblesort is $\mathcal{O}(n^{2})$.

Bubblesort is perhaps the simplest sorting algorithm to implement. Unfortunately, it is also the least efficient, even among $\mathcal{O}(n^{2})$ 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.

Title bubblesort Bubblesort 2013-03-22 12:31:07 2013-03-22 12:31:07 CWoo (3771) CWoo (3771) 9 CWoo (3771) Algorithm msc 68P10 bubble sort SortingProblem StableSortingAlgorithm InPlaceSortingAlgorithm