The Sounds of Sorting

(This assignment is inspired by the work of Timo Bingmann and Casey Rule!)

In this assignment, we will build both a visualizer and audibilizer for the various sorting algorithms that we implemented during the week.

You can access the Github repo for this assignment here:

• psosera/the-sounds-of-sorting

Note that for this week’s labs/project, you’ll only turn in this repository!

Part 1: Sorting Algorithms

First, we will implement a number of sorting algorithms over generic arrays as discussed in class. The sorting algorithms you need to implement and subsequently instrument in the next part are:

1. Selection Sort
2. Insertion Sort
3. Bubble Sort
4. Merge Sort
5. Quick Sort

You can copy your implementations of these sorting algorithms from the sorts lab into Sorts.java as a starting point. Note that the signatures of these sorting algorithms have changed from the sorts lab. This is to account for the event logging that we will implement in the next step!

Part 2: Instrumenting Our Sorting Algorithms

In order to visualize and audibilize our sorting algorithms, we must instrument our sorting algorithms so that we can see how they mutate the input list at each step. There are various advanced techniques for doing this, e.g., callbacks or continuations. For this project, we will simply log the interesting operations that our sorting algorithms perform and store them in a list for playback later.

We’ll represent these possible sorting events as a collection of classes united by a common interface. This interface is SortEvent<T> which represents a sort event over a generic list of Ts. The SortEvent<T> interface possesses the following methods:

• void apply(T[] arr): applies this sort event to the given array.
• List<Integer> getAffectedIndices(): returns a list containing all the indices that this event affects.
• boolean isEmphasized(): return true if this event should be emphasized by the visualizer/audibilizer.

There are three kinds of events to implement:

• Compare Events that are logged whenever an algorithm compares two elements of the array. Compare events are not emphasized, and their affected indices are the indices of the elements being compared. Applying a compare event does nothing to an array.
• Swap Events that logged whenever an algorithm swaps elements of the array. Swap events are emphasized, and their affected indices are the indices of the elements being swapped. Applying a swap event swaps the recorded indices of the array.
• Copy Events that fire whenever an algorithm copies an element into an index of the array. Copy events are emphasized, and the affected index is the destination of the copy. Applying a copy event performs the copy of the recorded value into the array, overwriting the value

You should complete the definitions of the three classes, CompareEvent<T>, SwapEvent<T>, and CopyEvent<T> found in the events package by having them implement the SortEvent<T> interface and the behavior described above.

To instrument your sorting algorithms:

1. Implement the SortEvent<T> class hierarchy.
2. Augment your sorting algorithms in Sorts.java so that they create and return a list of SortEvent<T> objects that capture all the events that the given algorithm generates.

To test whether your event logging is correct, you should implement one last sorting algorithm found in Sorts.java:

• <T> void eventSort(T[] l, List<SortEvent<T>> events), : given an array of Ts and list of SortEvent<T> objects, apply those events to the list in-order.

The test suite for the project has been enhanced to take the events generated from your sorting algorithms and also run eventSort on a copy of the original array and ensure that the generated events also sort that copy.

The Remainder of the Program

With the engine of the program completed, you can now enjoy your sorting audibilizer/visualizer! For reference, here are the remainder of the files and their contents. We encourage you to read through the code to understand how a more complicated program like this is put together.

• Main.java: the entry point of the program.
• ArrayPanel.java: the portion of the GUI that renders the note indices to the screen.
• ControlPanel.java: the portion of the GUI that contains widgets to control the program.
• Scale.java: an object that encapsulates a musical scale represented by a collection of MIDI notes.
• NoteIndices.java: an object that encapsulates a collection of indices into a particular Scale object.