Using sort.Sort() in Go

Using sort.Sort() in Go

A well written sorting algorithm is hard to replace, and typically the ones that have been battle tested will stand the test of time and stick around for a while. The Go programming language offers a clean abstraction on top of a commonly used sorting algorithm. With the sort  package in the standard library a user can sort arbitrary types in arbitrary ways using a time-proven sorting algorithm.

The way Go has set this up for us is by defining an interface called the sort.Interface. The rule is that as long as a type implements to this interface, it can be sorted.

 

The sort.Interface interface


type Interface interface {
       // Len is the number of elements in the collection.
       Len() int
       // Less reports whether the element with
       // index i should sort before the element with index j.
       Less(i, j int) bool
       // Swap swaps the elements with indexes i and j.
       Swap(i, j int)
}

The interface definition can be found here. The interface defines 3 functions, all of which are critical to the success of the sort.

Len()

The sort works by dividing the length of a collection by 2. So we need a way to determine a length (or size) of a collection. Think of this like the len() function in Go, and usually the len() function is appropriate to use here.

Less()

This is a function that will receive 2 integer indices from the collection. The algorithm assumes the implementation will perform some logic here and make an assertion. The algorithm will not care if a user actually checks if a value is less than another, as that assertion is completely arbitrary. This is analogous to the function used to compare values in C’s qsort()

Swap()

Go takes the sort abstraction one step further, and also makes the user define a Swap() function. This is called after Less() returns false and the algorithm understands that a change is needed. In Go however, you can make Swap() do whatever you want in this case.

Sorting integers with sort.Sort()

A very basic example of defining a sort.Interface implementation is to create an integer alias in Go, and implement the required functions.

type Integers []int

func (s Integers) Len() int {
	return len(s)
}
func (s Integers) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}
func (s Integers) Less(i, j int) bool {
	return s[i] < s[j]
}

This implementation can now be passed to sort.Sort() and sorted on. A full working example of an integer sort with sort.Sort() can be found here in the Go playground, or my raw source here on GitHub.

Sorting structs with sort.Sort()

Below is an example of sorting on a collection of custom types, and using the utf8 package to sort on the int32 value of a rune. This is important because it demonstrates how a user might want to sort on a “calculated” value instead of a literal value.

A user can implement any logic they wish in Less() or in Swap() giving the user a powerful opportunity to build quick and efficient sorting program on any type they can dream of. This is useful in situations where the logic for what a user wants to sort on, might be something different than a simple numerical or alphabetical sort.

type Type struct {
	Value string
}

type Types []Type

func (s Types) Len() int {
	return len(s)
}
func (s Types) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}
func (s Types) Less(i, j int) bool {
	iRune, _ := utf8.DecodeRuneInString(s[i].Value)
	jRune, _ := utf8.DecodeRuneInString(s[j].Value)
	return int32(iRune) > int32(jRune)
}

As always you can run the code in Go Playground, and also see the raw source in GitHub.

Conclusion

The Go programming language offers a familiar and clean abstraction for sorting on arbitrary types and with arbitrary logic. The user can implement any logic they wish in regards to what the sort will use to sort on.

By offering the underlying algorithm and defining the sort.Interface the programming language helps us build powerful sorting programs without enforcing a single opinion on what the algorithm should do but rather how to do it.

Thanks!

Thank you for reading my article. As always, I appreciate any feedback from users. So let me know how we could be better.

Follow @kris-nova

LEAVE A COMMENT

0 comment