Algorithms: 4. Insertion Sort

Algorithms: 4. Insertion Sort

Mar 19, 2022
programming, golang, algorithms, generics

Introduction #

Another way of sorting an array is by using the insertion sort method. In this case we start at position 1 in the array1. We then set j = i, or in this case, 1. We then compare array[j - 1] with array[j], i.e. array[0] and array[1]. If array[0] is greater than array[1], we swap them. Then we subtract 1 from j and if j is greater than zero, we do the next j, other we break and do the next i. In one sense this is very similar to the bubble sort, but we do not have to loop through the entire array each time, just part of it, which makes this faster and more efficient than the bubble sort. Let’s look at the code.

Solution # 

package main

import (
    "flag"
    "fmt"
    "math/rand"
    "golang.org/x/exp/constraints"
)

func insertionSort[T constraints.Ordered](array []T) []T {

    var n = len(array)

    for i := 1; i < n; i++ {
        j := i

        for j > 0 {
            if array[j-1] > array[j] {
                array[j], array[j-1] = array[j-1], array[j]
            }

            j = j - 1
        }
    }

    return array
}

func randomString(n int) string {

    var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

    s := make([]rune, n)

    for i := range s {
        s[i] = letters[rand.Intn(len(letters))]
    }

    return string(s)
}

func main() { main redeclared in this block

    var size int
    var intArray []int64
    var floatArray []float64
    var stringArray []string

    // Define the flags and their default values
    flag.IntVar(&size, "size", 100, "The size of the array")
    flag.Parse()

    // Load the input array
    for i := 1; i <= size; i++ {
        intArray = append(intArray, rand.Int63n(1000))
    }

    // Output
    fmt.Printf("Before Sorting : %v\n", intArray)
    fmt.Printf("After Sorting  : %v\n", insertionSort(intArray))

    // Load the input array
    for i := 1; i <= size; i++ {
        floatArray = append(floatArray, float64(rand.Int63n(1000)) / 10)
    }

    // Output
    fmt.Printf("---")
    fmt.Printf("Before Sorting : %v\n", floatArray)
    fmt.Printf("After Sorting  : %v\n", insertionSort(floatArray))

    // Load the input array
    for i := 1; i <= size; i++ {
        stringArray = append(stringArray, randomString(5)))
    }

    // Output
    fmt.Printf("---")
    fmt.Printf("Before Sorting : %v\n", stringArray)
    fmt.Printf("After Sorting  : %v\n", insertionSort(stringArray))
}

Testing #

Now we run go build and test the program

  • Show the usage
./insertionsort --help
Usage of ./insertionsort:
  -size int
        The size of the array (default 100)
  • Run the program with the default values
