How To Create An Audio Representation Of Bubble Sort With Ruby And Sonic Pi

 
bubble-sort-sonic-pi-ruby.jpg
 

The first type of algorithms that we generally encounter when starting to learn computer science are sorting algorithms. These types of algorithms are great because they solve a problem that is easy to understand (we have unsorted data and we want it to be sorted) and there are many different sorting algorithms which allow us to also learn about time and space complexity and efficiency by comparing each sorting method.

This is the first tutorial in a series of 3. By the end of this series, we will have explored in depth 5 of the most commonly used sorting algorithms: bubble sort, insertion sort, selection sort, merge sort and quicksort.

Setup

The first algorithm we will explore is bubble sort. Because this algorithm is so simple, we will also use it to get familiar with the tool we’ll use for building our audio representation, which is Sonic Pi.

I encourage you to code everything inside Sonic Pi, even before we start dealing with sounds.

If you don’t have Sonic Pi installed, you can install it here, it’s free and open source.

A Picture Is Worth A Thousand Words

To help us grasp programmatic concepts, it’s sometimes easier to visualize it as a picture or a diagram. When it comes to sorting algorithms, a popular visualization is the video below which accompanies this article:

 
 

You’ll probably agree with me that this kind of audio representation is not the most pleasant to listen to but it does help to see what the algorithm is doing step-by-step.

We are going to try and build something more pleasant to listen to and map data to audio parameters so that the sounds we hear also gives us information on what the algorithm is doing under the hood.

Let’s get to it!

Understanding Bubble Sort

The idea behind bubble sort is very simple.

You go through an unsorted list of elements and compare each element with the one directly next in the list. If that element is smaller than the current element, swap them.

Let’s take the problem apart and see exactly what this means programmatically.

For the purpose of this tutorial, we will assume that we are dealing with an unsorted array of integers of size N where N > 1.

  • Set a boolean variable which keeps track of whether or not a swap has occurred

  • While the array is not sorted, loop through each element of the array until N - 2 (we don’t need to look at the very last element because we are comparing each element to the one on its right).

  • If the element at index i is greater than element at index i + 1, make a swap and set the boolean variable to true

  • At the end of the iteration, check whether the list is sorted (boolean is still false). If yes, break out of the loop and return the sorted array, otherwise, set the boolean to false before starting a new iteration

An algorithm is basically a step-by-step guide of actions to perform to attain a desired result. Bubble sort has a time complexity of O(n2) and it’s the least efficient algorithm we will look at.

Here’s a pseudocode representation of bubble sort:

swapped = false

while true
  loop from i = 0 to (length of array - 2)
    if array[i] > array[i+1]
        array[i], array[i+1] = array[i+1], array[i]
        swapped = true
  if swapped
    break
   else
    swapped = false

Transferring that into Ruby code inside SonicPi and printing the results:

Bubble sort implementation in Ruby

 

Extracting Information From The Algorithm

First, we need to decide what kind of information is interesting for us to track. Here are the elements that I chose to keep track of:

  • total number of swaps

  • number of swaps for each iteration

  • number of iterations done to complete the sorting process

  • the state of the array after each iteration

  • time of execution (this will be relevant in future tutorials for comparing the execution time of the different sorting algorithms)

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

Keeping track of what the algorithm is doing and outputting the information in SonicPi’s built-in console.

 
 

Mapping Data To Frequencies and Audio Parameters

Great! Now we’re ready to use this information and map it to sounds.

If it’s your first time playing around with Sonic Pi, don’t be nervous, there is not much you need to know about music and sound design in order to start playing around.

Sonic Pi Basics

