基本的なソートアルゴリズムをGolangで実装してみた

2017/1/14 修正
intelf000さんのご指摘を受け、クイックソートについて、以下のバグを修正しました。
(合わせてsliceが参照渡しであることにも注意し、実装を改めています)

[内容]
a[left], a[right], pivotが同一の値となった場合に panic: runtime error: index out of range が発生。

背景

ソートアルゴリズムの話をするときに、自分の中で整理できていなかったので以下のアルゴリズムを実装してみました。

Goで書いたのは筋トレも兼ねているだけです。

そもそもGoにはsortパッケージ があります。
ちなみにリンク先を見て頂ければわかりますが、sortパッケージはクイックソートで実装されています。
(実体としては、データ長に応じて、ヒープソートと挿入ソートを併用する実装になっています)

ある程度ソート済みのアルゴリズムでは挿入ソートのほうが高速なのでソートしたいデータの特性によってはsortパッケージ以外を使用する選択肢もありそうです。

バブルソート

隣同士比較して交換するだけです.

gist95666e2ef1f45fece4b45fbafdff0f27

選択ソート

最小値(あるいは最大値)を「選択」し、小さい順に並べていくソートです。

gista224fb335644d3ca8567ec6aff87acb7

挿入ソート

整列済みのデータに対して、要素を正しい位置に挿入します。 整列済みであることを意識して、比較は後ろから行うようにしてみました。

連結リストで実装するのがよかったですね......。

gistfb4e64acc94d5b92a0227e898df99aa1

シェルソート

適当な間隔 h_iずつ空けて、グループを作り、グループ内でソートします。さらに間隔を狭めていき、間隔が1になったところで全体をソートします。

上記の過程である程度ソートされていき、最後は挿入ソートで締めます。

Knuth先生のThe Art of Computer Programmingによると以下を満たすよう間隔を選んでいくと O(n^{1.25})になるそうです。
(未読ですが......)

h_{i+1} = 3h_i + 1
h_0 = 1, h_i \in {\cal N}

giste344fbfc474b18e3e0f548dfaeb65ec8

マージソート

データを適当に分けていき、それをマージする際にソートします。

gist695d1274cca4314d1c755368ccd6abc0

クイックソート

一般なデータに対しては最も高速といわれているそうです。 ピボットより小さい値を持つグループと大きい値を持つグループにわけ、再帰的にソートしていきます。

ピボットの選び方によっては無限ループに入ってしまったり、計算量が増えてしまうので注意が必要です。

2017/1/14 訂正（詳細は記事冒頭に記載）

giste9999b007076c5c77f23b9188dc79598

ヒープソート

ヒープ木では根が最大(または最小)になるので、根を取り除き、残った部分をさらにヒープ木にすることを繰り返します。
こちらが大変参考になります。

UpHeapとDownHeapをまとめてヒープ木を作る関数にするのもありかと思ったのですが、それだと必要以上に計算が多くなるので微妙なんでしょうか。

gist71006d4ed430ae94e04dd6fe3c182ada

感想

全体的にGoの配列(slice)の操作に苦戦しました。 複数の値をまとめて代入できなかったり、配列を添え字で抜き出すところとか自分の想像する挙動と微妙に異なるので境界は特に気を遣いながら書きました。

上記以外にも様々なソートアルゴリズムがあるので実装していきたいです。 特にデータの特性に応じて、一定の条件下ではより高速になるようなソートはおもしろそうですね。

Reference