Sorting techniques in Go


In this post I am sharing a few interesting sorting techniques in Go.

Sorting is one of the most common operations in many programs. Many programming languages provide support to the sorting problem. Go is not an exception in this field. The out-of-the-box sort package provides a mechanism to perform in-place sorting of any collection implementing sort.Interface.

package sort

type Interface interface {
  Len() int
  Less(i, j int) bool
  Swap(i, j int)
}

As you can see, the interface is straightforward and does not require any complex functions. Any type that needs to be sorted must implement three so that the sorting algorithm can: find out the length of a collection, compare two elements, swap position of two elements. The sort package provides a number of functions to sort sliced of standard Go types like strings, integers or floats.

Single sorting function per type

But what happens when we want to sort our slice in a different way than Go provides. Let’s say, I want to sort my strings by a string length and for two strings of the same length I want to use alphabetical order.

We can create a new type whose base type is a slice of strings. That type would need to implement the sort.Interface interface with our comparison algorithm implemented in the Less(i, j int) bool function. Let’s call our new type byLength as in the example below.

type byLength []string

func (a byLength) Len() int { return len(a) }
func (a byLength) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a byLength) Less(i, j int) bool {
  li, lj := len(a[i]), len(a[j])
  if li == lj {
    return a[i] < a[j]
  }
  return li < lj
}

The same approach can be used more complex types. Let’s look at the example of sorting a collection of movies. We will sort movies by release year, title and rate.

import (
  "fmt"
  "sort"
)

type Movie struct {
  Title string  // movie title
  Year  int     // movie release year
  Rate  float32 // movie rating
}

// byYear sorts all movies by release year
type byYear []*Movie

func (m byYear) Len() int { return len(m) }
func (m byYear) Less(i, j int) bool { return m[i].Year < m[j].Year }
func (m byYear) Swap(i, j int) { m[i], m[j] = m[j], m[i] }

// byTitle sorts all movies by title
type byTitle []*Movie

func (m byTitle) Len() int { return len(m) }
func (m byTitle) Less(i, j int) bool { return m[i].Title < m[j].Title }
func (m byTitle) Swap(i, j int) { m[i], m[j] = m[j], m[i] }

// byRate sorts all movies by rate
type byRate []*Movie

func (m byRate) Len() int { return len(m) }
func (m byRate) Less(i, j int) bool { return m[i].Rate < m[j].Rate }
func (m byRate) Swap(i, j int) { m[i], m[j] = m[j], m[i] }

func main() {
  movies := []*Movie{
    &Movie{"The 400 Blows", 1959, 8.1},
    &Movie{"La Haine", 1995, 8.1},
    &Movie{"The Godfather", 1972, 9.2},
    &Movie{"The Godfather: Part II", 1974, 9},
    &Movie{"Mafioso", 1962, 7.7}}

  displayMovies("Movies (unsorted)", movies)

  sort.Sort(byYear(movies))
  displayMovies("Movies sorted by year", movies)

  sort.Sort(byTitle(movies))
  displayMovies("Movies sorted by title", movies)

  sort.Sort(sort.Reverse(byRate(movies)))
  displayMovies("Movies sorted by rate", movies)
}

func displayMovies(header string, movies []*Movie) {
  fmt.Println(header)
  for _, m := range movies {
    fmt.Printf("\t- %s (%d) R:%.1f\n", m.Title, m.Year, m.Rate)
  }
  fmt.Println()
}

The result of the this example is as follows:

Movies (unsorted)
  - The 400 Blows (1959) R:8.1
  - La Haine (1995) R:8.1
  - The Godfather (1972) R:9.2
  - The Godfather: Part II (1974) R:9.0
  - Mafioso (1962) R:7.7

Movies sorted by year
  - The 400 Blows (1959) R:8.1
  - Mafioso (1962) R:7.7
  - The Godfather (1972) R:9.2
  - The Godfather: Part II (1974) R:9.0
  - La Haine (1995) R:8.1

Movies sorted by title
  - La Haine (1995) R:8.1
  - Mafioso (1962) R:7.7
  - The 400 Blows (1959) R:8.1
  - The Godfather (1972) R:9.2
  - The Godfather: Part II (1974) R:9.0

Movies sorted by rate
  - The Godfather (1972) R:9.2
  - The Godfather: Part II (1974) R:9.0
  - La Haine (1995) R:8.1
  - The 400 Blows (1959) R:8.1
  - Mafioso (1962) R:7.7

Multiple sorting functions per type

As you can see, the single sorting function per type approach is straightforward. You must create a separate type for each sorting method. However, this approach has a small disadvantage, namely the Len andSwap methods have identical definitions for all types of slices. Another approach is to create a slightly more complex type that will accept a slice of a specific type and a function providing sorting mechanism.

The following example presents the implementation of a MovieSort type that has a slice of elements to be sorted and function implementing sorting mechanism. You need to provide an instance of the MovieSort type to sort.Sort method. There are also a few methods: sortByYear, sortByTitle and sortByRate implementing sorting mechanism. The displayMovies function is the same as in the previous example.

import (
  "fmt"
  "sort"
)

type MovieSort struct {
  m    []*Movie
  less func(i, j *Movie) bool
}

func (m MovieSort) Len() int { return len(m.m) }
func (m MovieSort) Swap(i, j int) { m.m[i], m.m[j] = m.m[j], m.m[i] }
func (m MovieSort) Less(i, j int) bool { return m.less(m.m[i], m.m[j]) }

func sortByYear(i, j *Movie) bool { return i.Year < j.Year }
func sortByTitle(i, j *Movie) bool { return i.Title < j.Title }
func sortByRate(i, j *Movie) bool { return i.Rate < j.Rate }

func main() {
  movies := []*Movie{
    &Movie{"The 400 Blows", 1959, 8.1},
    &Movie{"La Haine", 1995, 8.1},
    &Movie{"The Godfather", 1972, 9.2},
    &Movie{"The Godfather: Part II", 1974, 9},
    &Movie{"Mafioso", 1962, 7.7}}

  displayMovies("Movies", movies)

  sort.Sort(MovieSort{movies, sortByYear})
  displayMovies("Movies sorted by year", movies)

  sort.Sort(MovieSort{movies, sortByTitle})
  displayMovies("Movies sorted by title", movies)

  sort.Sort(sort.Reverse(MovieSort{movies, sortByRate}))
  displayMovies("Movies sorted by rate", movies)
}

When you run that example you get the same results like in the previous example.

Conclusion

Sorting is one of the most common operations in many programs. It is very likely that you will have to implement sorting at some point or have already done so. You can use one of the techniques shown or mix them together. Note that there is no common approach that would suit all your projects. Sometimes one approach has more sense than the other, but it all depends on your projects. However, the most important is the readability of the code and the ease of maintenance. That’s why you have chosen a solution that helps you to keep these two features of your software.

Happy Coding!


Tags:

#go #sorting


You may also be interested in:



comments powered by Disqus