Sorting Algorithms in Go
Tags: go, sort, tutorial
Published: 2020-10-25 22:33:13

Hey, Dev.to community!

As a little project, I've written some famous sort algorithms using Go. I hope this would be useful for you!

# Table of contents
- [Bubble Sort](#bubble-sort)
- [Recursive Bubble Sort](#recursive-bubble-sort)
- [Insertion Sort](#insertion-sort)
- [Selection Sort](#selection-sort)
- [Merge Sort](#merge-sort)
- [Counting Sort](#counting-sort)

# Bubble Sort <a name="bubble-sort"></a>

Bubble sort is a very easy algorithm to follow. You need to check every element of an array against the next element to see if it is larger, if so, you need to swap them. You should do this task as many times as finally there wouldn't be any swap action needed.

```go
package main

import "fmt"

func main() {
	var n = []int{1, 39, 2, 9, 7, 54, 11}

	var isDone = false

	for !isDone {
		isDone = true
		var i = 0
		for i < len(n) - 1 {
			if n[i] > n[i + 1] {
				n[i], n[i + 1] = n[i + 1], n[i]
				isDone = false
			}
			i++
		}
	}

	fmt.Println(n)
}
```

# Recursive Bubble Sort <a name="recursive-bubble-sort"></a>

Recursive bubble sort is a variation of the normal bubble sort (also knows as iterative bubble sort). This works the same as the iterative bubble sort with no extra advantages over time or complexity XD. But this will improve your understanding of bubble sort and recursion:
```go
package main

import "fmt"

func bubbleSort(arr []int, size int) []int {
	if size == 1 {
		return arr
	}

	var i = 0
	for i < size-1 {
		if arr[i] > arr[i+1] {
			arr[i], arr[i+1] = arr[i+1], arr[i]
		}

		i++
	}

	bubbleSort(arr, size - 1)

	return arr
}

func main() {
	var n = []int{1, 39, 2, 9, 7, 54, 11}

	fmt.Println(bubbleSort(n, len(n)))
}

```

# Insertion Sort <a name="insertion-sort"></a>

Insertion sort is a famous sorting algorithm that works like sorting a deck of cards in hand. As you proceed through the elements of an array you would move it back until it is in the correct place.

![Insertion Sort](https://media.geeksforgeeks.org/wp-content/uploads/insertionsort.png)
<figcaption>Credits to https://www.geeksforgeeks.org/</figcaption>

```go
package main

import "fmt"

func main() {
	var n = []int{1, 39, 2, 9, 7, 54, 11}

	var i = 1
	for i < len(n) {
		var j = i
		for j >= 1 && n[j] < n[j - 1] {
			n[j], n[j - 1] = n[j - 1], n[j]

			j--
		}

		i++
	}

	fmt.Println(n)
}
```

# Selection Sort <a name="selection-sort"></a>

Selection sort is quite interesting and yet simple. What you need to do is simply replace the current element in iteration by the lowest value on the right. As you go further the left part of the array is sorted, and you don't need to check for the last element.

![Selection sort](https://dev-to-uploads.s3.amazonaws.com/i/n9139pchafn4yrpozdc6.png)

```go
package main

import "fmt"

func main() {
	var n = []int{1, 39, 2, 9, 7, 54, 11}

	var i = 1
	for i < len(n) - 1 {
		var j = i + 1
		var minIndex = i

		if j < len(n) {
			if n[j] < n[minIndex] {
				minIndex = j
			}
			j++
		}

		if minIndex != i {
			var temp = n[i]
			n[i] = n[minIndex]
			n[minIndex] = temp
		}

		i++
	}

	fmt.Println(n)
}
```

# Merge Sort <a name="merge-sort"></a>

Merge is a quite fast sorting algorithm. In a merge sort, you should utilize the divide-and-conquer practice. First, you'll divide the passed array by 2 recursively, until you reach the length of 1, then you should merge them. To merge two arrays that we know are already sorted themselves you can implement a simple function called merge.

![Merge sort](https://dev-to-uploads.s3.amazonaws.com/i/px7mavk10hfwi7bzq1xk.png)

```go
package main

import "fmt"

func merge(fp []int, sp []int) []int {
	var n = make([]int, len(fp)+len(sp))

	var fpIndex = 0
	var spIndex = 0

	var nIndex = 0

	for fpIndex < len(fp) && spIndex < len(sp) {
		if fp[fpIndex] < sp[spIndex] {
			n[nIndex] = fp[fpIndex]
			fpIndex++
		} else if sp[spIndex] < fp[fpIndex] {
			n[nIndex] = sp[spIndex]
			spIndex++
		}

		nIndex++
	}

	for fpIndex < len(fp) {
		n[nIndex] = fp[fpIndex]

		fpIndex++
		nIndex++
	}

	for spIndex < len(sp) {
		n[nIndex] = sp[spIndex]

		spIndex++
		nIndex++
	}

	return n
}

func mergeSort(arr []int) []int {
	if len(arr) == 1 {
		return arr
	}

	var fp = mergeSort(arr[0 : len(arr)/2])
	var sp = mergeSort(arr[len(arr)/2:])

	return merge(fp, sp)

}

func main() {
	var n = []int{1, 39, 2, 9, 7, 54, 11, 8}

	fmt.Println(mergeSort(n))
}
```

# Counting Sort <a name="counting-sort"></a>

Counting sort is a really simple yet complicated sorting algorithm. To understand how counting sort works you can watch the video below from GeekforGeeks:

{% youtube 7zuGmKfUt7s %}

Here is the Go code:
```go
package main

import "fmt"

func countSort(arr []int) []int {
	var max = arr[0]

	var i = 1
	for i < len(arr) {
		if arr[i] > max {
			max = arr[i]
		}

		i++
	}

	var indices = make([]int, max + 1)

	var j = 0
	for j < len(arr) {
		indices[arr[j]]++

		j++
	}

	var k = 1
	for k < len(indices) {
		indices[k] += indices[k - 1]

		k++
	}

	var result = make([]int, len(arr))

	var m = 0
	for m < len(arr) {
		result[indices[arr[m]] - 1] = arr[m]
		indices[arr[m]]--

		m++
	}

	return result
}

func main() {
	var n = []int{1, 39, 2, 9, 7, 54, 11}

	fmt.Println(countSort(n))
}

```

---
I will complete this list by time.

BTW! Check out my free Node.js Essentials E-book here:

{% link https://dev.to/adnanbabakan/nodejs-essentials-free-e-book-5319 %}