Let's Learn Algorithms: Implementing Bubble Sort

In the last article we went over how the bubble sort algorithm works, optimizations for it, and the Big-O complexity of the algorithm. This article will take this all a step further and walk through writing an implementation of the algorithm.

We are going to start with an implementation that doesn’t use any optimizations, which will be the majority of this post, and then we will discuss how to add the optimizations into our code.

After all of that I will present you with a few practice problems to try to solve. I strongly encourage you to try your hand at each of these problems and tune in to the follow-up article where I cover how to solve each of the problems.

Implementing bubble sort without any optimizations

I mentioned this in the introduction to the Let’s Learn Algorithms series, but I will be writing my solutions in Go.

I will intentionally be trying to use code that is easy to understand, so if you are familiar with Golang and find yourself thinking “he could have just done x” you are probably right, but I don’t want to do anything too fancy that a non-Go developer wouldn’t know about :)

Now let’s jump into bubble sort. If you remember the solution we described in the last article, it was roughly broken into two pieces:

1. The “sweep” where we compared pairs of numbers in the array and swapped them if the first item in the pair was greater than the second.

2. The “loop” that ran the sweep N times, where N is the size of the list we are sorting.

We are going to take a second to think about each of these pieces in pseudo-code before we actually implement them. First lets look at the sweep.

Implementing the “sweep” portion of bubble sort

In pseudo-code, the sweep portion of the bubble sort algorithm can be roughly written as the following.

for each pair (first, second) in consecutive pairs:
  if first > second:
    swap(first, second)
  else:
    # Do nothing!

We are doing a lot of hand waiving here, but conceptually it covers everything in the algorithm. We iterate over each consecutive pair, compare them, and swap if the first is greater than the second.

Now let’s translate this into real code. To do this we are going to write a function named sweep() that takes in an integer slice and modifies it.

func sweep(numbers []int) {
  // our algorithm will go here.
}

Now we need to walk through our pseudo-code and fill in our function. We will start with the for loop and ask ourselves, how do I make a for loop that allows me to look at each consecutive pair in an array?

Let’s look at an example array to see if we get any ideas. First lets look at our first pair.

index =  0  1  2  3  4  5
A     = [5, 4, 2, 3, 1, 0]
pair  =  ^  ^

In this example, pair appears to be pointing at the numbers at the indexes 0 and 1. Let’s move on to the next pair to see how that changes.

index =  0  1  2  3  4  5
A     = [5, 4, 2, 3, 1, 0]
pair  =     ^  ^

Hmm, it looks like our new indexes are 1 and 2, so it appears that our indexes start at 0 and 1 and each increase by 1. But when does this end? What is our exit criteria for our loop?

index =  0  1  2  3  4  5
A     = [5, 4, 2, 3, 1, 0]
pair  =              ^  ^

This is the last pair we will look at, and in this case our indexes are 4 and 5. What are those values in relation to the size of our list? Well, our list has a size of 6, so it looks like our loop needs to terminate when the index of the second item in our pair is >= N, where N is the size of our list.

If a for loop needs to terminate when a value is >= N, this is the same as saying it should continue running as long as the value is < N. We can write that in a for loop like so.

func sweep(numbers []int) {
  // Go head and set N as the size of our list.
  var N int = len(numbers)

  // We know firstIndex and secondIndex need to start at 0
  // and 1, so we can initialize them with those values.
  var firstIndex int = 0
  var secondIndex int = 1

  // We just decided that our for loop needs to end when
  // secondIndex is >= N, so we write this like below.
  //
  // NOTE: Go doesn't have a "while" loop. It instead uses
  // the "for" loop for all loops. In other langauges you
  // may need to replace this with
  //
  //    while(secondIndex < N) { ... }
  //
  // Later in this lesson we will move it to a for loop in
  // every language.
  for secondIndex < N {
    // This is where we will compare the number at
    // firstIndex and secondIndex and swap if they are out
    // of order.

    // Once we finish our sweep we need to increment our
    // indexes so that we start looking at the next pair.
    firstIndex++
    secondIndex++
  }
}

When we are first learning an algorithm it is good to test that our code is working as anticipated, so lets go ahead and test this. Add the following code INSIDE of your for loop.

