Bubble sort
this wiki
Bubble sort is a simple comparison sorting algorithm where the list is repeatedly traversed through, swapping inplace 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 averagecase and worstcase).
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  2
→for 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 socalled 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