./insertionsort
Before Sorting : [410 551 821 51 937 320 758 148 216 449 84 287 574 836 515 873 968 91 790 331 273 956 911 637 378 109 72 650 588 971 344 443 623 459 803 739 883 907 932 780 115 716 20 71 652 907 719 62 110 397 105 721 917 712 449 579 333 825 746 734 718 901 704 610 24 717 269 479 269 750 657 923 512 702 655 257 643 301 19 18 694 41 788 21 911 280 343 55 41 453 631 217 631 218 632 514 904 180 500 71]
After Sorting  : [18 19 20 21 24 41 41 51 55 62 71 71 72 84 91 105 109 110 115 148 180 216 217 218 257 269 269 273 280 287 301 320 331 333 343 344 378 397 410 443 449 449 453 459 479 500 512 514 515 551 574 579 588 610 623 631 631 632 637 643 650 652 655 657 694 702 704 712 716 717 718 719 721 734 739 746 750 758 780 788 790 803 821 825 836 873 883 901 904 907 907 911 911 917 923 932 937 956 968 971]
---
Before Sorting : [38.5 82.3 44.1 80.5 25.8 76.5 86.8 8.3 85 37.9 81.2 11.3 57.1 42.2 12.3 18.9 36.4 58.7 63.7 39.9 62.9 24.4 75.2 52.9 82.2 59.9 78.8 51.4 70.6 79.6 61.1 94.3 51.1 78.8 52.9 90 43.8 80.8 55.9 33.5 15.8 90.2 3.9 14.7 39.7 52.9 17.6 33.8 53 7.5 74.1 44.9 95.1 30.4 22.1 57.4 43.9 50 41.2 98.9 66.6 43.6 86.7 70.1 79.3 88.4 75.9 67.9 73.6 37.5 68.7 49.7 4.4 36.5 91.5 41 24.4 24.7 84 42.8 78.6 23.6 80.7 98.9 70 21.8 75.8 91.2 89.7 74.9 65.6 65 14 15 18.2 8 21.3 45 5.6 24]
After Sorting  : [3.9 4.4 5.6 7.5 8 8.3 11.3 12.3 14 14.7 15 15.8 17.6 18.2 18.9 21.3 21.8 22.1 23.6 24 24.4 24.4 24.7 25.8 30.4 33.5 33.8 36.4 36.5 37.5 37.9 38.5 39.7 39.9 41 41.2 42.2 42.8 43.6 43.8 43.9 44.1 44.9 45 49.7 50 51.1 51.4 52.9 52.9 52.9 53 55.9 57.1 57.4 58.7 59.9 61.1 62.9 63.7 65 65.6 66.6 67.9 68.7 70 70.1 70.6 73.6 74.1 74.9 75.2 75.8 75.9 76.5 78.6 78.8 78.8 79.3 79.6 80.5 80.7 80.8 81.2 82.2 82.3 84 85 86.7 86.8 88.4 89.7 90 90.2 91.2 91.5 94.3 95.1 98.9 98.9]
---
Before Sorting : [LOpbU OpEdK updOM eRVja RzLNT XYeUC WKsXb GyRAO mBTvK SJfjz aLbtZ syMGe uDtRz QMDQi YCOhg HOvgS eycJP JHYNu fNjJh hjUVR uSqfg qVMkP YVkUR UpiFv IZRgB myArK Ctzkj kZIva BjMkX VbWGv bqzge xyALB sdjSG pngCw FkDif IBuuf FMoWd iTskZ oQJMq rTICT ojIYx yeSxZ yfroR ODMbN DRZnP NRWCJ PMHDt JmHAY ORsUf UMAps VgzHb lmYYt EjVgw fFbbG Gcnqb aEREu nUZjQ XmZOt aRLUt mYgmS VYBAD DvoxI fsfgP yCKmx IubeY TNDtj AyRRD edMiy Lpruc jiOgj hYeVw BTCML frDGX qwpzw VGqMZ cLVCx aSJlD SYEof kkEYe qkKHq gBpnb PbgHM LUIDj UMmpB HCSjM Jjxzu aiIsN BakqS wQpOQ gNczg aczAI nLqLI bAatL YHdao povFO kqIex sFzXz rlczt xcdJJ FuyZH]
After Sorting  : [AyRRD BTCML BakqS BjMkX Ctzkj DRZnP DvoxI EjVgw FMoWd FkDif FuyZH Gcnqb GyRAO HCSjM HOvgS IBuuf IZRgB IubeY JHYNu Jjxzu JmHAY LOpbU LUIDj Lpruc NRWCJ ODMbN ORsUf OpEdK PMHDt PbgHM QMDQi RzLNT SJfjz SYEof TNDtj UMAps UMmpB UpiFv VGqMZ VYBAD VbWGv VgzHb WKsXb XYeUC XmZOt YCOhg YHdao YVkUR aEREu aLbtZ aRLUt aSJlD aczAI aiIsN bAatL bqzge cLVCx eRVja edMiy eycJP fFbbG fNjJh frDGX fsfgP gBpnb gNczg hYeVw hjUVR iTskZ jiOgj kZIva kkEYe kqIex lmYYt mBTvK mYgmS myArK nLqLI nUZjQ oQJMq ojIYx pngCw povFO qVMkP qkKHq qwpzw rTICT rlczt sFzXz sdjSG syMGe uDtRz uSqfg updOM wQpOQ xcdJJ xyALB yCKmx yeSxZ yfroR]
  • Run the program and test the size parameter
./insertionsort --size=10
Before Sorting : [410 551 821 51 937 320 758 148 216 449]
After Sorting  : [51 148 216 320 410 449 551 758 821 937]
---
Before Sorting : [8.4 28.7 57.4 83.6 51.5 87.3 96.8 9.1 79 33.1]
After Sorting  : [8.4 9.1 28.7 33.1 51.5 57.4 79 83.6 87.3 96.8]
---
Before Sorting : [tcuAx hxKQF DaFpL SjFbc XoEFf RsWxP LDnJO bCsNV lgTeM aPEZQ]
After Sorting  : [DaFpL LDnJO RsWxP SjFbc XoEFf aPEZQ bCsNV hxKQF lgTeM tcuAx]
  • Run the program with an invalid value for the size
./insertionsort -size -1.0
invalid value "-1.0" for flag -size: parse error
Usage of ./insertionsort:
  -size int
        The size of the array (default 100)
  • Run the program with an invalid flag
./insertionsort --sized 10
flag provided but not defined: -sized
Usage of ./insertionsort:
  -size int
        The size of the array (default 100)

  1. Remember arrays in go start from 0, i.e. array[0] is the first element. ↩︎