Golang program for implementation of Insertion Sort
The idea of swapping adjacent elements to sort a list of items can also be used to implement the insertion sort. In the insertion sort algorithm, we assume that a certain portion of the list has already been sorted, while the other portion remains unsorted. With this assumption, we move through the unsorted portion of the list, picking one element at a time. With this element, we go through the sorted portion of the list and insert it in the right order so that the sorted portion of the list remains sorted.
Example
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
slice := generateSlice(20)
fmt.Println("\n--- Unsorted --- \n\n", slice)
insertionsort(slice)
fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
slice := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}
func insertionsort(items []int) {
var n = len(items)
for i := 1; i < n; i++ {
j := i
for j > 0 {
if items[j-1] > items[j] {
items[j-1], items[j] = items[j], items[j-1]
}
j = j - 1
}
}
}
Output
--- Unsorted ---
[503 -319 245 -537 -167 -804 469 -457 143 184 376 825 11 -309 -144 152 -493 684 165 29]
--- Sorted ---
[-804 -537 -493 -457 -319 -309 -167 -144 11 29 143 152 165 184 245 376 469 503 684 825]