I started with Go's sort package for some inspiration on how to build the API for my implementations. It is nice to be able to look at other approaches, especially when I'm more accusotmed to doing things in Node.js or C#.
The Interface
Sorting algorithms generally only need to know how many elements, how to compare two elements, and a way to move elements to different positions. When using Go's sort package, you implement sort.Interface to provide those functions. I thought Sorter was a more helpful name for the interface, but it represents the same thing.
type (
Sorter interface {
Less(i, j int) bool
Swap(i, j int)
Len() int
}
SortAlgorithm func(s Sorter)
)
The SortAlgorithm describes the interface of an implementation. There isn't much of a point to being explicit about this other than decoupling the implementations from the testing code.
Implementations
You can find all of this information in the wikipedia entry. It's pretty brute force; just keep walking the collection and swapping values until it's sorted.
func BubbleSort(s Sorter) {
length := s.Len()
for sorted := false; !sorted; {
sorted = true
for i := 1; i < length; i++ {
if s.Less(i, i-1) {
s.Swap(i, i-1)
sorted = false
}
}
}
}
We can optimize it to make it a little faster by tryin to avoid iterating over parts of the collection that are already sorted:
func OptimizedBubbleSort(s Sorter) {
length := s.Len()
for length != 0 {
newlength := 0
for i := 1; i < length; i++ {
if s.Less(i, i-1) {
s.Swap(i, i-1)
newlength = i
}
}
length = newlength
}
}
Taking it a bit further, we can try out a selection sort. Instead of thrashing back and forth with several swaps, we can swap when we find the smallest value.
func SelectionSort(s Sorter) {
length := s.Len()
for i := 0; i < length-1; i++ {
min := i
for j := i + 1; j < length; j++ {
if s.Less(j, min) {
min = j
}
}
s.Swap(i, min)
}
}
Example
We have a Person struct, and wish to sort a collection of Person objects.
type (
Person struct {
Age int
Name string
}
PeopleBy func(p1, p2 *Person) bool
sortPeople struct {
people []Person
by PeopleBy
}
)
The PeopleBy type represents a function that can compare two people. The naming might seem a bit curious, but I'm taking some creative license for the sake of experimenting with expressive code. More on that in a bit.
The sortPeople struct has the array of Person objects, and a PeopleBy function for dictating a sort order. The struct will implement the Sorter interface:
func (s *sortPeople) Len() int {
return len(s.people)
}
func (s *sortPeople) Less(i, j int) bool {
return s.by(&s.people[i], &s.people[j])
}
func (s *sortPeople) Swap(i, j int) {
s.people[i], s.people[j] = s.people[j], s.people[i]
}
Here is an example of how this sorting code will ultimately be called:
func sortSomePeople(people) {
ageAsc := func(p1, p2 *Person) bool {
return p1.Age < p2.Age
}
PeopleBy(ageAsc).Sort(people)
}
The ageAsc function can be cast to PeopleBy, which has a method attached to it, Sort().
func (by PeopleBy) Sort(people []Person) {
s := &sortPeople{people, by}
BubbleSort(s)
}
Another way to do it would be to organize the code so that you could write something like this:
people.Sort(PeopleBy(ageAsc))
Conclusion
I've explored some rudimentary aspects of implementing sorting in Go. While it's a far cry from using something like LINQ in C#, learning to think about problems in the Go way is a way to gain a fresh perspective on the problem.
It took me a long time to get through this post. Several months, by my count! I'm still hoping to get back in the swing of blogging. Here's hoping that I will find time to get to more Algorithms in Go.