In this post I will use ScriptCraft to create static visualizations in Minecraft for a couple well-known sorting algorithms.
Sorting Algorithms
Sorting algorithms are a popular branch of algorithms. For young computer scientists sorting algorithms are the vehicle for learning important concepts in the field such as Big O notation and time-space tradeoffs. For older computer scientists, this family of algorithms are still interesting enough to devote time for research and analysis (e.g. Library Sort). And yet despite the ubiquity of these algorithms I doubt most of us have developed strong intuitions on how they work, or have simply forgotten–myself included.
Static Visualizations
A few years ago, Aldo Cortesi, a New Zealand coder, made a case for static over animated visualizations as the tool of choice for understanding the flow of sorting algorithms. His argument is that these animated visualizations are initially unclear and take longer to understand. We have trouble with these animations because humans estimate distances in space well, but are generally poor at estimating distances in time, so why when trying to teach potentially confusing material would we play to our weakness? Static visualizations play to our strength.
Below there are three sorting algorithm visualizations along with a few notes. Look at each picture from right to left to follow the flow of each algorithm. If you hadn’t already guessed from the pictures we are sorting colored wool and using Minecraft’s internal IDs for each block. A list of all block IDs can be found at MinecraftInfo.
Bubblesort
Bubblesort Meets Colored Wool
A simple sorting algorithm. If your list is small and your data mostly sorted, then there is certainly nothing wrong with this little algorithm.
Notice:
- When a line of wool is swapped with another the most it moves is by one line.
- Towards the end of the rectangle (towards the left) there is a stretch where no wool is swapped and yet the algorithm is still “sorting”.
Shell Sort
Shell Sort Meets Colored Wool
Discovered by Donald Shell in ’59. Compare the picture above with that of Bubblesort and you should notice:
- Swaps between rows can move wool more than one line (unlike poor old Bubblesort)!
- The visualization has a shorter width than that of Bubblesort. This is due to the fact that Shell Sort took fewer passes sorting the same data.
Quicksort
Quicksort Meets Colored Wool
Discovered by Tony Hoare in ’60. Quicksort is popular because it is usually very fast in practice.
Notice:
- There is a pattern where first wool swaps are made from farther away, but then are followed by swaps with closer lines of wool. This is because Quicksort takes a bigger uglier problem (like sorting a lot of wool) and divides into smaller similar problems (sorting just a little bit of wool). The smaller problems are easier to solve and can be recombined to create a solution for the original big ugly problem.
- The orange wool does not appear at the very top like in the previous sorts. (Don’t worry it’s there, but for some reason Minecraft doesn’t always show the blocks I render with ScriptCraft).
More Visualizations
After your done reading this post I sugget you visit Cortesi’s sortvis site to see more sorting algorithm visualizations. If you are interested in creating your own sorting algorithm visualizations in Minecraft you can find the JavaScript code I used as a Gist. You’ll need ScriptCraft installed which is a little painful, but once installed you can do plenty of other neat things like creating L-system fractals.
Suggestions
Is there a topic you would like to see covered here? I want to hear your input. Send me an email with any suggestions for future posts.
Dullahan Soft. 