For a better understanding of this example, we always recommend you to learn the basic topics of Golang programming listed below:
Here we are explaining how to write a GO program to implement sort. There are different types of sorting methods. In this case, we use an insertion sort for sorting elements in an array. Insertion sort is a simple technique that was developed by using a comparison algorithm. It works just like arranging playing cards in your hands. Insertion sort is a more efficient and advanced algorithm than the merge sort, Heap sort, or Quicksort.
In this Go program, before sorting things, we must set a Starting Point, which helps to go consistently in one direction till we reach the end of the array. That means the array is first split into two sections sorted and unsorted sections. Initially, the sorted section contains only one element which is the first item of the main array and the rest of the items were considered as an un-sorted section. Take a leftmost element in an unsorted section to find a suitable position in the sorted section. Repeat this process until there is no element exist in the un-sorted subarray. Finally, each value from the unsorted section is inserted into the correct position of the sorted section.
In this GO program, we can use the built-in function fmt.println() to print anything and fmt.scanln() for reading the values and these methods are defined under the fmt package. In order to use these functions, we need to import the “fmt” package.
Here variable A holds the array elements. Other variables n is used as the size of the array. Use for loop to read array elements and perform sorting by calling function insertionSort().
The insertionSort() starts by iterating over the entire array elements in a nested for loop. That means as you can see, in this function, we need 2 for loops, Outer loop as well as inner loop.
The outer loop uses the loop variable j which helps to iterate over the array from left to right till the end of the array and selects a key which helps to go consistently in one direction till we reach the end of the array and compare the key to the left side on each iteration. Note that initially, we pick up the key from the second element (index 1) to save 1 iteration and have a left side to compare the key to.
Inside the inner loop, use the variable ‘i’ which helps to iterate backward over the elements on the left side. Here shift all the elements on the left side if they satisfy the sorting condition of the inner loop: i>-1 && A[i] > key, where the condition A[i]>key is used for ascending order.
On each key iteration of the outer loop, we insert the selected key into its correct position and repeat all this process till we loop over all the keys. Finally, the sorted array is returned to the main function which displays the sorted array as output.
Time Complexity:
Given below are the steps that are used in the Go program to implement Insertion Sort.
STEP 1: Import the packages 'fmt'.
STEP 2: Open the main() to start the program, GO program execution starts with the main().
STEP 3: Declare the variable n.
STEP 4: Read the size of the array as n.
STEP 5: Define the array A[].
STEP 6: Read the A[] array elements by using a 'for loop'.
STEP 7: Perform selection sort by calling function insertionSort (A, n)
STEP 8: Use for loop to display sorted array.
STEP 9: Exit
STEP 1: Initially set j=1
STEP 2: Open the outer loop by using for loop, which uses the j loop variable.
STEP 3: If the outer loop satisfies the j
STEP 4: Select a key by assigning A[j] to key to compare to the left side on each iteration?????
STEP 5: Set i := j - 1
STEP 6: Open the inner loop, which uses the 'i' variable.
STEP 7: if the inner loop satisfies the sorting condition: i>-1 && A[i] > key, then shift the element on the left side as A[i+1] = A[i]. Otherwise, Go to step 9.
STEP 8: Repeat step 7 by decrement the value of 'i' for iterates backward over the elements on the left side till the selected key reaches the beginning of the left side.
STEP 9: On each key iteration of the outer loop by increasing the value of j, we insert the selected key into its correct position as A[i+1] = key. Go to step 3
STEP 10: Return Sorted Array A.
package main
import (
"fmt"
)
func main() {
fmt.Println("Enter the size of the array")
var n int
fmt.Scan(&n)
A := make([]int, n, 100)
fmt.Println("Enter elements of the array : ")
for i := 0; i < n; i++ {
fmt.Scan(&A[i])
}
fmt.Println("Sorted array:")
fmt.Println(insertionSort (A, n))
}
func insertionSort(A []int, n int) []int {
for j := 1; j < n; j++ {
key := A[j]
i := j - 1
for i > -1 && A[i] > key {
A[i+1] = A[i]
i -= 1
}
A[i+1] = key
}
return A
}
Enter the size of the array 5 Enter elements of the array : 32 24 56 85 63 Sorted array: [24 32 56 63 85]
