In the first article I published related to sorting, we explored bubble sort while learning the basics of Sonic Pi. In this week’s post, we’ll dive deeper into our audio representation experiment and explore two more common sorting algorithms: selection sort and insertion sort.

You can find the code for all the tutorials in this series on Github.

Specifically, we’ll explore these algorithms according to the observation made by Professor Graham Hutton in the video below.

First, I’d like to encourage you to read the tutorial on bubble sort, especially if you don’t have any experience using Sonic Pi, and come back to this article after.

Theory Behind Selection and Insertion Sort

Both selection and insertion sort have a time complexity of O(n2), which is the same as bubble sort.

But wait a second… Didn’t I say in the first post on sorting that bubble sort was the least efficient sorting algorithm? Why are selection and insertion sort considered more efficient than bubble sort if they have the same time complexity?

Wikipedia gives us a very clear explanation:

Among quadratic sorting algorithms (sorting algorithms with a simple average-case of Θ(n2)), selection sort almost always outperforms bubble sort and gnome sort. Insertion sort is very similar in that after the kth iteration, the first k elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the k + 1st element, while selection sort must scan all remaining elements to find the k + 1st element.
Simple calculation shows that insertion sort will therefore usually perform about half as many comparisons as selection sort, although it can perform just as many or far fewer depending on the order the array was in prior to sorting. It can be seen as an advantage for some real-time applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably. However, this is more often an advantage for insertion sort in that it runs much more efficiently if the array is already sorted or "close to sorted."

What we can understand from this is that the efficiency of these algorithms comes from the number of comparisons made, not necessarily from optimizing the number of iterations it takes to sort the list.

Wikipedia also informs us that usually, insertion sort needs even less comparisons than selection sort and therefore outperforms selection sort in most cases. This is something we’ll definitely want to monitor in our sound experiment.

Selection Sort

This algorithm goes through each element of the array and saves the value of the current element and it’s position as minimum value and minimum index. It then loops over all the remaining elements of the array and compares them to the current element. If it finds an element smaller then the one saved as minimum, it replaces the minimum value and the minimum index by the element it found and it’s index.

Once the loop is completed, it checks whether the current minimum’s index is different than the index of the current element. If it is, it swaps the value of the current element with the value located at the minimum index.

Here is a pseudocode representation of selection sort:

loop over each element in array
    minimum = current element
    minimum index = index of current element
    
    loop over each element in the rest of the array
        if element is smaller than minimum
            minimum = element
            minimum index = index of element
            
if minimum index not equal to index of the current element in whole array
    swap values at current index and minimum index

Insertion Sort

This algorithm is extremely similar to selection sort. The main difference with the previous algorithm is the way it defines the subarrays.

Insertion sort loops over the whole array and saves each current element as a key. It then looks at the elements in previous positions in the array and loops over them. If these elements are bigger then the current key, their value is overwritten with the value of the element right next to it.

Once it finds a place where the value of the element is smaller than the key, it swaps the value of the element that is right next to it with the value of the current key, thus “inserting” the value at the appropriate place in the array.

Here is a pseudocode representation of insertion sort:

loop over the whole array
    key = current element
    loop over array from first element while key is smaller then element
            element = array[index of element + 1]

    array[index of element + 1] = key

“Insertion and selection sort are the same if you look at them correctly.”

In this video, Professor Graham explains that these two algorithms are actually the same if you paint a correct picture of them. His observation is that both these algorithms have a similar mechanism but one of them “selects” the correct value according to columns and the other “inserts” the value at the correct position according to rows.

I thought this was quite an interesting observation and the picture he demonstrated in the video is so clear and straight forward that I wondered if it would be possible to demonstrate that same observation through sounds.

So let’s get started!

Digging Deeply Into Both Sorting Algorithms

Extracting Information From The Algorithms

Let’s start by transferring those concepts into Ruby code inside SonicPi and printing the results:

Now is the time to decide what are the elements that are interesting for us to track in the execution of the algorithms. These are the elements I settled for:

