Insertion Sort with an Empty Interface and Tests

If you're not familiar with insertion sort, I recommend this awesome four minute video which depicts insertion sort in Romanian folk dance.

This implementation of a polymorphic insertion sort strengthened my understanding of interfaces in Go, and finally gave me the chance to write some tests. The whole process went through a good number of rewrites and ended up being very similar to the official Go sort package's implementation.

The type of slice used is an empty interface so that any type could be supported.

There are two main files to this writeup that compliment each other:

  • insertionSort.go, contains core implementation.
  • main.go, describes sample usage.

All code can be found at this Github repo.

InsertionSort.go

//insertionSort.go

package sort

func InsertionSort(data Interface) {
    for i := 0; i < data.Len(); i++ {
        for j := i; j > 0 && data.Less(j, j-1); j-- {
            data.Swap(j, j-1)
        }
    }
}

type Interface interface {
    Len() int
    Less(x int, y int) bool
    Swap(x int, y int)
}

Explanation of insertionSort.go

The magic of insertionSort is in the interface. Once we have a named type that implements the interface, we can pass it to insertionSort which will take care of the rest through use of the methods implemented from the interface.

Once that's understood, the rest of insertionSort is fairly simple.

The first for loop iterates through each cell of a slice from left to right:
for i := 0; i < data.Len(); i++

The second for loop starts at wherever i is, and iterates to the left:

for j := i; j > 0 && data.Less(j, j-1); j--

Every iteration of i is an unsorted element, which must be compared against the current sorted element to the left. If the value of the element at sub j (remember that initially j = i) is lesser than the cell directly to the left of it, we need to swap it.

j will always refer to the new cell that is being added, and the swap will keep occuring until the value of the element j is greater than the element to the left.

The second expression of the for loop condition data.Less(j, j-1) helps the loop to quit early. We don't need to make unneccessary trips to elements that are already sorted, so once the new element j is in place, just stop.

main.go

This puts everything to use.

package main

import (
    "fmt"
    "algorithms/sort"
)

type genericArray []interface{}

func (gA genericArray) Len() int {return len(gA)}

func (gA genericArray) Less(x, y int) bool { 
    return gA[x].(int) < gA[y].(int)
} 

func (gA genericArray) Swap(x int, y int) {
    gA[x], gA[y] = gA[y], gA[x] 
}

func main() {
    intSlice := genericArray{2, 4, 12, 7, 1, 3}

    fmt.Printf("\nintSlice before being sorted: %v", intSlice)

    sort.InsertionSort(intSlice)

    fmt.Printf("\n\nintSlice after being sorted: %v\n\n", intSlice)

}

Explanation of main.go

After importing the necessary packages, a named type genericArray is created.

To make use of the InsertionSort function, three methods Len(), Less(), and Swap() must be implemented from the interface that insertionSort takes as an argument. This is done right after the named type is created, and is also what makes this algorithm polymorphic. The insertion sort function will be applicable on any type as long as we implement the methods that it needs to use.

In a way, the sort function can be thought of as an operation or process. Having the interface as an argument can be thought of as a list of tools (methods of the interface) that need to be present before the operation is conducted.

The main function is straightforward. Create a slice of our named type, call the function and pass our slice in.

Testing

I created a test file within the same directory as the package, insertionSort.go, which tests the sorted output of an empty slice, single element slice, slice of multiple elements, and finally a slice of two duplicate elements.

It is adapted from the main.go file above and so only tests slices of integers for now. To implement support for other types, simply implement the interface methods for them, create named types as neede, and that's it (I think).

I would definitely appreciate any comments on this, as I didn't really understand testing in Go, nor do I know of any best practices. I do remember seeing a talk about testing standards at Google I/O 2014 which I will review ASAP.

Other Notes

I would have liked to iterate through the slice using a slice:

for slice := s[0:1];;{
//Do stuff here
if len(slice) + 1 > len(s) {break}
slice = s(0:len(slice) + 1]

Start at the first cell, grow slice by 1 cell through each step, and stop when slice has grown to capacity. Pretty creative, but somewhat confusing.

Things learned

Interface Assertion:

I had to provide my own comparison function. Since the < operator isn't overloaded to handle the interface{} type, and my example was using ints. I simply thought casting would do the trick, which works well from my experience in C:

return int(gA[x]) < int(gA[y])

This returned with the error:

./insertion_sort.go:25: cannot convert gA[x] (type interface {}) to type int: need type assertion

//insertion_sort.go:25: cannot convert gA[y] (type interface {}) to type int: need type assertion

Google led me to this stack overflow thread. Apparently, the compiler won't even attempt to interpret the bits of the value of an empty interface.

From Stephen Winberg on the thread, "A "type assertion" allows you to declare an interface contains a certain concrete type or that its concrete type satisfies another interface."

Quoting the Go Language Specification, "For an expression x of interface type and a type T, the primary expression x.(T) asserts that x is not nil and that the value stored in x is of type T."

So, an assertion needs to be made instead:

`gA[x].(int) < gA[y].(int)`

This assertion lets the compiler know that the value of type interface{} isn't nil, and that it is of the type that is mentioned in parentheses.

Methods

Methods must be bound to named types. The type []interface{} (slice of an empty interface) is not a named type.

Methods cannot be bound to an unnamed type, they need to be bound to a 'thing', an 'object'(?) which in Go is a named type.

In this case, a simple typedef took care of that:
type genericArray []interface{}

Swapping

Instead of creating a variable to temporarily store a value to be swapped:

    var temp, x y
    x, y = 10, 5
    temp = x
    x = y
    y = temp

Simply make the assignments in one statement:

    var temp, x y
    x, y = 10, 5 //x = 10, y = 5
    x, y = y, x //x = 5, y = 10

This way, the values of y and x are evaluated before their values are assigned.

Finally

  • File organization could use some work. I'm thinking about extracting every sorting algorithm in a different file, including interfaces. Not sure If I should do the same for testing functions. I mean, I could always name each test function accordingly.

I hope this was helpful, that's it for now. Will post other thoughts as they come up. If you've made it this far, I really appreciate the time taken to read this post.