Bubble Sort is a naive sorting implementation.
We might thing that to sort an array, we could just run through it element by element and, when a subsequent element is less than the previous element, flip the two values.
Set a flag for
swapped. Each time we flip two values, set the flag to true. After we iterate through the array, if the flag is true, we recursively call the function again & set the value to false.
When we are able to run through the entire array without flipping, we return the sorted array.
This is not an efficient algorithm. Also, Obama said not to use it.
Consider the worst-case scenario of a completely unsorted array:
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1].
It will take 10 loops to sort the array. Also note a subtle bug in the results below.
Can you figure out why
0 2 11 3 4 sorts to
0,11,2,3,4? Here’s the run-down.