Sorting Algorithms in Go

• Jason Ladd

Sorting lists of numbers is one of the most common tasks in programming. Because of that, it's important to know efficient ways to do it. These are some of the fundamental sorting algorithms implemented in Go.

Bubble Sort

Setp through the list comparing two elements at a time to see which is bigger. If the one on the left is bigger, switch them. On each pass, the largest element will end up being moved to the back of the list. Keep iterating through the list until all elements are in order. It's called bubble sort because the largest element bubbles up to the top of the list on each iteration. This works in O(n^2) time because it uses a nested loop and O(1) space because it doesn't need to use any extra memory. Bubble sort is a stable sorting algorithm which means values that are equal will retain their relative positions to eachother after the sorting is completed.


func BubbleSort(sl *[]int) {
	n := len(*sl)

	for i := range n - 1 {
		for j := range n - i - 1 {
			if (*sl)[j] > (*sl)[j+1] {
				temp := (*sl)[j]
				(*sl)[j] = (*sl)[j+1]
				(*sl)[j+1] = temp
			}
		}
	}
}

3, 10, 2, 1, 21, 5, 0, 8
^  ^

Are 3 and 10 in order? Yes. Check the next pair.

3, 10, 2, 1, 21, 5, 0, 8
   ^  ^

Are 10 and 2 in order? No. Swap them, and move to the next pair.

3, 2, 10, 1, 21, 5, 0, 8
      ^  ^

Are 10 and 1 in order? No. Swap them, and move to the next pair.

3, 2, 1, 10, 21, 5, 0, 8
         ^  ^

Are 10 and 21 in order? Yes. Move to the next pair.

3, 2, 1, 10, 21, 5, 0, 8
             ^  ^

Are 21 and 5 in order? No. Swap them, and move to the next pair.

3, 2, 1, 10, 5, 21, 0, 8
                ^   ^

Are 21 and 0 in order? No. Swap them, and move to the next pair.

3, 2, 1, 10, 5, 0, 21, 8
                   ^   ^

Are 21 and 8 in order? No. Swap them. We're at the end of the list so start back over from the beginning and keep going until the list is in order. Notice how 21, the largest number in the list, bubbled up to the top. On the next run through, 10 would do that until it's right where it's supposed to be in front of 21. Then 8, so on and so forth.

3, 2, 1, 10, 5, 0, 8, 21
                   ^  ^

Insertion Sort

For each value in the array starting at the second element, store that value into a temporary variable and check each value to the left of it with a loop. Inside that inner loop, as long as the one you're currently checking is greater than the element you're focusing on in the outer loop, keep shifting that outer loop element to the left until it's inserted into it's right spot in the array. This happens when the inner loop element you're checking is no longer larger than the one in the outer loop. This works in O(n^2) time and O(1) space. Insertion sort is also stable.


func InsertionSort(arr *[]int) {
	n := len(*arr)

	for i := 1; i < n; i++ {
		temp := (*arr)[i]
		j := i - 1

		for j >= 0 && (*arr)[j] > temp {
			(*arr)[j+1] = (*arr)[j]
			j--
		}

		(*arr)[j+1] = temp
	}
}

3, 10, 2, 1, 21, 5, 0, 8
^  ^
j  i

Store 10 inside of a temp variable. Now, checking all values to the left of 10: Is 3 greater than 10? No, set j + 1 to the temp value, 10. Basically, nothing happens on this iteration. Increment i and j.

3, 10, 2, 1, 21, 5, 0, 8
   ^   ^
   j   i

Store 2 inside of a temp variable. Now, checking all values to the left of 2: Is 10 greater than 2? Yes, so set j + 1 to j, which is 10. Decrement j.

3, 10, 10, 1, 21, 5, 0, 8
^      ^
j      i

Is 3 greater than 2? Yes, so set j + 1 to j, which is 3. Decrement j, so it's now -1.

  3, 3, 10, 1, 21, 5, 0, 8
^       ^
j       i

The inner loop for this iteration is complete since the loop only runs while j is greater than or equal to 0. So set the array at j + 1, which is index 0, to the temp value, 2. 

2, 3, 10, 1, 21, 5, 0, 8
^     ^
j+1   i

2 has been shifted down until it was inserted into it's rightful place in front of 2 and 3. These iterations continue until the entire list has been sorted.

Selection Sort

Start with your first element in the array and assume it's the smallest. Then check every element in the rest of the list to find the actual smallest value. After each scan, you swap that actual smallest value with the element you started the iteration with. Keep doing this until the list is sorted. On each iteration, you select the smallest element and move it to the front of the list, right behind the smallest element from the last iteration until the list is sorted. This works in O(n^2) time and O(1) space. Selection sort is not stable. This means although the list will be sorted, elements which were equal to eachother might end up in a different relative order than they were in before the list was sorted.


