The Bubble Sort Algorithm

Bubble Sort: Basic Idea

The idea of this sort is to continue making passes over the sequence of values, or a subset of the sequence, checking adjacent pairs of values and exchanging those pairs that are "out of order", until the list is sorted.

Bubble Sort: Name, Input and Output

Name: SortByBubble

Input:

• A sequence of values, all of a given type, which is called s
• Two positions in the sequence, to determine the range of values within the sequence that will be sorted, which are called firstPosition and lastPosition, and which satisfy firstPosition <= lastPosition

Output:

• The sequence of values s, sorted in ascending order between firstPosition and lastPosition, inclusive

Bubble Sort: Pseudocode

Algorithm SortByBubble(s, firstPosition, lastPosition)
------------------------------------------------------
while values not yet sorted
    for each pair of adjacent elements
        if they are out of order, swap them
endwhile

Note that after each iteration the number of remaining unsorted values has been reduced by one.

Bubble Sort: Performance

We say that the bubble sort algorithm is, in general, a O(n²) algorithm, or that it has "quadratic time complexity". The analysis for this algorithm is similar to that for many other exchange-based sorting algorithms which consist essentially of two nested loops.