Algorithm and Data Structures - Insertion Sort

Learn Insertion Sort, which divides the array into sorted and unsorted parts and builds the sorted sequence one element at a time. O(n²) time complexity with a Go implementation.

Read in: ja

Overview

Referencing the Algorithm Encyclopedia, we learn about algorithms and data structures.

The implementation is also available on github - bmf-san/road-to-algorithm-master.

Insertion Sort

Sorts sequentially from the beginning of the data series
Divides into sorted and unsorted subsequences
- 1st pass: Treat the 0th element as sorted, do nothing
- 2nd pass: Compare the 0th and 1st elements, swap if in reverse order
- 3rd pass: Compare with the data series from 0th to 1st, swap if necessary
- 4th pass: Compare with the data series from 0th to 2nd, swap if necessary
- Repeat until there are no unsorted parts

Time Complexity

O(n²)

Implementation

package main

import "fmt"

func insertionSort(n []int) []int {
	for i := 1; i < len(n); i++ {
		for j := 0; j < i; j++ {
			if n[i-j-1] > n[i-j] {
				n[i-j-1], n[i-j] = n[i-j], n[i-j-1]
			} else {
				break
			}
		}
	}

	return n
}

func main() {
	n := []int{2, 1, 5, 7, 9}
	fmt.Println(insertionSort(n))
}