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

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

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

今回はバケツソート

• 整列したいデータの取り得る値がm種類であるとき

• m個のバケツを用意しておき

• 値毎に1個のバケツを対応づける

• 元のデータ列を捜査して

• 各データに対応するバケツに入れておく

• この処理が終わった後

• 整列したい順序にしたがってバケツから値を取り出せば

• データをソートすることができる

• 成立する性質

  • 一様分布
  • 順序のついたハッシュ関数

package main

import "fmt"

const BUCKETS = 10

func bucketSort(a *[]int, size int) {
	var i, j, k int
	buckets := make([]int, BUCKETS)
	for j = 0; j < BUCKETS; j++ {
		buckets[j] = 0
	}
	for i = 0; i < size; i++ {
		buckets[(*a)[i]]++
	}
	i = 0
	for j = 0; j < BUCKETS; j++ {
		for k = buckets[j]; k > 0; k-- {
			(*a)[i] = j
			i++
		}
	}
}

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

実装しつつ、改めて考えてなるほど確かにこれは最初の条件に従う時にしかできないソートですね。なんか、クイックリファレンスが次のアルゴリズムを決めるベースになってしまっている。今回は入門データ構造とアルゴリズムのやり方がコンパクトだったのでそちらでやってしまった。hash関数を作る方法であとでもう一度tryしたい。

次回はマージソートの予定です。