Insertion Sort In Golang

Insertion sort is very important and useful algorithm, in this post we are going to implement insertion sort using Golang. for sorting small number of array its good to use insertion sort. 

In insertion sort, we can sort one item at a time, like playing card, when we get card , we pick one card from unsorted card and put into the sorted list.

Above graph show how the sorting happend, as we see we pick one number from right and compare with other numbers in its left and swap the index one by one in sorted order to sort the array.

Same scenario we can see in above image as well.

Let work on our algorithm based on above image:

• Step 1. Iterate from arr[index] to arr[n-index], where index start from 0.
  
• Step 2. Compare the current index(indx) with its predecessor number (0, index-1)
• Step 3. If current index or ( arr[index] ) is smaller than any predecessor index like ( arr[index-1], arr[index-2], arr[index-3]... ), in that case we shift number from arr[indx-i] to its specific place.
  

Lets convert the above logic in our favorite programming language:

Go Program:

 
package main

import "fmt"

//bubblesort
func insertionSort(arr []int) []int {
	var temp int
	for indx := 0; indx < len(arr); indx++ {
		temp = arr[indx]
		curentIndex := indx
		for j := indx - 1; j >= 0; j-- {
			if temp < arr[j] {
				arr[curentIndex] = arr[j]
				curentIndex--
			}
		}
		if curentIndex >= 0 {
			arr[curentIndex] = temp
		}
	}
	return arr
}

func main() {
	arr := []int{10, 1, 99, 0, 0, 0, 1}
	fmt.Println("Before Sorting: ", arr)
	insertionSort(arr) // used to sort the list
	fmt.Println("After Sorting:", arr)
}

In above code snippet, as per our algorithm we implemented our insertionsort function, we are going one by one index and compare this with its smaller index and if we found any index is greater than the index which we are checking in that case we replace that number index with compare one.

Insertion sort time complexity:

Best : O(n)

Average: O(n^2)

Worst: O(n^2)

We are going to implement,all golang sort algorithm, Please check our other post for Bubble sort, selection sort, quick sort and merge sort.

Give your valuable suggestion in comment box.