Bubble sort

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
A bubble sort illustrated

Bubble sort is a simple sorting algorithm. It is simple to understand, so it is usually taught to new students. It is not as efficient as some other sorting algorithms.

Bubble sort's name comes from the fact that each item in the list “bubbles” up to where it should go, like bubbles in water.

Algorithm[change | change source]

The algorithm compares pairs of elements in a list. The elements constituting pairs are next to each other. Starting at one end of the vector, pairs are sequentially assumed. That means for example, the first and second element are compared, then the second and third element, and then the third and fourth, and so on. If the current pair is out of order, its elements are swapped in place. This process – of comparing two elements – is done over and over again, until the vector is sorted. The vector is sorted, when no pairs had to be swapped.

In the best case, the vector being sorted, the algorithm's complexity is O(n) (Big O notation). In the worst case, the vector being reversely sorted, O(n²).

Implementation[change | change source]

In an imperative programming language, bubble sort can be implemented by using a flag variable and looping through the array's elements:

  1. Set the flag sorted.
  2. Starting at one end, consider every neighbored pair of elements in a vector one after another (in their order).
  3. If a pair's elements are out of order, swap them, and clear the flag sorted.
  4. Repeat the previous steps until sorted remains set.

Alternatively, since the greatest value ascends to the highest index within the first iteration and then has reached its final right position, two for-loops nested into one another sort the vector, too:

for top  high(vector)1 downto low(vector) do
    for current  low(vector) to top do
        if vector[current] > vector[current+1] then
            exchange(vector, current, current+1)

Related pages[change | change source]