挿入ソート

• 「最小値を決める」ことを繰り返してソートするのではなくて，**「この値が入るべき場所はどこなのかを決める」**ことを繰り返してソートする
• ほとんどデータが整列済みの時に使える
• トランプを順番に並び変えるときに自然にやる動作が挿入ソート

func InsertionSort(target []int) []int {
	target = append([]int{-1}, target...)
	for i := 2; i < len(target); i++ {
		log.Printf("\t---- i = %d ----\n", i)
		sentinel := target[i]
		target[0] = sentinel
		j := i - 1
		for sentinel < target[j] {
			target[j+1] = target[j]
			log.Printf("[%d %v]\n", target[0], target[1:])
			j -= 1
		}
		target[j+1] = sentinel
		log.Printf("[%d %v]\n", target[0], target[1:])
	}
	return target[1:]
}

2019/06/13 23:44:36 Target: []int{7, 1, 4, 2, 0, 8, 5, 9, 3, 6}
2019/06/13 23:44:36     ---- i = 2 ----
2019/06/13 23:44:36 [1 [7 7 4 2 0 8 5 9 3 6]]
2019/06/13 23:44:36 [1 [1 7 4 2 0 8 5 9 3 6]]
2019/06/13 23:44:36     ---- i = 3 ----
2019/06/13 23:44:36 [4 [1 7 7 2 0 8 5 9 3 6]]
2019/06/13 23:44:36 [4 [1 4 7 2 0 8 5 9 3 6]]
2019/06/13 23:44:36     ---- i = 4 ----
2019/06/13 23:44:36 [2 [1 4 7 7 0 8 5 9 3 6]]
2019/06/13 23:44:36 [2 [1 4 4 7 0 8 5 9 3 6]]
2019/06/13 23:44:36 [2 [1 2 4 7 0 8 5 9 3 6]]
2019/06/13 23:44:36     ---- i = 5 ----
2019/06/13 23:44:36 [0 [1 2 4 7 7 8 5 9 3 6]]
2019/06/13 23:44:36 [0 [1 2 4 4 7 8 5 9 3 6]]
2019/06/13 23:44:36 [0 [1 2 2 4 7 8 5 9 3 6]]
2019/06/13 23:44:36 [0 [1 1 2 4 7 8 5 9 3 6]]
2019/06/13 23:44:36 [0 [0 1 2 4 7 8 5 9 3 6]]
2019/06/13 23:44:36     ---- i = 6 ----
2019/06/13 23:44:36 [8 [0 1 2 4 7 8 5 9 3 6]]
2019/06/13 23:44:36     ---- i = 7 ----
2019/06/13 23:44:36 [5 [0 1 2 4 7 8 8 9 3 6]]
2019/06/13 23:44:36 [5 [0 1 2 4 7 7 8 9 3 6]]
2019/06/13 23:44:36 [5 [0 1 2 4 5 7 8 9 3 6]]
2019/06/13 23:44:36     ---- i = 8 ----
2019/06/13 23:44:36 [9 [0 1 2 4 5 7 8 9 3 6]]
2019/06/13 23:44:36     ---- i = 9 ----
2019/06/13 23:44:36 [3 [0 1 2 4 5 7 8 9 9 6]]
2019/06/13 23:44:36 [3 [0 1 2 4 5 7 8 8 9 6]]
2019/06/13 23:44:36 [3 [0 1 2 4 5 7 7 8 9 6]]
2019/06/13 23:44:36 [3 [0 1 2 4 5 5 7 8 9 6]]
2019/06/13 23:44:36 [3 [0 1 2 4 4 5 7 8 9 6]]
2019/06/13 23:44:36 [3 [0 1 2 3 4 5 7 8 9 6]]
2019/06/13 23:44:36     ---- i = 10 ----
2019/06/13 23:44:36 [6 [0 1 2 3 4 5 7 8 9 9]]
2019/06/13 23:44:36 [6 [0 1 2 3 4 5 7 8 8 9]]
2019/06/13 23:44:36 [6 [0 1 2 3 4 5 7 7 8 9]]
2019/06/13 23:44:36 [6 [0 1 2 3 4 5 6 7 8 9]]
2019/06/13 23:44:36 Sorted: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}