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.

But before we can get to the sort package, we first need to look at the final practice problem (not published yet) where you were supposed to sort a custom type based on two fields on the type.

Learn Web Development with Go!

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.

Avatar of Jon Calhoun
Written by
Jon Calhoun

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.

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!

Vote on Hacker News

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.

Recent Articles All Articles Mini-Series Tags About Me Go Courses

©2018 Jonathan Calhoun. All rights reserved.