var firstNumber int = numbers[firstIndex]
var secondNumber int = numbers[secondIndex]
fmt.Println("Comparing the following:", firstNumber, secondNumber)

Now we are going to test this code. I don’t mean by writing a test, but instead we are going to test it simply be writing a main() function and passing in a list of numbers to see what happens.

Rather than show you all of this code and having you type it up just to throw it away, you can instead head over to the Go Playground to check it out. Make sure you run the code! The link is here: https://play.golang.org/p/IiwBGZlFg6

When you run the code you should see the following output:

Our list of numbers is: [5 4 2 3 1 0]
Comparing the following: 5 4
Comparing the following: 4 2
Comparing the following: 2 3
Comparing the following: 3 1
Comparing the following: 1 0

It looks like our code is looking at each pair in our list in the order we expected, so we can move on with some confidence that our current code works. Sweet!

So far our code will iterate over each pair in the list, so now we need to move to the next line in our pseudo-code; We need to start comparing the first and second numbers. This is pretty simple to code up, so lets add it.

func sweep(numbers []int) {
  // ... other code from before

  for secondIndex < N {
    var firstNumber int = numbers[firstIndex]
    var secondNumber int = numbers[secondIndex]

    if firstNumber > secondNumber {
      // Swap the numbers if this happens!!!
    }

    // Once we finish our sweep we need to increment our
    // indexes for our pair.
    firstIndex++
    secondIndex++
  }
}

Now comes a slightly more complicated part. We need to swap the numbers if the first is greater than the second. To do this we basically need to overwrite the values stored in our numbers slice (again, this is similar to an array). That means we need to set the value of numbers[firstIndex] to the secondNumber and similarly we need to set the value of numbers[secondIndex] to firstNumber. Below is code showing how to do this.

// ... other code from before
if firstNumber > secondNumber {
  numbers[firstIndex] = secondNumber
  numbers[secondIndex] = firstNumber
}
// ... other code from before

If we did everything right, our sweep() function should be done. We are going to test it like before, and you can see that code here: https://play.golang.org/p/GHTXwCJuYZ

Running this code will get the following output.

After 0 sweep(s): [5 4 2 3 1 0]
After 1 sweep(s): [4 2 3 1 0 5]

It looks like our code is correctly sweeping, as the 5 was moved to the final index and every other number was shifted left one position. Awesome! Now we are ready to move on to the second part of our algorithm, the loop that uses our sweep() function N times, but before we do that I want to give you a cleaned up copy of our code without any comments, since this can be helpful for those of you in another language.

package main

import "fmt"

func main() {
  var numbers []int = []int{5, 4, 2, 3, 1, 0}
  fmt.Println("After 0 sweep(s):", numbers)

  sweep(numbers)
  fmt.Println("After 1 sweep(s):", numbers)
}

func sweep(numbers []int) {
  var N int = len(numbers)
  var firstIndex int = 0
  var secondIndex int = 1

  for secondIndex < N {
    var firstNumber int = numbers[firstIndex]
    var secondNumber int = numbers[secondIndex]

    if firstNumber > secondNumber {
      numbers[firstIndex] = secondNumber
      numbers[secondIndex] = firstNumber
    }

    firstIndex++
    secondIndex++
  }
}

Implementing the outer loop for bubble sort

Next we are going to be writing our outer loop that calls the sweep() function. Like before, let’s look at this in pseudo-code before proceeding.

N times do:
  sweep(numbers)

Looks pretty simple right? That is because it is!

This section is going to go much faster than the previous section because we basically just need a loop that runs N times and calls our sweep() function on each pass.

We are going to write this inside of a function named bubbleSort() because it is the topmost level of our algorithm and is what other code will call to sort a list. Go ahead and create the function to get started.

func bubbleSort(numbers []int) {
  // Outer loop goes here
}

Now we add the loop that runs N times, and call sweep() inside of that loop.

func bubbleSort(numbers []int) {
  var N int = len(numbers)
  var i int
  for i = 0; i < N; i++ {
    sweep(numbers)
  }
}

Voilà! We now have a completed bubble sort algorithm! We can test this by updating our main function to call bubbleSort() instead of calling sweep(). You can check out the final code below or you can run it on the Go Playground here: https://play.golang.org/p/SL5FV2WLBV

package main

import "fmt"

