Go – Insertion Sort

In this tutorial, we will learn how to implement the Insertion Sort algorithm using the Go programming language (Golang).

Insertion Sort is a simple and efficient sorting algorithm for small datasets. It works by building a sorted section of the list one element at a time. We will provide a step-by-step explanation and example program to understand and implement Insertion Sort.

Logic of Insertion Sort

The Insertion Sort algorithm involves the following steps:

  1. Iterate Through the List: Start with the second element (as the first element is considered sorted).
  2. Compare and Insert: Compare the current element with elements in the sorted section of the list. Shift larger elements to the right and insert the current element into its correct position.
  3. Repeat: Continue this process for all elements in the list.
  4. Result: After all iterations, the list will be sorted in ascending order.

Insertion Sort has a time complexity of \( O(n^2) \) in the worst case but performs better for nearly sorted datasets.

Example Program for Insertion Sort

Program – insertion_sort.go

</>
Copy
package main

import "fmt"

// Function to implement Insertion Sort
func insertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        key := arr[i]
        j := i - 1

        // Move elements of arr[0..i-1] that are greater than key
        // to one position ahead of their current position
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

func main() {
    // Input array
    arr := []int{64, 34, 25, 12, 22, 11, 90}

    // Display the original array
    fmt.Println("Original array:", arr)

    // Sort the array using Insertion Sort
    insertionSort(arr)

    // Display the sorted array
    fmt.Println("Sorted array:", arr)
}

Explanation of Program

  1. Function Definition: The insertionSort function accepts a slice of integers and sorts it in ascending order using the Insertion Sort algorithm.
  2. Outer Loop: The outer loop starts from the second element (index 1) and iterates through the list.
  3. Key Element: The key variable stores the current element to be inserted into the sorted section.
  4. Inner Loop: The inner loop compares the key with elements in the sorted section. Larger elements are shifted to the right to make space for the key.
  5. Insert Key: After shifting elements, the key is inserted into its correct position.
  6. Display Results: The original and sorted arrays are printed to the console using fmt.Println.

Output

This program demonstrates the Insertion Sort algorithm, which iteratively builds a sorted list by inserting elements into their correct positions.