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.

Welcome back to another post in the Let's Learn Algorithms series!

In this post we are going to be covering the first practice problem introduced after we discussed how bubble sort works and implemented bubble sort in Go.

We are going to look at how to write bubble sort to sort a list of numbers in reverse (decreasing) order.

If you aren’t already familiar with bubble sort I suggest you check out the previous articles, and if you are unfamiliar with the practice problem and want to give it a try on your own you can see read about it here and you can find the code we will be starting with on github.

The first practice problem for bubble sort is to take a list of 25 numbers and sort them in reverse (decreasing) order.

Truthfully, the size of the list isn’t very important, but I opted to use a list of 25 numbers because I felt this would be large enough to (hopefully) catch any bugs you may have in your code. You could just as easily start off with a list of 5 numbers and then try your code on a larger list once it is done.

Similar to when we implemented bubble sort, we are going to break this problem into two sub-problems. First we are going to write our outer loop (called `bubbleSort()`

in our first implementation), and then we are going to implement the `sweep()`

portion of our bubble sort where we look at each consecutive pair of numbers in our list and swap them if necessary.

If you followed along with the article where we implemented bubble sort, then the outer loop portion of the bubble sort should be pretty straight-forward. It is identical here as it was when we first implemented bubble sort.

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

Your code won’t compile right now because we haven’t written the `sweep()`

function yet, but we will be getting to that shortly.

Aside from the function name, everything here should be the same as our original implementation of bubble sort. We simply call the sweep portion of our code `N`

times, where `N`

is the size of the list.

With that out of the way, we are ready to look at the `sweep()`

function. We are first going to write this like we did when first implementing bubble sort; That is, we are going to sort the numbers in increasing order, and then look at what we need to change in our code to change that order.

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

*Before we proceed you should double check that your code matches the code here: https://play.golang.org/p/-1C2ld4N8v*

This is the same bubble sort algorithm we implemented in the last article with a different main function, so what do we need to change in order to make it sort our list in reverse order?

Well, if you look over the cod you might notice that there is really only one line where are even look at values in our list. Go ahead and find it for yourself. I’ll wait…

If your answer was “the if block starting on line 29” then you found the right block of code! If that wasn’t your answer, then check out the code on line 29 to make sure you understand why we are looking at this code.

The block starts with `if firstNumber > secondNumber {`

and this is the only code where we actually look at values in the list. When we look at them we are asking “Is the first number greater than the second number?”

If that turns out to be true, we then swap our numbers, but that isn’t what we want now. Instead we want to swap our numbers when the reverse is true; We should be swapping numbers when the first is **less than** the second number.

By swapping when the first number is less than the second we will end up pushing the smallest number to the rightmost (highest index) position in the list, and moving larger numbers to positions to the left.

Put another way, if we are comparing two consecutive numbers like `[3, 5]`

we want to move the 3 to the right because that is where it should be in our final list if it is sorted in reverse order, and we want to move 5 to the left. To do this we need to swap these two numbers when the first number (3) is less than the second (5).

This change is pretty simple to make - we simply update line 29 to read `if firstNumber < secondNumber {`

. We only had to change a single character, the `>`

character, into the less than character (`<`

).

Update your code with this change and then run it. You should now have a list sorted in reverse order!

If you are having issues, you can check out and run the final code on the Go playground or check it out below.

```
package main
import "fmt"
func main() {
var numbers []int = []int{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}
fmt.Println("Unsorted:", numbers)
reverseBubbleSort(numbers)
fmt.Println("Sorted: ", numbers)
}
func reverseBubbleSort(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++
}
}
```

The next problem we are going to look at is very similar to this one, but instead of looking at numbers we are going to look at strings.

While this might seem trivial at first, I purposely included an example with strings to help you familiarize yourself with comparing non-numeric values. Many situations in the real world require us to sort values that aren’t strictly numeric, so it is a good idea to be familiar with writing your own comparison code.

As always, if you have an algorithm you would love to learn about check out other articles in the Let's Learn Algorithms series to see if I have already covered it. If I haven’t feel free to get in touch (jon@calhoun.io) and make a request. I am always happy to hear from my readers :)

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 three chapters from the book, and over 2.5 hours of screencasts.

You will also receive notifications when I release new articles, along with other freebies that I only share with my mailing list.

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.