Golang React JS Technology Blog

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]
Most Helpful This Week
Golang program for implementation of Floyd–Warshall Algorithm Golang program for implementation of Merge Sort Golang program for implementation of ZigZag Matrix Golang program for implementation of Rabin-Karp Golang program to implement Binary Tree Golang program for implementation of Interpolation Search