Data Structures & Algorithms In Go/

...

/

Insertion Sort

Insertion Sort

Let’s look at the insertion sort in detail.

We'll cover the following...

Introduction

Insertion sort is how we organize a deck of cards. We keep a sorted subarray. Each value is placed in the sorted subarray to the left of it in the proper position.

Let’s look at an illustration of the insertion to better understand how it works.

Code example

Press + to interact
package main
import ("fmt")
func InsertionSort(arr []int, comp func(int, int) bool) { 
  size := len(arr)
  var temp, i, j int
  for i = 1; i < size; i++ {
      temp = arr[i]
      for j = i; j > 0 && comp(arr[j-1], temp); j-- {
          arr[j] = arr[j-1]
      }
      arr[j] = temp
    }
}
func more(value1 int, value2 int) bool {
   return value1 > value2
}
//Testing Code
func main() {
  data := []int{9, 1, 8, 2, 7, 3, 6, 4, 5}
  InsertionSort(data, more)
  fmt.Println(data)
}

Analysis

  • The outer loop is used to choose the value to be inserted into the left-hand sorted array.

  • We choose the value we want to insert and save it in the temp variable.

  • The more() method is used in the inner loop to perform the comparison. The values are moved to the right until the correct place of the temp value for which this iteration is performed.

  • Finally, the value is assigned to the appropriate location. The length of the sorted array grows by one with ...