When I was first learning about data structures and algorithms I found it hard to visualize how the algorithms manipulated the data. I would draw out the data after each iteration, but this would take a while and became very tedious. Recently, while helping a friend learn about sorting algorithms, I found myself drawing out these pictures by hand again and figured it might be a good time to try and create a few short programs that visually demonstrate some sorting and searching algorithms. This post has a short description of each program, but doesn’t contains a detailed discussion of each algorithm. I’ll continually update this post as I add new ones, with the code available on GitHub:
Sorting
Bubble Sort
Bubble sort works by “bubbling up” a value every iteration. In the example above, the numbers in red are the current values being compared; if they need be swapped one color is changed to yellow and the other to blue so the swap can be seen more easily; a value is changed to green once it “bubbles” to its final position.
Selection Sort
Selection sort is an in place sort that divides a list into 2 parts: a sorted sublist on the left, which is built from the unsorted sublist. In this example the unsorted sublist is shown in white and the sorted sublist in green, and it’s being sorted in ascending order. First the minimum value of the unsorted sublist is found and highlighted in red, then swapped to the end of the sorted sublist.
Searching
Linear Search
Linear search checks each item in an array from start to end. This example shows which item is currently being checked in yellow, changes to red when it doesn’t match the item being searched for, and green when the correct item is found.
Binary Search
Binary search is a method for searching a sorted dataset by continually dividing the data set in half. This program highlights the lower and upper bounds of the search with blue and the middle value being tested in yellow. If the yellow value isn’t the one being looked for then either the upper or lower bound is adjusted, and the invalid values are marked in red. Once the correct value is found it’s marked in green.