bubblesort

The bubblesort algorithm is a simple and naïve approach to the sorting problem. Let $\le$ 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]\le 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.

• $\mathrm{BubbleSort}(A,n,\le )$Input: List $A$ of $n$ values.Output: $A$ sorted with respect to relation $\le$.Procedure:$done\leftarrow \mathrm{𝐟𝐚𝐥𝐬𝐞}$$\text{𝗐𝗁𝗂𝗅𝖾}$$(\text{not }done)$$\text{𝖽𝗈}$$done\leftarrow \mathrm{𝐭𝐫𝐮𝐞}$$\text{𝖿𝗈𝗋}$$i\leftarrow 0$$\text{𝗍𝗈}n-1$$\text{𝖽𝗈}$$\text{𝗂𝖿}$$A[i+1]\le A[i]$$\text{𝗍𝗁𝖾𝗇}$$\mathrm{swap}(A[i],A[i+1])$$done\leftarrow \mathrm{𝐟𝐚𝐥𝐬𝐞}$$$fi$$od$$od

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 $𝒪(n^2)$.

Bubblesort is perhaps the simplest sorting algorithm to implement. Unfortunately, it is also the least efficient, even among $𝒪(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.