Bubble SortAn explorable explanation &
|
|
This work-in-progress is not public — please don't share. Also, there are lots of broken things and notes to myself scattered about.
Bubble SortAn explorable explanation &
|
|
Bubble sort is an algorithm that sorts collections of items — like numbers from smallest to largest, or words alphabetically. In this essay, we'll see how we can use bubble sort to put lists of numbers in order, which is a good introduction to algorithms. We'll represent lists of numbers as bar charts so it's easier to see what's going on. Our goal is simple:
Let's see how bubble sort does it.
At its core, bubble sort is just a few simple rules. Let's see how those rules work. We'll use little bar people because it's more fun!
And that's it! If you just follow those steps, you'll end up with a sorted list! Isn't that amazing? Let's try it out.
In this diagram, try using the rules described above to sort the list. Remember, jump if you're taller, and tag if you're shorter. You could even try to play this game in real life!
this isn't working yet, add table history of actions to connect to table representationIf you've sorted the list, you might try shuffling it and trying again. You can also try seeing what would happen if you followed different rules. For example, how could you sort the line from biggest to smallest instead?
Phew! Sorting is a lot of work! Let's get the computer to do bubble sort for us and show us what it did.
In the diagram below, hover over each row to animate the bar chart on the left.
You may have noticed that at the beginning of pass #3 the list was already sorted but the computer did another pass anyway. Why is that?
Unlike you or me, a computer can only check if a list is sorted by making sure that each number is bigger than the one before it — one at a time. This is what the computer does in the final pass of bubble sort because this is how it knows that the list is finally sorted and it can stop.
In the example above, it took three passes to sort a list of four numbers. But depending on the arrangement and values of the initial list, bubble sort can act differently.
In the diagram below, try changing the initial list to see how bubble sort reacts. [Drag to change the order of numbers] [click to edit] [new number button to append a number to the list (careful of +/add terminology)] [delete item button]
should I add a shuffle the list button down here? Don't exactly want to encourage totally random exploration.
Did you notice how bigger numbers tend to be pushed to the right early on and smaller numbers move to the left more slowly? The smaller numbers "bubbling up" to the left is why it's called bubble sort. Yeah, I don't really get it either. ¯\_(ツ)_/¯
Here's a puzzle: Can you rearrange the items below so that bubble sort will take the most number of steps to complete? There's a scoreboard to help you keep track of the number of steps for each configuration.
If you think you've figured out the puzzle, try making the list longer (probably should be an automatic command to scroll up and add an item, right?) and see if your solution still works.
If you solved the puzzle above, you've found what computers scientists call an algorithm's "worst case performance". This just means the most number of steps an algorithm can ever take to complete.
compare and contrast best case? average case? interleaved smallest and largest (5,1,4,2,3?)
In the fewest number of steps, bubble sort just does one pass, so the total number of steps is the total number of people in a row. [show]
In the largest number of steps, bubble sort forms a square.[show]
in fact, you can see how that square grows by a row and a column as its length grows [show]
For bubble sort, you may have noticed that when you've found the most number of steps for any list, the summary table makes a square of rows and columns: (label '5' or '6' on each side)
The number of rows and columns in this square depends on the initial list's length. A list of 5 items will make a 5x5 square, a worst-case 6-item list will make a 6x6 square, and so on.
Every time we make our list one number bigger, this square grows by another row and another column [[use darker yellow to highlight, show comparison(s), 5->6 (yellow)->7 (darker highlight)]].
To get to the total number of steps for the table, you can just count them, or you can do fancy counting and multiply the number of rows by the number of columns. For the worst case, the rows will be equal to the number of columns which is equal to the number of items in the list.
In this diagram Hover over the plot. Moving left to right changes the length of the unsorted list, and moving up and down under the blue line shows each step taken to sort the list. Hold the mouse button down to explore the selected sort.
add buttons for "next/previous step" and "next/previous starting set"
As you can see, this gets out of control really quickly! Algorithms are often judged by their worst case performance. Computer scientists want an algorithm that takes the fewest steps possible because on a computer this will be the fastest.
Because of For most purposes, bubble sort is not a practical algorithm to use. this growing square time means that bubble sort is not a practical algorithm. More practical algorithms might be quicksort, or mergesort. But I think there is something beautiful about merge sort, that with only two actions, jump and tag, and following those instructions blindly, you kind of magically end up with a sorted list.
There is a way of making bubble sort take fewer steps. You may have noticed when you do bubble sort that the largest item is always at the end after the first pass, the second-largest item is second from the end in the second pass, and so on. That means these items are already sorted.
If each step took one nanosecond to complete (about what a typical consumer processor can handle), we can figure out the lower bound for how long it will take.
Because the number of steps grows like crazy in the worst case, bubble sort is not a very practical algorithm. Even after optimizing, it still takes a whole bunch of steps to finish. There are other algorithms that people generally use for sorting instead, such as merge sort or quick sort. Their worst case looks more like this:
Even though bubble sort isn't the most practical algorithm, it's still useful and fun to understand!
add *bonk* arrow as callout to play below \/---\/
