Bubble sort is a simple comparison sorting algorithm where the list is repeatedly traversed through, swapping in-place any items that are in the wrong order.

As the list is traversed through n times, and each traversal is at maximum about n items long, bubble sort has O(n²) complexity (both average-case and worst-case).

The algorithm is named as such because large values "bubble" up rather fast early up in the algorithm.

Algorithm Edit

A loop is started that exits when the loop is sorted. Another loop iterates through the list. if the current item is out of order with the next item the items are swapped. If none of the items need swapping the algorithm can exit.

Pseudocode Edit

bubble_sort(list of t)
    temp as t
    swapped as boolean
    for i = list.count - 1 to 0 step -1
        swap = false
        for j = 0 to i - 1
            if list(j) > list(j + 1)
                temp = list(j) // swap
                list(j) = list(j + 1)
                list(j + 1) = temp
                swapped = true
        if not swap then


Traversal reduction
With the knowledge of what happens in bubble sort, we end up with the fact that for each traversal, the largest value will always end up at the end. With this knowledge, each traversal can be stripped off the values that are already sorted.
Pseudocode replacement: for j = 0 to list.count - 2for j = 0 to i - 1

Sort completion detection Edit

For each traversal, we know for a fact that when no swaps occured, the list is already sorted.
Pseudocode addition: We introduce a swapped boolean that detects when a swap is done.

Rabbits and turtlesEdit

Small values at the end of the list, the so-called turtles, tend to move rather slowly down the list. Cocktail sort, a variation of bubble sort, solves this problem. Comb sort compares elements with large gaps so turtles can be eliminated early on.

 See Also Edit

Sorting algorithms
Bubble sort - Insertion sort - Merge sort - Quicksort - Selection sort - Heap sort