func SelectionSort(arr *[]int) {
	n := len(*arr)

	for i := range n - 1 {
		min_index := i

		for j := i + 1; j < n; j++ {
			if (*arr)[j] < (*arr)[min_index] {
				min_index = j
			}

		}
		temp := (*arr)[i]
		(*arr)[i] = (*arr)[min_index]
		(*arr)[min_index] = temp
	}

}

3, 10, 2, 1, 21, 5, 0, 8
^ 
min

Start with the first element and assume it's the smallest. Scan the rest of the list until you find something smaller than that.

3, 10, 2, 1, 21, 5, 0, 8
^  ^
min

10 is not smaller so next...

3, 10, 2, 1, 21, 5, 0, 8
^      ^
min

2 is smaller than 3 so now it's the new min_index

3, 10, 2, 1, 21, 5, 0, 8
       ^  ^
       min

1 is smaller than 2 so now it's the new min_index

3, 10, 2, 1, 21, 5, 0, 8
          ^  ^ 
          min

keep checking...

3, 10, 2, 1, 21, 5, 0, 8
          ^      ^
          min

keep checking...

3, 10, 2, 1, 21, 5, 0, 8
          ^         ^
          min

0 is smaller than 2 so now it's the new min_index

3, 10, 2, 1, 21, 5, 0, 8
                    ^  ^
                    min

8 isn't smaller than 0, so We've reached the end of this iteration and 0 was the smallest number we found, so we swap it with i.

3, 10, 2, 1, 21, 5, 0, 8
^                   ^  
i                   min

0, 10, 2, 1, 21, 5, 3, 8

On this first iteration, we selected the smallest value and put it at the front of the list. On the next go around, we'd end up scanning and finding that 1 is the next smallest value, so when we swap it with i, it will be at index 1, (where 10 currently is). This continues until the entire list is sorted.

Quick Sort

This sorting algorithm uses the 'divide and conquer' strategy. The idea is to use recursion to keep breaking down the array into smaller and smaller arrays until they're just comparisons of two numbers, then swap the elements so that they're in the correct order. To break it down into those smaller arrays, we just pick a 'pivot point', which could be anything, but we'll always choose the last element in the list for simplicity. The only criterea is that all the numbers to the left need to be less than it and all the numbers to the right need to be greater, so we'll shift into place using the Partition() function.

So before we even start, let's break this algorithm down into 3 separate functions so each part is easier to digest. We need to be able to find that pivot index, which will need to be able to swap elements, then we'll recursively call the main QuickSort function on each partition of the array. In bubble sort and selection sort, we've seen how to swap elements. Let's go ahead and break that logic out into a separate function that we can use for our Quick Sort algorithm and anything else that might need it:


func SwapElements(elem1 *int, elem2 *int) {
	temp := *elem1
	*elem1 = *elem2
	*elem2 = temp
}

The main part of the QuickSort function is actually pretty simple, we just split the array into two partitions and recursively call on each piece.


func QuickSort(arr *[]int, start int, end int) {
	if start < end {
		pivot_index := Partition(arr, start, end)
		QuickSort(arr, start, pivot_index-1)
		QuickSort(arr, pivot_index+1, end)
	}
}

But what's the pivot index and how do we find that? The pivot_index is the element that has been put into it's rightful place after we run the Partition() function on the array. Again, this means that all elements to the left of it are less than it and all values to the right are greater than it. Those values aren't sorted yet, but when we further partition them, we'll end up with a bunch of sorted sub-arrays. At that point, the entire original array will be sorted. Let's see how the partioning works.


func Partition(arr *[]int, start int, end int) int {

	pivot := (*arr)[end]
	p_index := start - 1

	for i := start; i < end; i++ {
		if (*arr)[i] < pivot {
			p_index++
			SwapElements(&(*arr)[i], &(*arr)[p_index])
		}
	}

	SwapElements(&(*arr)[p_index+1], &(*arr)[end])
	return p_index + 1
}

  3, 10, 2, 1, 21, 5, 0, 8
^                        ^
p_index                  pivot

pivot is 8 and 3 is less than 8, so increment p_index to 0 and swap it with the first element. We just swapped 3 with 3 so nothing moves yet.

3, 10, 2, 1, 21, 5, 0, 8
^                      ^
p_index                pivot

On the 2nd iteration, 10 is not less than 8 so we do nothing.

But on the 3rd iteration, 2 is less than 8 so we increment p_index to 1 and swap it with the 2.

