There are some news items from the past year that deserve a second chance. Here we have one such - sorting algorithms are fundamental to computer science and writing one of your own will teach you a lot. There are many different approaches to sorting - but one thing they share in common is that they are better understood when visualized.

(2019-04-28)

I Programmer is always happy to discover art, in its many forms, being used algorithmically and, ever since an early news item, Sorting Algorithms as dances, became an instant success,  we have a particular fondness for sorting algorithms. 

If you missed the folk dance videos by students for Sapientia University, Romania and uploaded to You Tube by AlgoRythmics, then we have the complete series here.

The latest visualization of sorting algorithms is the Sortraits project from William Tracy. Open-sourced under an MIT licence this is a project to create portraits of a variety of sorting algorithms, including selection sort, insertion sort, bubble sort and Quicksort. The results are very striking. Here are some of sortraits of that I'd be happy to display as works of art using Even-odd sort, Cocktail sort and Gnome sort - all sorts that are new to me:

Explaining how he created his his Sortraits Tracy writes:

For each portrait, I started with one line of pixels, where each pixel is assigned a number. Larger numbers make brighter pixels, and smaller numbers make darker pixels. Then, I run the algorithm. Each time the algorithm moves items around in the list, I add another row to the picture showing the current state of the list. This continues until the list is entirely ordered, with black at the left, and white at the right.

I used several types of starting lists: I tried lists shuffled in random order. I tried lists set up in reverse order. I tried starting with an ordered list, and interleaving pixels from the two halves. I tried swapping the two halves. I tried swapping the first and last thirds. I even tried running the algorithms on an already sorted list--several algorithms insist on completely rearranging the list and then putting it back in order!

I also tried difference visualizations as well: For each pixel, I compared the current value of the pixel, and the value that it should have when the list is properly ordered. If they are the same, I color the pixel black. The more different they are, the brighter the pixel becomes. Areas that need work will light up, and areas that are already sorted go dark.

The Sortraits gallery contains Tracy's selection of the most interesting pictures some of which are tinted several with different colors that "felt right". This one, titled Kaliedoscope Pinwheel uses Even-odd sort run against a shuffled list in which values have been assinged to rainbow hues, rather than to brighter and darker shades. 

According to the Sortrait project's readme on GitLab, where you can access the code for the project and modify or add to it should you so wish states:

This codebase is an unholy union of Haskell code and Bash shell scripts. The management does not assume any responsibility for your sanity should you continue further.

The Todo list has the following outstanding items:

Maybe implement smooth sort. Probably not gravity sort. Not sure about patience sort, Dutch-flag sort, American-flag sort, and block sort.

Experiment with partitioning values in output as unmodified, modified, and final values. Each partition could be color-coded differently. 

Personally I'm happy just to look at the output - Haskell and Bash!:

Whereas these portraits are a static interpretation of different sorts, animations are a good way to show sorting in action, see for example Amazing Animated Sorting Demo. The Sortraits Gallery includes a link to animations that were the original inspiration for the project: Sorting Algorithms Visualized, noting:

There's lots of big animations on this page, so don't follow that link if you're on a slow connection!

Here is the YouTube video that inspired the difference visualizations used in Sortraits:

Another source of inspration from the project came from Timo Bingmann's the Sound of Sorting, described by its creator as:

the Visualization and "audibilization" of 15 Sorting Algorithms in 6 Minutes.

The video sorts random shuffles of integers, with both speed and the number of items adapted to each algorithm's complexity:

Bingmann provided the code he used for the Sound of Sorting demo on GitHub  and it has been extensively forked. This video, based on the code found here is the sound of sorting a descending order list with radix sort that its author thought sounded pretty cool so shared it:

More Information

Sortraits: Portraits of Sorting Algorithms (Gallery)

Sortraits Project on GitLab

Sorting Algorithms Visualized: Album on Imgur

Sound of Sorting on GitHub

Sound of Sorting Source Package 

Related Articles

Sorting Algorithms As Dances

Amazing Animated Sorting Demo

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info