Let's Learn Algorithms: Sorting a list of strings in alphabetical order 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 second 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 strings in alphabetical 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 check out the practice problem here and you can find the code we will be starting with on github.

Sorting a list of strings in alphabetical order

The second practice problem for bubble sort is to take a list of animals (strings) and sort them in alphabetical order. Depending on the language you are coding in this could be really easy, or it could require a bit more code, but don’t worry! I am going to walk you through writing a custom comparison function in case you are using one of those less friendly languages.

Once again, the code we are going to use to get started is going to be pretty similar to our original implementation of bubble sort. In fact, the Go implementation of this problem is identical to the original implementation, except that we need to make a few variables strings (or string slices) instead of integers, and I renamed a few variables (like firstNumber became firstVal) to properly reflect what they store.

The code is shown below. After looking at it, we are going to talk about how this might vary with your language and how to write a custom comparison function. You can also find the code on the Go playground so that you can run it.

package main

import "fmt"

func main() {
  var animals []string = []string{
    "dog",
    "cat",
    "alligator",
    "cheetah",
    "rat",
    "moose",
    "cow",
    "mink",
    "porcupine",
    "dung beetle",
    "camel",
    "steer",
    "bat",
    "hamster",
    "horse",
    "colt",
    "bald eagle",
    "frog",
    "rooster",
  }

  fmt.Println("Unsorted:", animals)
  bubbleSort(animals)
  fmt.Println("Sorted:  ", animals)
}

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

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

  for secondIndex < N {
    var firstVal string = animals[firstIndex]
    var secondVal string = animals[secondIndex]

    if firstVal > secondVal {
      animals[firstIndex] = secondVal
      animals[secondIndex] = firstVal
    }

    firstIndex++
    secondIndex++
  }
}

Now that you have seen the code you are probably thinking “Well that was easy,” and while you aren’t wrong, one of the things that Go is masking here is how we go about comparing strings.

Numbers are relatively simple to compare to one another because every language provides us with a greater than operator for numbers, but not every language provides us with an equivalent for strings, or it might not provide the functionality we want for strings.

For example, is our sort case sensitive? That isn’t really obvious at first glance, so let’s check. Update the list to change cheetah to Cheetah and then run the code. How does that affect your sort?

It looks like our code is case sensitive, but what if we need our sort to be case insensitive? To do this we would need to write our own comparison function.

Sorting a case insensitive list of strings

The first thing we need to do is write a function to use where we compare firstVal and secondVal. This is the start of the if statement inside of the sweep() function, and the line reads if firstVal > secondVal {.

Rather than using the greater than operator (>) we are going to replace this with a function call. We are going to call our function greater(), and it is going to take in two strings and return true if the first is greater than the second, false otherwise.

Update your sweep function so it matches the code below.

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

  for secondIndex < N {
    var firstVal string = animals[firstIndex]
    var secondVal string = animals[secondIndex]

    if greater(firstVal, secondVal) {
      animals[firstIndex] = secondVal
      animals[secondIndex] = firstVal
    }

    firstIndex++
    secondIndex++
  }
}

Next we need to create the greater() function. In it we have a large variety of options available to us, but for simplicity we are going to just use strings.ToLower() to convert our strings to lowercase, after which we will compare then and return the results. This should make our sort case insensitive.

func greater(a, b string) bool {
  if strings.ToLower(a) > strings.ToLower(b) {
    return true
  } else {
    return false
  }
}

With our newly created greater() function we should now have a case insensitive sort! Try running it again with the word Cheetah instead of cheetah and you should see it properly sorted.

Or if you want to run the code on the Go playground you can.

In summary…

While it wasn’t 100% necessary to write a custom comparison function for this problem, I wanted to demonstrate how this can be one because it is a technique that we will be extending in the next practice problem, and then even further in a bonus article where I discuss how to use Go’s sort package to sort any data type.

By breaking the comparison out into a separate function we have created one of only three necessary functions required to sort anything.