シェルソート

• 挿入ソートを「大雑把にやる」ことを繰り返すことで全体を整列させていくのがシェルソート
  • 「widthごとに挿入ソートをする」を繰り返す
• 「シェル」は人名

func ShellSort(target []int) []int {
	n := len(target)
	width := 1
	for width < n {
		width = 3*width + 1
	}
	for width > 1 {
		width /= 3
		log.Printf("---- width: %d ----\n", width)
		for i := width + 1; i < n; i++ {
			v := target[i]
			j := i - width
			for v < target[j] {
				log.Printf("%v\n", target)
				target[j+width] = target[j]
				j -= width
				if j < 0 {
					break
				}
			}
			target[j+width] = v
		}
	}
	return target
}

2019/06/14 13:07:37 Target: [0 7 5 6 3 10 1 8 2 4 11 9]
2019/06/14 13:07:37 ---- width: 4 ----
[0 7 5 6 3 10 1 8 2 4 11 9]
[0 7 1 6 3 10 5 8 2 4 11 9]
[0 7 1 6 2 10 5 8 3 4 11 9]
[0 7 1 6 2 10 5 8 3 10 11 9]
2019/06/14 13:07:37 ---- width: 1 ----
[0 4 1 6 2 7 5 8 3 10 11 9]
[0 1 4 6 2 7 5 8 3 10 11 9]
[0 1 4 6 6 7 5 8 3 10 11 9]
[0 1 2 4 6 7 5 8 3 10 11 9]
[0 1 2 4 6 7 7 8 3 10 11 9]
[0 1 2 4 5 6 7 8 3 10 11 9]
[0 1 2 4 5 6 7 8 8 10 11 9]
[0 1 2 4 5 6 7 7 8 10 11 9]
[0 1 2 4 5 6 6 7 8 10 11 9]
[0 1 2 4 5 5 6 7 8 10 11 9]
[0 1 2 3 4 5 6 7 8 10 11 9]
[0 1 2 3 4 5 6 7 8 10 11 11]
2019/06/14 13:07:37 Sorted: [0 1 2 3 4 5 6 7 8 9 10 11]