Extended Courses Discount

My Go courses are discounted for the next few weeks to help out anyone who may need or want access to them. I'm also going to try to help out anyone who can't afford a course, and I will be writing posts about working from home over the next week in an attempt to help anyone new to WFH. Read more here.

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.

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:

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.

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.

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.

What is a slice?

If you are unfamiliar with Go, you may not know what a slice is. In that case, when you read “slice”, just think “array”. The analogy won’t be completely accurate, but it should be close enough that it doesn’t trip you up.

In Go slices are basically a data type built on top of arrays. You can iterate over them, access data by its index, and basically anything else you would do with an array, but slices can also be resized and handle dynamic data much easier. As a result, you will pretty much always see slices being used in human-created code, and arrays will often only be used in generated code or in specific cases where the exact array size is known upfront.

For more on this, I suggest you check out this article on slices from the Go blog.

```
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++
}
}
```

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.

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

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

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

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++
}
}
```

*The only line that changes was the line for secondIndex < (N - prevPasses) {.*

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)
}
}
```

*Again, we only changed one line, the line that reads 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.

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
}
```

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 :)

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.

Hint *If you get stuck, look in our previous code for where we compared numbers to see if they should be swapped. Is there some way you can change this that would cause our list to be sorted in another 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.

Hint *Try turning your if statement that compares the two objects into a function call (shown below) if you are stuck. Does that help you move forward?*

```
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.
}
```

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.

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)

This article is part of the series, Let's Learn Algorithms.

Sign up for my mailing list and I'll send you a FREE sample from my course - Web Development with Go. The sample includes the first few chapters from the book, and over 2.5 hours of screencasts.

You will also receive emails from me about upcoming courses (including FREE ones), new blog posts, and course discounts.

Jon Calhoun is a full stack web developer who also teaches about Go, web development, algorithms, and anything programming related. He also consults for other companies who have development needs. (If you need some development work done, get in touch!)

Jon is a co-founder of EasyPost, a shipping API that many fortune 500 companies use to power their shipping infrastructure, and prior to founding EasyPost he worked at google as a software engineer.

Jon's latest progress update: Writing Course Notes

More in this series

This post is part of the series, Let's Learn Algorithms.

Spread the word

Did you find this page helpful? Let others know about it!

Sharing helps me continue to create both free and premium Go resources.

Want to discuss the article?

See something that is wrong, think this article could be improved, or just want to say thanks? I'd love to hear what you have to say!

You can reach me via email or via twitter.

©2018 Jonathan Calhoun. All rights reserved.