total number of swaps for each algorithm
each subarray we are looking at
number of overwrites or replacements inside each subarray iteration
the time of execution (for comparison between algorithms)

Ultimately, we also want to give an auditive sense of wether we are sorting according to columns (selection sort) or rows (insertion sort).

Interesting fact:
In order to really wrap my head around how each algorithm works, it was important for me to log a lot of information during the execution, especially to see what happens inside the loop of the subarrays. To do that inside Sonic Pi, I had to “slow down” the execution by using Sonic Pi’s sleep function. Otherwise, the program executes too quickly and the print statements don’t appear in Sonic Pi ‘s console.
Likewise, in order to properly benchmark the time of execution of each algorithm, I suggest running the code from your terminal first before transferring the code into Sonic Pi.

Here is the code and a picture of what the printed data looks like inside Sonic Pi for both algorithms:

It’s interesting to note that, in our case, it seems like selection sort outperforms insertion sort in the amount of total swaps and comparisons it needs to make in order to sort the array.

Mapping Data To Frequencies and Audio Parameters

Great! We are now ready to start mapping all this data to sounds and make an audio representation of both algorithms that highlight their similarities as well as their differences.

Start Tracking Data With Sounds Through Sonic Pi

To create our unsorted array of notes, I chose to use the built-in hirajoshi scale. The following code creates an unsorted array of unique values of length 16.

Creating an unsorted array using the hirajoshi scale built in Sonic Pi.

Back to our sorting functions, let’s start by defining a reasonable speed for our audio representation to run:

use_bpm 80

Then, the first thing we need to do for both functions is make sure that we can hear the array at least once unsorted and once when sorted. The ruby each method allows us to do just that.

arr.each {|n| play n, release: 0.3; sleep 0.25}

We also need to make sure we create a copy of our unsorted array so that we’ll be able to loop function calls in our final piece (assuming we did a good job and our audio representation is nice enough that we’ll want to hear the functions run more than once!).

Next, in both functions, it would be nice to have a bass drum mark the start of a new iteration of the outer for loop.

# SELECTION sort
def selection_sort array
  arr = array.dup
  r = arr.length - 1
  swaps = 0
  
  # Play unsorted array once
  arr.each {|n| play n, release: 0.3; sleep 0.25}
  
  # Loop over the entire array once
  for i in 0..r
    # Current element is saved as minimum base value
    # Index of smallest value found saved with default value of current index
    min = arr[i]
    min_idx = i
    
    # Mark when we enter the loop
    in_thread do
      sample :bd_tek
    end
 ...
 
 # INSERTION Sort
def insertion_sort array
  arr = array.dup
  r = arr.length - 1
  swaps = 0
  
  # Play unsorted array once
  arr.each {|n| play n, release: 0.3; sleep 0.25}
  
  # Loop over the array
  for i in 1..r
    # Mark when we enter the loop
    sample :bd_tek
 ...

If you understand how threads work in Sonic Pi, the reason why I used in_thread for the bass drum in selection sort but not in insertion sort should become clear when we walk through the next steps.

Now, let’s take each algorithm separately and map some more data.

For selection sort, I wanted to try and give the auditive impression that each subarray is a column of data. The effect I tried to get is a cascade of notes that end by the right value falling in place, like we saw in the picture drawn by Professor Graham.

Once the correct value is found, we will play that value, along with the one it’s been swapped with. We can use different synths to play each values so that we can clearly differentiate between the sorted element and the one it swapped positions with.

