Golang Insertion Sort Algorithm

Insertion sort is an algorithm that creates a final sorted array one element at a time. The algorithm's performance is of the order O(n2). This algorithm is less efficient on large collections than other algorithms, such as quick, heap, and merge sort.

In real life, a good example of insertion sort is the way cards are manually sorted by the players in a game of bridge.

Golang Insertion Sort Algorithm Implementation

The implementation of the insertion sort algorithm is shown in the following code snippet.

Let's create a file named "insertion_sort.go" and add the following source code to it:


package main

// importing fmt and bytes package
import (
	"fmt"
	"math/rand"
	"time"
)

// randomSequence method
func randomSequence(num int) []int {

	var sequence []int
	sequence = make([]int, num, num)
	rand.Seed(time.Now().UnixNano())
	var i int
	for i = 0; i < num; i++ {
		sequence[i] = rand.Intn(999) - rand.Intn(999)
	}
	return sequence
}

//InsertionSorter method
func InsertionSorter(elements []int) {
	var n = len(elements)
	var i int

	for i = 1; i < n; i++ {
		var j int
		j = i
		for j > 0 {
			if elements[j-1] > elements[j] {
				elements[j-1], elements[j] = elements[j], elements[j-1]
			}
			j = j - 1
		}
	}
}

//main method
func main() {

	var elements []int
	elements = []int{11, 4, 18, 6, 19, 21, 71, 13, 15, 2}
	fmt.Println("\n ====== Before Sorting ======= \n\n", elements )
	InsertionSorter(elements )
	fmt.Println("\n--- After Sorting ---\n\n", elements , "\n")
}

Run the following command to execute the insertion_sort.go file:

G:\GoLang\examples>go run insertion_sort.go
 ====== Before Sorting ======= 

 [11 4 18 6 19 21 71 13 15 2]

--- After Sorting ---

 [2 4 6 11 13 15 18 19 21 71]