Sorting Visualized
Sort it out!
It’s the most fundamental problem in computer science, sorting, yet it remains elusive. With so many sorting algorithms out there, it’s easy to get overwhelmed with them. There are two parts to the problem, the visual representation of state of array during sorting and the sorting algorithm itself. We often look at each part in isolation, what if we have a visual representation of array along with some details about inner workings of the algorithm?
That’s what I have tried to depict in this post, by creating a fancy print method in Java, and invoking it during various stages of sorting. Turns out you could print in different font colors, background colors using vanilla System.out.print() statement, add some delay and clear terminal after each print statement, voila, you have got animated output, sort of.
Read on to find out how I used this fancy print method to depict inner working of most popular N squared sorting algorithms, Bubble sort, Insertion sort and Selection sort
N Squared sorting algorithms visualized
Below you can see animated gifs depicting inner workings of three N squared sorting algorithms, Bubble sort, Insertion sort and Selection sort. On top of each gif, there is a legend explaining how to read different font colors and background colors in the the output.
Since all the algorithms are N squared, they all have two loops, inner and an outer loop. Outer loop is represented in green font color while inner loop is depicted in red font color with underline. You would notice that inner loop size is changing with each iteration of outer loop. Inner loop usually represents data being worked upon, while outer loop is usually sorted, but that’s not true always.
Besides loops, values being compared are depicted by yellow background color, and values being updated are shown by blue background color. Each algorithm also has a specific key, that is tracks, it’s represented in purple font color. Keys are usually updated with each iteration of outer loop.
Equipped with this knowledge, we are now ready to take a look at the gifs.
Bubble Sort
The idea here is to compare adjacent elements and swap them if second element is smaller. With each iteration the next largest element moves to the right side of array in its sorted position.
In the example above, see how 9 reaches its sorted position at the end of array in first iteration, then 8 and so on, larger numbers move to end of array.
Notice the inner loop, with each iteration of outer loop, it shrinks, skipping rightmost element, since it is already in sorted position.
Notice the tracked key here, it’s the upper bound for inner loop. With each iteration of outer loop, the end index for inner loop is reduced, since the subsequent numbers have reached their sorted position, this is the optimized variation of bubble sort.
In Bubble sort large numbers reach their sorted position faster than small numbers, they bubble slowly toward the front half of array.
Notice how array starts to get sorted from right side to left.
This is a stop the world sorting algorithm, as in it is looking over entire array to sort it, so array cannot be modified, while Bubble sort is going on.
Insertion Sort
The idea here is to keep left side of array sorted. Start with size 2 sub-array of left-most elements, and with each iteration, add one element from right side, place it in sorted position in left side.
In the example above, see how left sub-array of 8 and 2 is sorted in first iteration, then 4 is added in left sub-array in sorted position (2, 4, 8), and so on.
Notice the inner loop, with each iteration of outer loop, it expands, to include next right element, while keeping left sub array sorted.
Notice the tracked key here, that’s the next right element, that needs to be placed in left sub array. The key is compared with elements in left sub array, starting from tail end, if the key is smaller, elements in subarray are shifted right to make space for key.
Insertion sort is concerned with keeping current left sub array sorted, it doesn’t run into issues with larger or smaller numbers getting sorted faster.
Notice how array starts to get sorted from left side to right.
This is an online sorting algorithm, as in it’s only looking over current left sub-array to sort it, so new numbers can be added in tail end while sorting.
Selection Sort
The idea here to find next smallest element with each iteration, and put it in the beginning of array in its sorted position. The element at sorted position is swapped with smallest element found.
In the example above, see how 2 reached the beginning of array in first iteration, followed by 3 and so on, smaller numbers move to start of the array.
Notice the inner loop, with each iteration of outer loop, it shirks, skipping the leftmost element, since it is already in sorted position.
Notice the tracked key here, it’s ith smallest element for ith iteration of outer loop. Once the ith smallest element is found, its swapped with the element at ith position. Now the inner loop starts with i+1 position to find the next smallest number.
Selection sort tries to address the issue with smaller numbers moving slowly to front by finding smallest numbers and moving them to front.
Notice how array starts to get sorted from left side to right.
This is a stop the world sorting algorithm, as in it is looking over entire array to sort it, so array cannot be modified, while Selection sort is going on.
N squared sorting algorithms with reverse sorted input
All of the N squared sorting algorithms discussed here, struggle with reverse sorted input. They have to work very hard, with lot of comparisons and swaps. But it does make it a good use case for illustration purposes. That’s what the next snapshots are about, output with reverse sorted data. The only difference is that it’s not an animated output. For this section I disabled the clearing of console after each print statement, and printed each statement in new line to generate a complete log of array sorting steps. The rest of the output formatting options, like font colors and background colors are still same as before. So let’s take a look at the snapshots for reverse sorted input.
Bubble sort
Notice how 90 reaches the end of array after first iteration of outer loop, inside the inner loop, there is a swap in almost every iteration. And the process is repeated with 80 and so on, until all large numbers move to back and smaller one move slowly to front.
It is evident that the algorithm is working very hard to sort the data.
Insertion Sort
This snapshot depicts very well the inner workings of insertion sort. Notice how size of left subarray increases with each iteration of outer loop, first 80, 90 are sorted, then 60 is added to mix, so 80 and 90 are shifted to get left sorted sub array of 60, 80 and 90.
See the last iteration, when 10, the smallest number is encountered, the entire left subarray is shifted by one position to insert 10 in the beginning, that’s lot of work.
Selection Sort
See how 10 reaches the beginning of array after first iteration of outer loop, followed by 30 and so on. You can also see the stark contrast with Bubble sort output, with data being sorted on opposite ends and inner loops working on opposite ends.
This also shows the contrast with Insertion sort, although both of these algorithms, start to sort the array from left, they way the do it is completely different. Notice 10 is the first element being sorted here, while it’s the last to be sorted in Insertion sort.
N squared sorting algorithms with sorted input
The following section contains snapshots of these algorithms for sorted input. The formatting is same as above. Some algorithms do better in handling sorted input than other, keep reading to find out more.
Bubble Sort
By default, Bubble sort is not very efficient in handling sorted data, the output above is of optimized version of Bubble sort, with a boolean flag, that is set, when any swaps happen during iteration of outer loop. If no swaps happen, that means data is sorted. This allows the optimized variant of Bubble sort to detect in constant time that data is sorted.
Insertion Sort
Insertion sort usually works well with sorted or partially sorted data. As with every iteration of outer loop, the left sub array is kept sorted, all that needs to be checked is, if the next element is smaller than last element of left sub array, if it is not, that element is already in sorted position. Which is the case with sorted input, so even Insertion sort is able to detect in constant time that data is sorted.
Selection Sort
Its evident that Selection sort is working hard to sort the sorted data, since its comparing with each element to make sure current element is the next smallest element. It should be possible to have optimization here like Bubble sort, to detect early on, that input is already sorted. But the current variant does not have it.