3, 2, 10, 1, 21, 5, 0, 8
   ^                   ^
   p_index             pivot

But on the 4th iteration, 1 is less than 8 so we increment p_index to 2 and swap it with the 1.

3, 2, 1, 10, 21, 5, 0, 8
      ^                ^
      p_index          pivot

On the 5th iteration, 21 is not less than 8 so we do nothing.

But on the 6th iteration, 5 is less than 8 so we increment p_index to 3 and swap it with the 5.

3, 2, 1, 5, 21, 10, 0, 8
         ^             ^
         p_index       pivot

But on the 7th iteration, 0 is less than 8 so we increment p_index to 4 and swap it with the 0.

3, 2, 1, 5, 0, 10, 21, 8
            ^          ^
            p_index    pivot

Since our loop only goes until we've scanned through all the numbers less than the pivot, we can exit it and do the last step which is...

                  swap
                /     \
3, 2, 1, 5, 0, 10, 21, 8
            ^          ^
            p_index    pivot

3, 2, 1, 5, 0, 8, 21, 10
            ^          ^
            p_index    pivot

Then return p_index + 1, which is the 8

You can probably see what happened here. The array obviously isn't sorted yet, but all the numbers to the left of the pivot are less than it and all the numbers to the right are greater than it. So even though the list isn't sorted, we know the 8 has it's rightful place in the list, so we can ignore it and move on to sorting the parts to the left and to the right of it.

All we have to do that is call QuickSort() on the left side (the start of the array up until 1 element before the pivot) and the right side (1 past the pivot to the end), and because this function is recursive, every time it's called, it will partition the given array until the base case is met (start is no longer less than end). So using our above array, the sorting process will look something like this:

3, 10, 2, 1, 21, 5, 0, 8 // original list, 8 is pivot value
3, 2, 1, 5, 0, | 8 | 21, 10 // 8 is in it's sorted position, choose 0 as pivot for portion of array before 8
|0 | 2, 1, 5, 3, | 8 | 21, 10 // 0 is in it's sorted position, nothing is before 0 so choose 3 as pivot for portion after 0 
|0 | 1, 2, | 3 | 5 | 8 | 21, 10 // 3 is in it's sorted position, choose 2 for next pivot value
|0 | 1 | 2 | 3 | 5 | 8 | 21, 10 // 2 is in it's sorted positon, 1 is the only thing in it's list so it is too (start is equal to end for that array)
|0 | 1 | 2 | 3 | 5 | 8 | 10 | 21 // now finally do the part after 8

All 'starts' equal 'ends' for each recursive call (each list is one item long), so the list is sorted

0, 1, 2, 3, 5, 8, 10, 21

So, putting the whole thing together looks like this:


func Partition(arr *[]int, start int, end int) int {

	pivot := (*arr)[end]
	p_index := start - 1

	for i := start; i < end; i++ {
		if (*arr)[i] < pivot {
			p_index++
			SwapElements(&(*arr)[i], &(*arr)[p_index])
		}
	}

	SwapElements(&(*arr)[p_index+1], &(*arr)[end])
	return p_index + 1
}

func SwapElements(elem1 *int, elem2 *int) {
	temp := *elem1
	*elem1 = *elem2
	*elem2 = temp
}

func QuickSort(arr *[]int, start int, end int) {
	if start < end {
		pi := Partition(arr, start, end)
		QuickSort(arr, start, pi-1)
		QuickSort(arr, pi+1, end)
	}
}

Quick sort runs in O(nlogn) in the best case, but O(n^2) in the worst case. It's also not stable. It's space complexity is O(logn) in the best case and O(n) in the worst case.

Find Kth Largest Element in an Array

How would you go about finding, say the 3rd largest element in that list we started with? Your first thought might be, "First I'll sort the entire array, then count back from the largest element." That would definitly work, but we can do better. Another cool thing about Quick Sort, is because the pivot is always going to fall into it's rightful place when you parition the array, you can also use it to find the Kth largest element in an array without having to sort the whole thing first.

We'll just run Quick Sort until our pivot point is the index we're looking for. For example, if we have a list of 10 numbers, and we want to find the 3rd largest value, we do QuickSort until our pivot point is at index 7 (length of the array minus 3)


func QuickSrt(arr *[]int, desired int, start int, end int) int {
	p_index := Partition(arr, start, end)

	if p_index == desired {
		return (*arr)[p_index]
	}

	if p_index > desired {
		return QuickSrt(arr, desired, start, p_index-1)
	} else {
		return QuickSrt(arr, desired, p_index+1, end)
	}

}

We know our desired index will be the length of the array minus k, so 10 - 3 = 7