Here is a very simplified explanation of the main functions we’ll use that are specific to Sonic Pi. If you want to go more in depth, have a look at the Sonic Pi documentation, all the different methods and parameters are very clearly explained.

  • play : play a given frequency (takes a number or a symbol representing a frequency as argument)

  • sleep : Waits given amount of time before executing the next operation. Takes a number as argument.

    Sleep will come in very handy because it allows us to “slow down” the algorithm and really listen to what’s going on.

  • sample : a sample is simply a pre-recorded sound that we can use and manipulate. Sonic Pi comes with its own sample library.

  • in_thread : This function allows us to indicate to Sonic Pi that we want events to happen simultaneously

  • bpm : short for beats per minute. Allows us to choose the speed at which our sounds will be played. Sonic Pi has a default bpm of 60, which makes it easy to conveniently map events to seconds (so sleep 1 at the default bpm of 60 means “sleep for 1 second”).

With that you have everything you need to understand the next part of this tutorial.

Let’s start by defining a range of frequencies we will use as our unsorted list. For best results, we want to stay in a range that is audible (I like to stay in the 50 to 80 range).

For now, I suggest that you start by using the array I’m giving you below. The reason for that is because I generated this array by using a bit of music knowledge and I “just know” it’ll sound decent. But if you feel ready to experiment or you have some experience with Sonic Pi, feel free to come up with your own unsorted arrays.

**** Quick Note: If you’d like to have some music pro tips and tricks to improve your coding experience with Sonic Pi, please let me know in the comment section below.

I’m playing with the idea of making a “Music Tutorials For Programmers” series but I don’t know if that would be interesting for anyone so your feedback and suggestions would be very much appreciated. ***

In a new Sonic Pi buffer (not the one with your Ruby code… not yet), copy/paste the following lines and press play:

unsorted_arr = [81, 79, 69, 59, 55, 71, 83, 52, 64, 74, 76, 62, 57, 67, 86, 88]
unsorted_arr.each { |num| play num; sleep 0.25 }

This is what our unsorted list sounds like. Notice that the lower the numerical value, the lower the pitch. So once sorted, we will end up with a sequence that gradually goes from low to high pitch.

Start Tracking Data With Sounds Through Sonic Pi

Now let’s go back to the buffer where our code for bubble sort is. The first thing we’ll do is make a copy of the original array so that the function doesn’t directly modify it (that’ll become important if you want to loop your function call… more on that later).

Then, we probably want to hear at least once the unsorted array at the beginning and once the final sorted array at the end.

Create a copy of the array using dup and add a loop using each before and after the while loop in the function:

unsorted_arr = [81, 79, 69, 59, 55, 71, 83, 52, 64, 74, 76, 62, 57, 67, 86, 88]

def bubble_sort array
  arr = array.dup # Create a copy of original array for sorting
  swapped = false
  r = arr.length - 2
  
  # DATA - Tracking variables
  array_states = []
  total_swaps = 0
  swaps_per_iter = []
  num_iters = 0
  time_of_exec = 0
  
  # Play the unsorted array once
  # Each note is played at an interval of 0.25s
  arr.each { |n| play n; sleep 0.25 }
  
  start_time = Time.now # Start calculating time of execution
  
  while true do
    ...
    # rest of your code here...
    ...
  
  # Plays the final sorted array once
  arr.each { |n| play n; sleep 0.25 }

  # return the sorted array and all the tracking data
  [arr, total_swaps, swaps_per_iter, num_iters, time_of_exec, array_states]
  end
  
  # Get rid of the print statements and replace them with a 
  # simple call to your function
  bubble_sort unsorted_arr

Now if you press play, you should hear the array played twice: first time unsorted, second time sorted. We still don’t hear anything that the algorithm is doing though. Time to play around inside the loop where all the sorting process happens.

We want to start by doing two things:

  • Play the current value that is being compared and sorted

  • Have some kind of audio indication that a swap event happened

Playing notes at a reasonable time interval will allow us to slow down the algorithm and give us a chance to listen to what it’s doing step-by-step.

for i in 0..r 
        play arr[i] # Play current value
        sleep 0.25 # Wait 0.25s
        if arr[i] > arr[i+1]
          arr[i], arr[i+1] = arr[i+1], arr[i]
          swapped = true if !swapped
          sample :elec_blip2 # Play a sound when a swap happens
          sleep 0.25 # Wait for 0.25s
          swaps += 1 # Keep track of the number of swaps 
        end
      end

