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

次回は選択ソートの予定