func FindKthLargestElement(arr *[]int, k int, start int, end int) int {
	desired := len(*arr) - k

	return QuickSrt(arr, desired, 0, len(*arr)-1)
}

We we can stop sorting when our p_index is at index 7 because we know it's in the place would be if we were to fully sort the list.

Merge Sort

When you call this function, it's going to split the array in half and call itself again with each half until each sub array can't split anymore (when each one only has one value). This is going to stack up a bunch of calls on the call stack. As the call stack unwinds, those sub arrays will start being merged together via the Merge() function. Merge sort is stable and runs in O(nlogn) time and O(log) when run recursively.


package main

func Merge(arr *[]int, start int, middle int, end int) {
	left_array_len := middle - start + 1
	right_array_len := end - middle

	left_array := make([]int, left_array_len)
	right_array := make([]int, right_array_len)

	for i := 0; i < left_array_len; i++ {
		left_array[i] = (*arr)[start+i]
	}

	for j := 0; j < right_array_len; j++ {
		right_array[j] = (*arr)[middle+j+1]
	}

	var i, j, k int

	k = start

	for i < left_array_len && j < right_array_len {
		if left_array[i] <= right_array[j] {
			(*arr)[k] = left_array[i]
			i++
		} else {
			(*arr)[k] = right_array[j]
			j++
		}
		k++
	}

	for i < left_array_len {
		(*arr)[k] = left_array[i]
		i++
		k++
	}

	for j < right_array_len {
		(*arr)[k] = right_array[j]
		j++
		k++
	}
}

func MergeSort(arr *[]int, start int, end int) {
	if start >= end {
		return
	}

	middle := start + (end-start)/2
	MergeSort(arr, start, middle)
	MergeSort(arr, middle+1, end)
	Merge(arr, start, middle, end)
}

Split the array half, by creating a copy of each of those halves

3, 10, 2, 1, 21, 5, 0, 8, 9
3, 10, 2, 1   |   21, 5, 0, 8, 9

The next recursive call splits the first half again

3, 10   |   2, 1   |    21, 5, 0, 8, 9

This is the last split before start would equal end, so we return from the call that did this split and do the second recursive call, which is to split the second half.

3, 10   |   2, 1   |    21, 5   |   0, 8  |   9

Now, we can move on to the merge.

(3, 10)   |   (1, 2)   |    (5, 21)   |   (0, 8) |  (9)

(1, 2, 3, 10)   |    (0, 5, 8, 21)   |   (9)

(0, 1, 2, 3, 5, 8, 10, 21)   |   (9)

(0, 1, 2, 3, 5, 8, 9, 10, 21)

Heap Sort

Heap sort works by transforming the array into a max heap, which is basically a binary tree where each parent node is larger than both of it's children. From there we can take the largest element (the top node) and put it at the end of the array. After that, we won't have a max heap anymore, but we just heapify the array again, then move the new largest element to the next to last element in the array. We just keep doing that until the entire array is sorted. Heap sort is not stable and runs in O(nlogn) time and O(log) when run recursively.


func Heapify(arr *[]int, n int, i int) {
	largest := i
	l := 2*i + 1
	r := 2*i + 2

	if l < n && (*arr)[l] > (*arr)[largest] {
		largest = l
	}

	if r < n && (*arr)[r] > (*arr)[largest] {
		largest = r
	}

	if largest != i {
		SwapElements(&(*arr)[largest], &(*arr)[i])
		Heapify(arr, n, largest)
	}
}

func HeapSort(arr *[]int) {
	n := len(*arr)

	for i := n/2 - 1; i >= 0; i-- {
		Heapify(arr, n, i)
	}

	for i := n - 1; i > 0; i-- {
		SwapElements(&(*arr)[0], &(*arr)[i])
		Heapify(arr, i, 0)
	}
}

So that's pretty much it for the basic sorting algorithms using Go. One more honorable mention is Radix Sort, which I'll cover in another post since this one is already pretty long.

Binary Search in Go

Binary Search is an algorithm that is used to find out if a number exists in a list, and if so, what it's position in that list is. The strategy is to "divide and conquer", which makes it much faster and more efficient than checking every single number.

Working with The Graph Data Structure in Go

Graphs are data structures made up of a bunch of individual nodes that connect to each other. Their main purpose is to model the connection relationships between things. Another name for graphs that you've likely already heard of is "networks".

Binary Trees In Golang

A binary tree is a data structure that consists of a hierarchy of nodes where each node has a maximum of two child nodes that can each also have a max of two child nodes. They offer a way of organizing data that can be fast and efficient to search.

View all posts →