読者です 読者をやめる 読者になる 読者になる

No Programming, No Life

新しいNPNLです。http://d.hatena.ne.jp/fumokmm/ から引っ越してきました。

Groovyでスリープソートとバケットソートをやってみた

Groovy アルゴリズム ソート

はじめに

ちょっと前にスリープソートが流行ってたので、それをid:orangecloverさんが実装していたのを見て、id:nobeansさんがさらに添削していたものを参考に書いたコードが下のようになりました。

スリープソートって

スリープソートって、あるデータのもつ重みを時間単位に変換し(たとえば、[1, 2, 3] とかのデータだったら、[1秒, 2秒, 3秒] とか)、それぞれその時間だけ待機させたのちに値を集めて行くっていうアルゴリズムですよね。

これって今までにないソートアルゴリズムなのかな?と思ってちょっと調べてみると、概念として近いのはバケットソートですよね。

バケットソートって

Groovyで実装するとたぶんこんな感じ


Groovyのリストはインデックスがない場合は自動拡張されるのでそれを利用して、対応する値のindex位置にどんどん値を配置してゆきソートしています。

まとめ

スリープソートは時間というリソースを対価にソートを行っているのに対し、バケットソートはメモリ空間を対価にしてソートを行うわけですね。