Bubble Sort

Bubble Sort Process

Imagine, for simplicity, that you have a deck of numbered cards from 1-10 that are all face down and mixed up. You need to sort them, but are only allowed to have 2 cards facing up at a time.

What if we started by looking at the first 2 cards and swapping them if they are in the wrong order?

You might think that this would not help, as all the other cards are still in the wrong order. However, what if we then compare the second and third cards, and swap them if needed?

Are any patterns emerging?

If we continue this process until we reach the end of the list, we get the following result:

We notice that the largest element (10), has been pushed all the way to the back of the list while every other element has been shifted closer to its correct location. The larger elements are moving to the back, and the smaller elements are moving to the front. This is all great, but the list still isn't sorted.

What if we repeat this process from the beginning with this new list we've made? We then get the following result:

Now, the next largest element (9) has been pushed all the way to the end. The list appears to be sorting itself from the back forward, which is a good sign to continue. In fact, in this case, if we continue repeating this process, it will take 5 total iterations and then we get a completely sorted list! In general, you would keep repeating the process until you make 0 swaps in a passthrough. What we have discovered here is a sorting algorithm called Bubble Sort. It gets this name from the way that small values seem to 'bubble up' to the front of the list.

Bubble Sort Visualization

You can do a single passthrough of the list by pressing the Step button, undo a passthrough by pressing the Step Back button, or continue to step through using the Play button. Additionally, while it is running, you can press the Stop button or Skip button to pause or skip the animation. The slider controls the animation speed, and the bottom set of buttons are data presets, to see how the algorithm works on different data. While the animation is playing, colored circles will represent what values the algorithm is currently processing, and they will be red if a swap is not needed and green if one is needed.

Bubble Sort Time and Space Complexity

Bubble Sort is not the most efficient, having a time complexity of $O(n^2)$. This is because Bubble Sort averages $O(n)$ swaps per passthrough and $O(n)$ total passthroughs. Unlike some sorting algorithms like Selection Sort, Bubble Sort can become much quicker if the data is sorted or nearly sorted (try running with the 'In Order' preset). As for the space complexity, Bubble Sort has an average space complexity of $O(1)$.