## You are here

Homebubblesort

## Primary tabs

# 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.

BubbleSort(A, n, ≤) Input: List $A$ of $n$ values. Output: $A$ sorted with respect to relation $\leq$. Procedure: done ←false \WHILE(not done) \DOdone ←true \FORi←0 \TOn-1 \DO\IFA[i+1]≤A[i] \THENswap(A[i], A[i+1]) done ←false \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 $\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.

## Mathematics Subject Classification

68P10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections