Let's Learn Algorithms: Reverse sorting a list of numbers with bubble sort

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.

Sorting a list of 25 numbers in reverse order

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

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

Up Next…

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