Ok great! Now with these modifications we can start to get an auditive sense of whats happening.

We hear when a swap happens and we hear the value slowly bubbling through towards the end of the list. The reason for that is because we always play the value at index i. If a swap happens, the value at index i will become the value at index i+1… so the next time we play a value at index i it will be the same as the previous time around. This is interesting because it allows us to hear how many times a value has been swapped.

To clearly mark a swap event, we play a sample (I chose :elec_blip2 but feel free to experiment!).

To give us a better sense of the swapping process, let’s also play the value that was compared to the current value after a swap event occurs:

...
sample :elec_blip2
sleep 0.25
play arr[i] # Play the value which the current value was being compared to
sleep 0.25
swaps += 1
...

Now, let’s add a few percussive elements to 1) mark the start of a new iteration 2) keep track of the number of iterations we did so far.

For that, I’m going to use a bass drum sample that will give a low kick every time we enter the loop and a cymbal sample that will play as many times as we have current iterations (so once after one iteration, twice after two iterations, etc…). 

...
while true do
      swaps = 0
      num_iters += 1 # Keep track on the number of iterations we did so far
      
      in_thread do
        # Plays once every time we enter the loop
        sample :bd_tek 
      end
       
      in_thread do 
        # Plays a sound as many times a we have iterations so far
        # Divide sleep time equally between each cymbal sound
        num_iters.times do 
          sample :drum_cymbal_closed
          sleep (2.0 / num_iters).round(2) 
        end
      end
   ...

Taking It To The Next Level: Making Real Music With Bubble Sort and Ruby

Ok. I know what you’re thinking. This is not exactly the grand musical masterpiece you signed up to create at the beginning of this tutorial. Well, now is the time to spice things up and make it interesting.

For that, we are going to use a few parameters that are specific to sound manipulation which you might not be familiar with so let’s go through them one by one.

  • amp : This affects the volume at which a sound is played (default value is 1).

  • attack, sustain, decay, release : Each of these parameters affect a different part of the sound wave. The attack is how quickly or slowly you enter the sound, sustain is how long will this sound be heard at its maximum level, decay indicates how long it takes for the sound to decrease and release is how long it takes after the decay period until the sound stops.

  • rate : Rate applies to samples and indicate at what speed the sample should be played at. It’s comparable to doing a fast forward or slowing down a video (not to be confused with the speed indicated by the bpm or the value passed to sleep).

  • beat_stretch : This parameter comes in very handy when dealing with longer samples. If you play samples that are many beats long, you can tell Sonic Pi to fit the sample into a specific number of beats. Sonic Pi will speed or slow down the sample accordingly for you.

  • use_bpm : Allows us to change the default bpm and change the speed of what is being played.

  • use_synth : Sonic Pi comes with a library of synthesizers we can use to play notes. If not specified, Sonic Pi will use the sine synthesizer by default (that’s the one you are hearing until now if you are following the tutorial).

Now that we have the technical stuff out of the way, let’s continue by speeding things up a bit. At the top of your buffer, after your variable declaration, change the bpm to something greater than 60, for example:

use_bpm 90

Now that everything is playing at a more comfortable speed, let’s work a little bit on that cymbal sound. Right now, it’s always playing at the same volume. It’s ok when we have a few iterations but it starts to be annoying when we hear it a lot.

To improve it, I decided to create a crescendo effect (starts soft and gradually plays louder and louder) by affecting the amp parameter every time a cymbal sound is played. I’m also changing the rate of the sample from the default value of 1 to 2 to make the cymbal sound crisper.

in_thread do # Gives a sense of how many iterations we've done so far
    num_iters.times do |i|
        sample :drum_cymbal_closed, amp: 1.0 + (i.to_f / 2.0), rate: 2
        sleep (2.0 / num_iters).round(2)
    end
end

