Goでのアルゴリズムクイックリファレンス第2版(4.1.1 挿入ソート)

Goに慣れるためとアルゴリズムの復習の為に週1ぐらいで更新していきます。アルゴリズムクイックリファレンス 第2版を読んで各種アルゴリズムをGoで実装して行きます。

今回は挿入ソートです。整列アルゴリズムの一種。平均(O(n2))と遅い処理。安定しているソート。追加の記憶領域を殆ど使わないin-placeアルゴリズムでありオンラインアルゴリズムでもあるようだ。(この2種類の仕分けは改めて確認していたらしれたので良かった)

package main

import "fmt"

func sort(ary *[]int) {
	for pos := 1; pos < len(*ary); pos++ {
		insert(ary, pos, (*ary)[pos])
	}
}

func insert(ary *[]int, pos int, value int) {
	i := pos - 1
	for i >= 0 && (*ary)[i] > value {
		(*ary)[i+1] = (*ary)[i]
		i = i - 1
	}
	(*ary)[i+1] = value
}

func main() {
	ary := []int{3, 2, 1, 5, 10, 7, 9}
	fmt.Println(ary)
	sort(&ary)
	fmt.Println(ary)
}

次回は選択ソートの予定