Bubble Sort Atom Feed 1

In Brief This sorting algorithm performs multiple passes over a list, comparing consecutive elements. If the two elements are out of order, they are swapped. This continues until a pass shows all elements in order.... more
Performance Bound Quadratic
Implementation Difficulty * * * * *
 1 function bubble_sort(array)
2
3 do
4 swapped = False
5
6 for i = 0 len(array) - 2
7 if array[i] > array[i + 1]
8 swap(array[i], array[i+1]) // Swap the element positions
9 swapped = True
10
11 while swapped == True
12
13 return array

This sorting algorithm performs multiple passes over a list, comparing consecutive elements. If the two elements are out of order, they are swapped. This continues until a pass shows all elements in order.

It is named 'bubble sort' because smaller elements slowly 'bubble up' towards the top of the list.

This is one of easiest sorting algorithms to implement but also one of the slowest.

An Example

Say I have the following list I wish to sort:

[2 4 1 3]

The algorithm makes multiple passes over the list, comparing adjacent elements. Each pass will compare adjacent numbers, and if the left one is larger than the right one it will swap them. Below, bold indicates the numbers being examined.

Watch how the smaller numbers gradually bubble up.

The First Pass

[2 4 1 3] The first two numbers are in order, so nothing happens.

[2 4 1 3] → [2 1 4 3] The next pair is not in order, and so is flipped.

[2 1 4 3] → [2 1 3 4] Again, the two numbers are not in order. They are swapped.

The Second Pass

[2 1 3 4] → [1 2 3 4]

[1 2 3 4] (no change)

[1 2 3 4] (no change)

The Third Pass

[1 2 3 4] (no change)

[1 2 3 4] (no change)

[1 2 3 4] (no change)

Since nothing was changed on this pass, the list must be in order and the sort terminates.

Further Information

Wikipedia: Bubble Sort

Implementations
Simple implementation of the Bubble Sort algorithm in Javascript....
A simple implementation of the Bubble Sort algorithm....