Ok, great. Now we can work a little bit on our main melody, which is the array being sorted.

It would be nice to have a way to differentiate the current value from the value its being compared to. In order to do that, I chose to affect the duration of the sound. By changing the default value of the release parameter, we can make the sound shorter.

I’m also going to bump a little bit the volume of :elec_blip2 because I feel it’s starting to get a bit lost with everything else going on.

 for i in 0..r 
    play arr[i], release: 0.1 # Shorten the note by affecting release param
    sleep 0.25
    if arr[i] > arr[i+1]
        arr[i], arr[i+1] = arr[i+1], arr[i]
        swapped = true if !swapped
        sample :elec_blip2, amp: 1.5 # Increase the volume slightly
        sleep 0.25
        play arr[i] # hear the value which the current value is being compared to
        sleep 0.25
        swaps += 1
    end
 end

Nearly there! It’s already starting to sound much better but there is still a few simple tricks we can apply that will improve it even more.

How about having a bass sound that gives a ground for all the frequencies playing on top of it? We can very easily create a basic pad that is going to give us a bit of ambiance.

Because we want this pad to start at the beginning of the loop and continue for the whole iteration, I’m going to integrate it inside the same thread as our drum kick:

in_thread do
    # Gives a bass frequency (take lowest value of the array)
    use_synth :dsaw
    play 52, amp: 0.5, attack: 2, sustain: 6, decay: 2, release: 4, cutoff: 60
    sample :bd_tek # Tracking when we are entering the loop
end

You can play around with the sounds and the parameter values!

Creating A Custom Sorted Function

Now for the last addition to our code. It would be nice to not only hear the sorted array but make something different and interesting with it that clearly indicates that the list is now sorted.

So instead of just iterating over the sorted array, we’ll create a new function (which I called sorted) which we’ll call after breaking out of the loop.

This part is really up to you and doesn’t have much to do with the algorithm itself apart from indicating a successful sorting so feel free to be creative and experiment!

Here is my sorted function:

def sorted arr
  4.times do # Play the sorted array 4 times
    in_thread do
      arr.each { |n|
        play n, release: 0.1
        sleep 0.25
      }
    end
    # Plays once at the beginning of the iteration
    in_thread do 
      sample :bd_tek
      sleep 16
    end
    # Gives a nice and steady rythm that marks we have successfully sorted the list
    sample :loop_breakbeat, beat_stretch: 4, amp: 2
    sleep 4
  end
end

Once we have a function to trigger with our sorted array, the only thing left to do is call it inside bubble_sort.

Last but not least, we can give our piece a bit more “vibe” by wrapping the call to bubble_sort inside a reverb effect (I just love reverb 😋).

And if you want to get fancy, try wrapping your call to bubble_sort inside a live_loop to have it repeat over and over again (that’s where making a copy of the array instead of changing the original array comes in handy).

For simplicity’s sake, I won’t go into details about live_loops here but if you are curious you can refer to Sonic Pi’s documentation.

Here is the final code (if you don’t see it in your browser, try refreshing the page).

And there we have it! We created a decent audio representation of the bubble sort algorithm using Ruby and Sonic Pi! This representation is cool to listen to but also gives us clear information on how the algorithm works under the hood.

Here’s a simple video posted on Instagram that shows how it should sound like if you followed all the steps as explained (don’t be shy to follow me on Instagram or drop me a comment!):

 
 
 

Here is a video where I take the material from this article and play around with it.

 

Conclusion

Learning basic algorithms is an important part of becoming a good programmer. I hope this tutorial inspired you to be creative with the concepts you learn in computer science and programming in general.

In the next post, we will look at insertion and selection sort. Specifically, we’ll build audio representations of these algorithms to examine the theory explained by Professor Graham Hutton in this video which says that insertion sort and selection sort are the same.

Did you come up with creative ways to play around with bubble sort? 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.

 
Tutorials, Creative CodingMynah Mariesonicpi, bubblesort, algorithms, featured4 Comments