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

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

基本的なアルゴリズムは、以下。(wikipediaより)

1. データ列を分割する（通常、等分する）
2. 各々をソートする
3. 二つのソートされたデータ列をマージする

package main

import (
    "fmt"
    "math/rand"
)

func mergeSort(a *[]int, tmp *[]int, start int, end int) {
    m := (end + start) / 2
    if end <= start {
        return
    }
    mergeSort(a, tmp, start, m)
    mergeSort(a, tmp, m+1, end)
    merge(a, tmp, start, m, end)
}

func merge(a *[]int, tmp *[]int, start int, m int, end int) {
    var start_i, end_i int
    for start_i = m + 1; start_i > start; start_i-- {
        (*tmp)[start_i-1] = (*a)[start_i-1]
    }

    for end_i = m; end_i < end; end_i++ {
        (*tmp)[end+m-end_i] = (*a)[end_i+1]
    }

    for i := start; i <= end; i++ {
        if (*tmp)[end_i] < (*tmp)[start_i] {
            (*a)[i] = (*tmp)[end_i]
            end_i--
        } else {
            (*a)[i] = (*tmp)[start_i]
            start_i++
        }
    }
}

func main() {
    var ary, tmp []int
    size := 30
    for i := 0; i < size; i++ {
        ary = append(ary, rand.Intn(size-1))
        tmp = append(tmp, 0)
    }
    fmt.Println(ary)
    mergeSort(&ary, &tmp, 0, len(ary)-1)
    fmt.Println(ary)
}

今回はしょうも無いところで色々はまって、考え違いしてるのかと思って色々参考にさせていただきました。再帰じゃないバージョンのマージソートも考察されているようで、これもあとでもう一度トライしたいです。

あと、途中で見つけたこの本結構良さそうなので後で購入したいです。

次回は逐次探索の予定です。