Insertion Sort in Go

Recently, I have been diving into the internals of Terraform and some of the providers as I look at terraform-policymaker, as it only makes empty policy definitions and it may be an issue with the significant revisions on the AWS provider since its last update. This means, while becoming more familiar with Go, it is time to walk through some of the algorithms in The Algorithm Design Manual, as one does.

I like working through the examples in various languages having practiced with C, Java, PowerShell, C#, and Python.

Insertion sort is an algorithm to sort various elements in an ascending order.

Here is the code example from:

	insertion_sort(item s[], int n)
	{
	int i, j

	for (i=1; i<n; i++) {
	j=i;
	while ((j>0) && (s[j] < s[j-1])) {
	swap(&s[j],&s[j-1]);
	j = j-1;
	}
	}
	}

view raw main.c hosted with ❤ by GitHub

In my Go example, it will take an argument from the command line and sort it. I won’t implement it as a function, it will just be completed within main, as it is an exercise. Just before starting it, I didn’t anticipate many of the nuances of Go this simple exercise would touch upon, although I was aware of many of these things beforehand.

The first interesting thing that this touches on is looping syntax in Go. We have the for loop and that is it. We can use it in different ways and it is reminiscent of Python, in that regard. It is mostly semantics, anyhow. When executed as instructions by the CPU, the various syntaxes of loops all end up being the same, generally. Also, this use of the while loop is simply breaking out the components of the for loop rather explicitly, so I just will just the more standard for loop structure of <initialization>; <condition>; increment and be done with it.

As far as libraries, we’ll use the fmt and os packages from the Go Standard Library since the result will be printed and we will take in the information to sort from a command-line argument.

The only thing that through me for a bit of a loop was that Go doesn’t have a char type even though a string is still an array like in so many languages. In Go, characters are either a byte with the Unicode , or a “rune” which is an int32 containing the UTF-8 value .

If we were to convert the rune to a byte, we would use my_byte := byte("A") which would be 65, which is what we would expect with UTF-8. This makes things rather easy when sorting because it is already in a numeric format which the algorithm needs in one way or another. It is a bit strange that it isn’t handled without type conversion, though. If I do not cast the initial string to a byte array, the assigning the individual elements gives an error about assigning a byte. So, I cast it to a byte array and then cast the byte array to a string when printing.

Otherwise, the syntax of Go handling multiple elements together for the swap is rather nice:

	package main

	import (
	"fmt"
	"os"
	)

	var insertion_sort = []byte(os.Args[1])

	func main() {
	for i := 1; i < len(insertion_sort); i++ {
	for j := i; j > 0 && insertion_sort[j] < insertion_sort[j-1]; j– {
	insertion_sort[j], insertion_sort[j-1] = insertion_sort[j-1], insertion_sort[j]
	}
	}

	fmt.Println(string(insertion_sort))
	}

view raw main.go hosted with ❤ by GitHub

The amount of ceremony required in Go is extremely low. Since I want this to be compiled, I make it part of package main on the first line and that expects the func main() for the entry point.

The worst case for insertion sort is O(n^2), if we must iterate through every possible character throughout each loop (basically, if it were sorted in a descending manner.

Breaking the algorithm out into its own function is simple as we will accept a byte array as input and return a byte array as output:

	package main

	import (
	"fmt"
	"os"
	)

	func main() {
	fmt.Println(string(insertion_sort([]byte(os.Args[1]))))
	}

	func insertion_sort(insertion_sort []byte) []byte {
	for i := 1; i < len(insertion_sort); i++ {
	for j := i; j > 0 && insertion_sort[j] < insertion_sort[j-1]; j– {
	insertion_sort[j], insertion_sort[j-1] = insertion_sort[j-1], insertion_sort[j]
	}
	}

	return insertion_sort
	}