func main() {
  var numbers []int = []int{5, 4, 2, 3, 1, 0}
  fmt.Println("Unsorted:", numbers)

  bubbleSort(numbers)
  fmt.Println("Sorted:", numbers)
}

func bubbleSort(numbers []int) {
  var N int = len(numbers)
  var i int
  for i = 0; i < N; i++ {
    sweep(numbers)
  }
}

func sweep(numbers []int) {
  var N int = len(numbers)
  var firstIndex int = 0
  var secondIndex int = 1

  for secondIndex < N {
    var firstNumber int = numbers[firstIndex]
    var secondNumber int = numbers[secondIndex]

    if firstNumber > secondNumber {
      numbers[firstIndex] = secondNumber
      numbers[secondIndex] = firstNumber
    }

    firstIndex++
    secondIndex++
  }
}

Now that we have working code we can move on to optimizations.

Optimizing our bubble sort implementation

In the introduction to bubble sort we talked about two optimizations:

1. Don’t compare numbers that are already in their final position.
2. Stop sorting if our list is already sorted.

In this section we are going to implement both of those optimizations.

Don’t compare numbers that are already in their final position

In order to implement this optimization we need to change both our bubbleSort() and our sweep() function. In our sweep() function we need to provide it with some way to know which numbers are already sorted, and in our bubbleSort() function we need to keep track of this number and provide it to the sweep function.

Let’s start by updating our sweep() function with a second argument, prevPasses, which tells us which how many previous passes we have done.

func sweep(numbers []int, prevPasses int) {
  // ... keep this the same for now
}

In the introduction I said that for every iteration i of our outer loop (the loop inside of bubbleSort), we know that the last i - 1 numbers are in their correct position. Or in other words, if there have been 2 previous passes and we are currently on pass 3, the last 2 numbers are in their correct position.

This means that the prevPasses argument will tell us exactly how many numbers we can ignore, so we can update our code to take this into consideration like so.

func sweep(numbers []int, prevPasses int) {
  var N int = len(numbers)
  var firstIndex int = 0
  var secondIndex int = 1

  for secondIndex < (N - prevPasses) {
    var firstNumber int = numbers[firstIndex]
    var secondNumber int = numbers[secondIndex]

    if firstNumber > secondNumber {
      numbers[firstIndex] = secondNumber
      numbers[secondIndex] = firstNumber
    }

    firstIndex++
    secondIndex++
  }
}

Now we need to update the bubbleSort() function to provide the number of previous passes, which happens to be stored in the value i in our for loop.

func bubbleSort(numbers []int) {
  var N int = len(numbers)
  var i int
  for i = 0; i < N; i++ {
    sweep(numbers, i)
  }
}

Now let’s go ahead and test our code. You can run the code by going here: https://play.golang.org/p/BwFBrP7Ej0

It is now time to move on to our final optimization - early termination of our for loop in bubbleSort() if the list is already sorted.

Stop sorting if our list is sorted

To make this happen we need to do two things.

First, we need some way for the sweep() function to tell us that it didn’t actually swap any numbers. Second, we need to use this information to terminate our for loop in bubbleSort() early.

The first requires us to modify the definition of our sweep() function and to add a return variable to it.

func sweep(numbers []int, prevPasses int) bool {
  // don't change this yet
}

In Golang this means that our function is going to return a boolean, so we now need to update our function to actually return something!

To do this we need to first declare a variable didSwap and set it to false at the start of the function. After that we want to make sure we set it to true if and only if we swap some numbers. Finally, we need to return the value in didSwap at the end of our function.

The resulting code is shown below.

func sweep(numbers []int, prevPasses int) bool {
  var N int = len(numbers)
  var firstIndex int = 0
  var secondIndex int = 1
  var didSwap bool = false

  for secondIndex < (N - prevPasses) {
    var firstNumber int = numbers[firstIndex]
    var secondNumber int = numbers[secondIndex]

    if firstNumber > secondNumber {
      numbers[firstIndex] = secondNumber
      numbers[secondIndex] = firstNumber
      didSwap = true
    }

    firstIndex++
    secondIndex++
  }
  return didSwap
}

To use this in our bubbleSort() function we simply need to check the return value of our call to sweep(). If it is true, we know our loop needs to continue running. If it returns false we know that our list is already sorted and we can stop trying to sort it.

