Lab 12: The Sounds of Sorting (and Radix sort)

The Sounds of Sorting

This week in lab you're going to be building our own inferior version of the sorting visualizer that we saw in class.

We've provided with you two files in the sorting directory for our visualization/audibilization.

SortSounds.java

SortSounds is the top level class that coordinates the animations of our sorting algorithms. When it starts up, it creates an array of length N called toSort, and based on command line arguments, initiates one of 6 different sorts: quicksort, merge sort, selection sort, insertion sort, shell sort, and heap sort.

To run SortSounds, you can use the following syntax:

java sorting/SortSounds [-n <number>] [-s <sortName>] [-o <order>]

Where number is the number of elements that you are sorting, sortName is the name of the sort you want to see, and order is if you want an in-order, reversed, or randomized array. The default behavior if you don't include any of the options will be to run a visualization with a randomized array with 32 items for all the possible sorts. Valid sortNames are 'quick', 'merge', 'selection', 'insertion', 'shell', and 'heap'. Valid orders are 'inorder', 'reverse', and 'random'.

The chosen sorting algorithm is expected to make calls to the following three animation methods, providing us with the ability to see and hear what the algorithm is doing as it works:

static void drawRectangle(Color c, int i)
static void clearRectangle(int i)
static void play(int i)

As the docstrings for the methods say, drawRectangle will draw a rectangle of Color c, based on the item in the int array we are sorting at index i. For example, if toSort[7] == 9, then drawRectangle(7) will draw a rectangle at x-coordinate 7 with height 9. Similarly, clearRectangle will clear the rectangle based on the item at index i, completely removing it from the screen.

play will play a sound based on the int at index i. The tone ranges from 400Hz to 800Hz. You can change this by changing the LOWTONE and HIGHTONE fields in SortSounds, though I believe that anything higher than 1000Hz is unpleasant and anything below 200Hz cannot be heard with typical laptop speakers.

Let's start by running the following:

javac -g sorting/*.java
java sorting/SortSounds -s merge

You'll see the merge sort algorithm execute, displaying its state as it runs by calling the three animation methods provided. When it's done, you'll see that SortSounds finishes with a glorious rainbow flourish.

Now try running the following:

javac -g sorting/*.java
java sorting/SortSounds -s quick

You'll see that the data is drawn (as with merge sort), but then immediately gets overwritten by the rainbow flourish. The problem is that quicksort never reported back to the SortSounds method, so nothing was animated. Let's change this.

Sort.java

If you look inside Sort.java, you'll see implementations for quicksort, merge sort, selection sort, insertion sort, shell sort, and heap sort.

We can divide these sorts into two categories:

  1. Exchange based sorts: Quicksort, selection sort, insertion sort, shell sort, and heap sort
  2. Mergesort

Each of our exchange based sorts make use of a helper method called exch that exchanges two elements. We recommend that you modify the exch method so that it makes interesting calls to drawRectangle, clearRectangle, and play. For inspiration, you might look at the drawRectangle, clearRectangle, and play calls that are made by the merge sort algorithm.

Other improvements you might consider:

Note from Daniel: I really hope you had fun doing this part of the lab. It was really fun developing it. Exercise your creative freedom while doing this! If you don't like my default colors or the rainbow flourish, feel free to change it. Your prefered color scheme is probably different from mine. Make the simulation your own!

Radix Sort

In this part of lab you'll write an implementation of radix sort for integers. We've provided you with method declarations in radix/Sorts.java. For this implementation of radix sort, you'll be sorting positive integers with a radix of 16, i.e. there will be 16 different 'characters' in our 'alphabet'.

What does this mean? Let's consider the decimal number 9731. If R=10 (i.e. our radix is 10), then we'd say that our alphabet consists of [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], and thus our number is a sequence of 4 digits in this alphabet, namely 9, 7, 3, and 1.

What happens if R=16, i.e. What is our alphabet, and how would we represent 9731 in that alphabet? The most natural approach is to say that our alphabet consists of all possible combinations of 4 bits [0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, and 1111]. To represent 9731, we'd represent it as a sequence of digits from this alphabet of 4 bit chunks. Since 9731 is 00000000000000000010011000000011, in terms of our basic alphabet, we have:

0000 0000 0000 0000 0010 0110 0000 0011

As we learned earlier in the semester, Java represents integers in binary. This makes it possible for us to implement radix sort using bit masking (the & operator) and shifting (the << and >> operators) in order to get specific digits.

For this part of the lab, there are two methods that you have to implement:

public static int[] countingSort(int[] keys, int whichDigit)

countingSort() is the procedure that we described in lecture 32, sorting only on the whichDigith digit of each key. Since we have 32 bit integers, and each alphabet character is 4-bits, then each key in the int[] array consists of 8 digits (i.e. whichDigit should only be a number between 0 and 7). If whichDigit is 0, you should use the rightmost digit, and if it is 7, you should use the leftmost digit. Note that you going to return an array. Do NOT change the actual keys array.

public static int[] radixSort(int[] keys)

radixSort() will fully implement the radix sort algorithm. Given the countingSort procedure above, radixSort will be very easy to write.

Extra for experts: Compare the runtime of your radix sort compared to Arrays.sort. Which is faster for short arrays? Long arrays?

References