Implementing Insertion Sort in Go

👋 Welcome Gophers! In this lesson, we are going to implement the insertion sort algorithm that we looked at in the previous lesson.

Implementation

Let’s start by creating a new file called main.go in a directory called 02-insertion-sort/. We’ll build up the InsertionSort function step by step, just like we did with bubble sort.

Let’s start with the basic setup:

package main

import "fmt"

func main() {
  fmt.Println("Insertion Sorting Algorithm in Go")
}

Now, let’s define the function signature for our insertion sort function:

// InsertionSort - takes in a slice of ints and sorts it in place
func InsertionSort(input []int) {

}

Unlike bubble sort which returned a new slice, we’ll modify the slice in place. This is more memory efficient!

Let’s fill out the InsertionSort function. We’ll iterate through the slice starting from index 1 (since the first element is already “sorted”):

func InsertionSort(input []int) {
  // iterate through the slice starting from the second element
  for i := 1; i < len(input); i++ {
    // store the current element we're inserting
    current := input[i]
    j := i - 1

    // shift elements that are greater than current to the right
    for j >= 0 && input[j] > current {
      input[j+1] = input[j]
      j--
    }

    // insert the current element into its correct position
    input[j+1] = current
  }
}

Let me break down what’s happening here:

The outer loop iterates through each element starting from index 1
We store the current element we’re trying to insert
The inner loop compares the current element with elements before it
If an element is greater than current, we shift it one position to the right
Once we find the correct position, we insert the current element

This builds the sorted portion of the array from left to right. Each iteration ensures that the first i elements are sorted.

Now let’s test it out by creating a slice in our main function and calling our new InsertionSort function:

func main() {
  fmt.Println("Insertion Sorting Algorithm in Go")

  unsortedInput := []int{5, 3, 4, 1, 2}
  fmt.Println("Before:", unsortedInput)

  InsertionSort(unsortedInput)

  fmt.Println("After:", unsortedInput)
}

Perfect! Let’s give this a shot and run it from the command line:

$ go run main.go
Insertion Sorting Algorithm in Go
Before: [5 3 4 1 2]
After: [1 2 3 4 5]

Awesome! Our insertion sort is working correctly. Let’s add a bit more detail to see what’s happening during the sort. Let’s update our function to print out when we’re shifting elements:

func InsertionSort(input []int) {
  for i := 1; i < len(input); i++ {
    current := input[i]
    j := i - 1

    for j >= 0 && input[j] > current {
      fmt.Println("Shifting", input[j], "to the right")
      input[j+1] = input[j]
      j--
    }

    fmt.Println("Inserting", current, "at position", j+1)
    input[j+1] = current
  }
}

Now when we run it again:

$ go run main.go
Insertion Sorting Algorithm in Go
Before: [5 3 4 1 2]
Shifting 5 to the right
Inserting 3 at position 0
Shifting 5 to the right
Shifting 3 to the right
Inserting 4 at position 1
Shifting 5 to the right
Shifting 4 to the right
Shifting 3 to the right
Inserting 1 at position 0
Shifting 5 to the right
Shifting 4 to the right
Shifting 3 to the right
Shifting 2 to the right
Inserting 2 at position 1
After: [1 2 3 4 5]

Perfect! Now you can see exactly how the algorithm is building up the sorted portion of the array by inserting each element into its correct position.

Testing

Let’s create a proper test to validate our implementation works correctly:

func TestInsertionSort(t *testing.T) {
  tests := []struct {
    input    []int
    expected []int
  }{
    {[]int{5, 3, 4, 1, 2}, []int{1, 2, 3, 4, 5}},
    {[]int{1}, []int{1}},
    {[]int{2, 1}, []int{1, 2}},
    {[]int{1, 2, 3, 4, 5}, []int{1, 2, 3, 4, 5}},
    {[]int{5, 4, 3, 2, 1}, []int{1, 2, 3, 4, 5}},
  }

  for _, tt := range tests {
    InsertionSort(tt.input)
    if !slicesEqual(tt.input, tt.expected) {
      t.Errorf("InsertionSort(%v) = %v, want %v", tt.input, tt.input, tt.expected)
    }
  }
}

func slicesEqual(a, b []int) bool {
  if len(a) != len(b) {
    return false
  }
  for i := range a {
    if a[i] != b[i] {
      return false
    }
  }
  return true
}

Conclusion

Awesome! We now have a working implementation of the insertion sort algorithm in Go! It’s simple, efficient for small datasets, and great for nearly-sorted data. Remember that while it has O(n²) complexity in the worst case, it performs very well on small arrays and partially sorted data.

Quiz Time

Try your hand at these questions below to validate what we’ve just covered in this lesson:

Implementing Insertion Sort in Go

Course Instructor: Elliot Forbes

Implementation

Testing

Conclusion

Quiz Time