func bubbleSort(numbers []int) {
  var N int = len(numbers)
  var i int
  for i = 0; i < N; i++ {
    if !sweep(numbers, i) {
      return
    }
  }
}

The final code can be seen below and run on the Go Playground here: https://play.golang.org/p/oywm6Sy78t

package main

import "fmt"

func main() {
  var numbers []int = []int{5, 4, 2, 3, 1, 0}
  fmt.Println("Unsorted:", numbers)

  bubbleSort(numbers)
  fmt.Println("Sorted:", numbers)
}

func bubbleSort(numbers []int) {
  var N int = len(numbers)
  var i int
  for i = 0; i < N; i++ {
    if !sweep(numbers, i) {
      return
    }
  }
}

func sweep(numbers []int, prevPasses int) bool {
  var N int = len(numbers)
  var firstIndex int = 0
  var secondIndex int = 1
  var didSwap bool = false

  for secondIndex < (N - prevPasses) {
    var firstNumber int = numbers[firstIndex]
    var secondNumber int = numbers[secondIndex]

    if firstNumber > secondNumber {
      numbers[firstIndex] = secondNumber
      numbers[secondIndex] = firstNumber
      didSwap = true
    }

    firstIndex++
    secondIndex++
  }
  return didSwap
}

Practice problems

I am going to try to present you with three practice problems. All of which are a little more challenging than what we walked through, so don’t be frustrated if you get stuck. Feel free to ask questions on reddit or to send me an email. I’ll gladly try to help without giving the solution away :)

1. Sort a list of 25 numbers in REVERSE order

Given the array of numbers:

[21, 4, 2, 13, 10, 0, 19, 11, 7, 5, 23, 18, 9, 14, 6, 8, 1, 20, 17, 3, 16, 22, 24, 15, 12]

Sort the list in decreasing order with a bubble sort. That is, sort is in reverse of how you normally would. The final list should look like this:

[24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0]

You can see the boiler plate code (and translate it into your own language of preference) on github.com/joncalhoun/lets_learn_algorithms.

2. Sort a list of animals (strings) in alphabetical order

Given the array of strings that are all animal names like so:

["dog", "cat", "alligator", "cheetah", "rat", "moose", "cow", "mink", "porcupine", "dung beetle", "camel", "steer", "bat", "hamster", "horse", "colt", "bald eagle", "frog", "rooster"]

Sort the list in alphabetical order with a bubble sort. The final list should look like this:

["alligator", "bald", "eagle", "bat", "camel", "cat", "cheetah", "colt", "cow", "dog", "dung", "beetle", "frog", "hamster", "horse", "mink", "moose", "porcupine", "rat", "rooster", "steer"]

You can see the boiler plate code (and translate it into your own language of preference) on github.com/joncalhoun/lets_learn_algorithms.

func greaterThan(a, b string) bool {
  // return true if string a is "greater than" b. That is, return true if a comes AFTER b in alphabetical order.
}

3. Sort a User object by last, then first name.

This one is going to be a bit harder, especially since you will need to translate some Go code into your own language, but the goal is given a list of users with a first and last name, sort them in alphabetical order by their last name, and if two last names are the same, sort them by their first name.

You will be given a list of users with first and last names like so:

Jon Calhoun
Bob Smith
John Smith
Larry Green
Joseph Page
George Costanza
Jerry Seinfeld
Shane Calhoun

And your code should output the list sorted by last name, then first name if there is a tie with the last name, like so:

Jon Calhoun
Shane Calhoun
George Costanza
Larry Green
Joseph Page
Jerry Seinfeld
Bob Smith
John Smith

Use the hint from problem #2 if you get stuck, but you will need to expand it a bit to make it work on this problem.

You will want to check out the boiler plate code and translate it into your own language of preference to get started, as this shows you how I created a type to store the user object. It is here: github.com/joncalhoun/lets_learn_algorithms.

Up Next…

Spend some time this week going over these problems. Ask questions. Email me or or post your questions on Reddit, but make an honest attempt at coding each of them before doing so.

Once you have done that you can check out the solutions here:

• Pratice Problem #1 - Reverse sorting a list of numbers
• Pratice Problem #2 - Sorting a list of strings
• Pratice Problem #3 - Sorting a custom type (not published yet)