bubblesort
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 and if holds. By going through all of in this manner 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 is sorted.
-
\@startfield
\@stopfield\@addfield\@startfieldInput: List of values.\@stopfield\@addfield\@startfieldOutput: sorted with respect to relation .\@stopfield\@addfield\@startfieldProcedure:\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\=\+\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\=\+\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\=\+\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\=\+\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-fi\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-od\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-od\@stopfield\@addfield\@startfield\@stopfield\@addfield
Analysis
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.
Title | bubblesort |
---|---|
Canonical name | Bubblesort |
Date of creation | 2013-03-22 12:31:07 |
Last modified on | 2013-03-22 12:31:07 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 9 |
Author | CWoo (3771) |
Entry type | Algorithm |
Classification | msc 68P10 |
Synonym | bubble sort |
Related topic | SortingProblem |
Related topic | StableSortingAlgorithm |
Related topic | InPlaceSortingAlgorithm |