Go遊会 ５日目

今日のテーマ：ヒープソート

バイナリヒープを使ったソーティングを実装した。 実装アプローチとしては、配列で領域を確保して添字演算で二分木構造を実現する一般的なもの。

アルゴリズム自体大して難しくないし、過去に何回か書いたことがあるのでさくっとできると思っていたけど、Goのstructとメソッド定義の方法やらポインタの扱い、スライスの拡張方法などを調べたりするのと、upheapとdownheapの手続きをごちゃごちゃ書くのに手間取って30分弱かかった。

文法のケアレスミスのコンパイルエラーを取り除くと、そのままスルっと動作した。よしよし。

明日のテーマ：基数ソート

Go言語の線形リストの扱いをおさらいしながらバケットソートを実装して、その上で基数ソートを実装する。 基数ソートは理屈は理解しているけど、実は今まで実装したことが無い気がする。

ソーティングアルゴリズムを一通りやりおわったら、goroutineを使った並列化の練習として、ソーティングを並列化していくのもよいかもしれない。