While this is happening, we also want to indicate how many times the algorithm needed to replace a value when iterating over the subarray. For that, I chose to use a short cymbal sound playing n times, n being the number of replacements we counted for that iteration. I also chose to use a soft snare drum sound to play in the case that no replacements were needed.

  ...
    # loop over each subarray
    replacements = 0
    for j in (i + 1)..r 
      # if current element of subarray is smaller then min, 
      # replace min value and save current index
      if arr[j] < min
        min = arr[j]
        min_idx = j
        replacements += 1
      end
    end
    
    in_thread do
      replacements.times do
        sample :drum_cymbal_closed, rate: 2
        sleep 0.125
      end
    end
    
    if min_idx != i
      arr[i], arr[min_idx] = arr[min_idx], arr[i]
      # Play the note that was swapped with arr[i]      
      use_synth :pretty_bell
      play arr[min_idx] 
    else
      # Marks that no swap was needed
      sample :drum_snare_soft
    end
    
    # Play the selected note
    use_synth :tb303
    play arr[i], cutoff: 50, sustain: 0.5, decay: 0.3, release: 0.2
    sleep 1

For insertion sort, the approach is slightly different. In this function, I want to hear the insertion of a note. Meaning, I want to iterate through each row (subarray) and hear the note that has been inserted in the right place when we arrive to it in the iteration. As previously for selection sort, we want to hear how many times a value needed to be overwritten in order for the key to be inserted in the right position.

In case the key is already at the appropriate position and no overwrites were needed, we will mark that event using the same snare drum sound as we used in selection sort.

    ...
    overwrites = 0
    while j >= 0 and arr[j] > key
      arr[j + 1] = arr[j]
      j -= 1
      overwrites += 1
    end
    
    if arr[j+1] != key
      arr[j+1] = key
    else
      in_thread do
        # Marks that key was already at the right position
        sample :drum_snare_soft 
      end
    end
    
    # Indicates how many times we needed to overwrite values in orer to insert the key
    # at the right place in the array
    in_thread do
      overwrites.times do
        sample :drum_cymbal_closed, rate: 2
        sleep 0.125
      end
    end
    
    sub = arr[0..i]
    sub.each { |n|
      # If the note we are playing is the current key, use a different synth
      n === key ?
      (inserted = true; use_synth :tb303) :
      (inserted = false; use_synth :pretty_bell)
      # The difference in the parameters comes from the fact that :tb303 has a sustained sound
      # compared to :pretty_bell which is a percusive synth
      inserted ?
      (play n, cutoff: 50, sustain: 0.5, decay: 0.3, release: 0.5, amp: 0.4) :
      (play n, release: 0.3)
      sleep 0.25
    }
    sleep 0.5
  end
  ...

We finish our program by calling and logging the results of both functions. Here is what your code should look like until now:

Now if you run this code, you should hear your first audio representation of selection and insertion sort!

Taking It To The Next Level And Turning The Audio Representation Into A Music Piece

Again, like in the bubble sort tutorial, the first version of our program is not necessarily the most pleasant to listen to. Let’s do some adjustments to our code to create a better audio experience 😎.

Adding A Bit Of “Vibe”

First, instead of just calling our functions, let’s wrap these calls inside a live_loop so that we can have the code running more than once. Then, let’s create another live_loop that will play a drone and give some bass to the whole piece. Finally, let’s wrap both of these inside a :reverb effect (I chose to put a lot of reverb because, well, I just love it).

with_fx :reverb, room: 0.95 do
  # This provides a drone for ambiance
  live_loop :trembling_bass do
    use_synth :dsaw
    with_fx :slicer, phase: 0.125, smooth: 0.125 do
      play :g2, cutoff: rrand(60, 70), sustain: 4, decay: 1, release: 3, attack: 1, amp: 2.5
      sleep 8
    end
  end
  
  # This loops the calls to the sorting functions
  live_loop :sorting do
    selection = selection_sort unsorted_arr
    puts selection
    
    insertion = insertion_sort unsorted_arr
    puts insertion
  end
end

This, to my taste, already sounds much better.

Next, let’s adjust the amount of sleep time the program executes before starting a new iteration. To make the audio easier to follow but still dynamic, I decided to fit every iteration inside two beats. This means that I need to subtract whatever time it took for hearing the subarray from 2.0 to have the correct value for the sleep function.

sleep 2.0 - (sub.length * 0.125)

Next, a few minor adjustments.

I decided to keep the same synth (:tb303) for playing both the sorted value and the one it swapped positions with but give each one a different cutoff and amplitude so that it’s still possible to differentiate them.

