Fandom

Programmer's Wiki

Bubble sort

410pages on
this wiki
Add New Page
Talk2 Share

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
    return

OptimizationsEdit

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.

ExampleEdit

Sorting the list: 4, 5, 3, 7, 6, 1, 2.

4537612
  • pass 1
4537612
4357612
4357612
4356712
4356172
4356127
  • pass? 2
3456127
3456127
3456127
3451627
3451267
  • pass? 3
3451267
3451267
3415267
3412567
  • pass? 4
3412567
3142567
3124567
  • pass? 5
1324567
1234567
  • pass? 6
1234567

Examples Edit

External links Edit

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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.