2017/11/18

Sorting the gophers

Sorting in go has always been a bit different than other languages. Not that the algorithms for sorting is different, but merely by the fact that go does not have generics.

This is not going to be about the pros/cons of generics. There are plenty of that on the web.

On the other hand i will go through a bunch of examples how to sort your data.

Go contains built in sorting functions for strings and ints and floats, however if you have a slice of structs you are bound to implement some sorting code.

We will sort the gophers using this structure:

type Gopher struct {
	Name string
	Age  int
}

var gophers = []Gopher{
	{"Bob", 31},
	{"John", 42},
	{"Michael", 17},
	{"Jenny", 26},
	{"Alice", 17},
	{"John", 17},
}

Before go 1.8, sorting had to be done by implementing the sort interface (https://golang.org/pkg/sort/#Interface).

// ByAge helper type to sort the gophers by age
type ByAge []Gopher

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

While this required a bunch of boiler plate code to be written, it was reusable across your codebase.

In go 1.8 we got an extra function in the sort package “sort.Slice” that essentially took a function identically to the Less function in the old sort interface. Yay! We can now get rid of some boiler plate code.

sort.Slice(a, func(i, j int) bool {
	return a[i].Age < a[j].Age
})

However we still have to write such a func for each struct we want sorted. Now what if you want to reuse your new sort function? With the old sort interface reusability was easy as it was declared as a type. Well, you still have the possibility to wrap it in another func to help you reusing it.

byAge := func(a []Gopher) func(int, int) bool {
	return func(i, j int) bool {
		return a[i].Age < a[j].Age
	}
}
sort.Slice(a, byAge(a))

If you have multiple reusable sorting functions you can still wrap them in a helper type as what we did with the original Interface.

// NewSorter helper type for multiple sort funcs
type NewSorter []Gopher

// ByAge sorts by age
func (a NewSorter) ByAge(i, j int) bool {
	return a[i].Age < a[j].Age
}

// ByName sorts by name
func (a NewSorter) ByName(i, j int) bool {
	return a[i].Name < a[j].Name
}
sorter := NewSorter(gophers)
sort.Slice(gophers, sorter.ByAge)

This opens up for the possibility to choose order of sorting, sort by multiple keys in the struct etc.

// Ordersorter is a helper type to support order
type Ordersorter struct {
	a     []Gopher
	order bool // asc = true // desc = false
}

// Asc sets asc flag
func (s Ordersorter) Asc() Ordersorter {
	s.order = true
	return s
}

// Desc sets desc flag
func (s Ordersorter) Desc() Ordersorter {
	s.order = false
	return s
}

// ByAge sorts by age
func (s Ordersorter) ByAge(i, j int) bool {
	if s.order {
		return s.a[i].Age < s.a[j].Age
	}
	return s.a[i].Age > s.a[j].Age
}

// NewOrderSorter returns a new instance of ordersorter
func NewOrderSorter(a []Gopher) Ordersorter {
	return Ordersorter{a, true}
}

sorter := NewOrderSorter(gophers)
sort.Slice(gophers, sorter.Desc().ByAge)
sort.Slice(gophers, sorter.Asc().ByAge)

Now you migh think that it is a whole lot of code to write for sorting your struct. And i agree. It is. Which leads me the conclusion.

1) Keep your implementation as simple as possible. 2) Expand your implementation if the need arises. 3) Don’t go all in if all you need is to sort a slice of structs by an int field. Simply use the new sort.Slice func.

How about writing a generator to generate go code to sort your struct in all your possible ways? I haven’t gotten around to that yet but it’s certainly possible to take advantage of go generate for this task. I’ll leave the task for somebody else to implement.

Don’t go generate a bunch of boiler plate code if it’s not needed. It only leads to more code to reason about, more code to maintain, etc.

If you enjoyed reading this, you are more than welcome to support my writing/work/whatever on patreon. For disussions of alternative implementations etc. (not generics related) go here.