To play the swapped value in insertion sort, I had to modify my code by adding a new variable and an if statement. In this function, I also chose to add a sleep statement before playing the cymbals marking the overwrites to space out a little bit the various audio events.

Last detail, I decided to keep the :drum_snare_soft sound in selection sort but use a :drum_splash_sound in insertion sort and have both these sounds play in reverse to make them sound more interesting.

    # INSERTION SORT
    ...
    note_swapped = false
    if arr[j+1] != key
      note_swapped = arr[j+1]
      arr[j+1] = key
      swaps += 1
    else
      # Marks that key was already at the right position
      sample :drum_splash_soft, rate: -1
    end
    
    in_thread do
      sleep 1
      overwrites.times do
        sample :drum_cymbal_closed, rate: 2, amp: 1.3
        sleep 0.125
      end
    end
   ...
    
    sub.each { |n|
      n === key ?
      (inserted = true; use_synth :tb303) :
      (inserted = false; use_synth :pretty_bell)
      
      if inserted
        play n, cutoff: 70, release: 0.3, amp: 0.5
        # If there was a swap play the swapped value
        if note_swapped
          play note_swapped, cutoff: 60, release: 0.3, amp: 0.3
        end
      end
    ...

Now, you might’ve noticed that there is one piece of data we are monitoring that I didn’t yet map to audio in the code: the total amount of swaps. I chose to represent that information inside the sorted function.

Creating A Custom Sorted Function

As we previously did in the bubble sort tutorial, instead of just playing the sorted array once at the end of each function, let’s create a sorted function that will run once we have successfully sorted the list.

Like I mentioned, we are also going to use this function to map the last piece of data we didn’t do anything with yet. I chose to do that by using the :elec_blip2 sample and passing an extra argument to the sorted function. This function now takes an array as argument and a number representing the total amount of swaps.

Here is my sorted function but feel free to come up with your own!

def sorted array, swaps
  in_thread do
    4.times do
      # Marks how many swaps the algorithm performed
      # Repeats on each iteration of the sorted array
      swaps.times do
        sample :elec_blip, amp: rrand(1.5, 2.0), pan: rrand(-1, 1)
        sleep 3.0 / swaps
      end
      sleep 1
    end
  end
  
  in_thread do
    16.times do
      in_thread do
        sample :bd_tek, amp: 3
        sleep 0.5
        sample :drum_snare_hard
        sleep 0.5
      end
      in_thread do
        4.times do
          sample :drum_cymbal_closed, rate: 2
          sleep 0.25
        end
      end
      
      8.times do
        sample :drum_cymbal_pedal, rate: 3 if one_in(3)
        sleep 0.125
      end
    end
  end

With that, our audio representation is complete! Here is the final code:

Here’s an instagram post where I show how it should sound like if you followed exactly all the steps described above (don’t be shy to follow me on Instagram or drop me a comment!):

Conclusion

I had a lot of fun working on this article and it made me realize how many details I was overlooking when I first started to learn about computer science and these basic algorithms. This research allowed me to fill in quite a few gasps in my knowledge that I didn’t even know were there.

I’ll be posting a new video on my YouTube channel soon where I take these concepts and play around with them as I did for bubble sort. You can subscribe to my channel if you’d like to be notified when the video is out!

Next in this series, we’ll break away from sorting and examine recursion as a preparation to look at more advanced “divide and conquer” sorting algorithms: quick sort and merge sort.

If you enjoyed this post, don’t forget to press Like and share it! 🏆

Did you come up with creative ways to play around with selection and insertion sort? I’d love to hear it! Send me a message or post a link to your creation in the comment section below! ⬇️

Thank you for reading and happy coding! ❤️

Curious to hear how your code sounds like?

Programming is not only useful to build applications, it’s also a powerful means of expression. When I started programming, I never thought I would one day merge both my passion for music and my passion for technology together.

Tell Me More

Understanding Selection And Insertion Sort By Creating Audio Representations With Ruby And Sonic Pi