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]