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

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

前回: Goでのアルゴリズムクイックリファレンス第2版(バケツソート)

今回はマージソート

基本的なアルゴリズムは、以下。(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)
}

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

• http://d.hatena.ne.jp/kankinkon/20120202/1328138584
• http://konbu13.hatenablog.com/entry/2014/02/11/195731

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

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