Edited at

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

More than 1 year has passed since last update.

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

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

https://play.golang.org/p/R8RFUjfwkm


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)
}

次回は選択ソートの予定