時間の概念を活用した全く新しいソートアルゴリズム「Sleep sort」

アルゴリズムの代表例として取り上げることの多い「ソートアルゴリズム」。

多種多様な整列方法が考案され、もはや新しいアイデアも出尽くしたかに思われていたこのアルゴリズムに「sleep」を活用した全く新しい整列方法、通称「Sleep sort」が提案されていたことが判明し(実は2011年に発表されていました)、今また話題となっています(Reddit、Hacker News)。

実行例

Sleep sort実装例は以下の通り。シェルスクリプト製です。

function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

これをsleepsort.shとして保存し「./sleepsort.sh 5 3 6 3 6 3 1 4 7」と実行すると、以下のような結果が表示されます。

ランダムに与えた数値の引数が順番に表示されました。

画像では分かりませんが、1は1秒後に、3は3つ同時に3秒後に表示され、以下数値の秒数が経過するとともに結果が表示されていき、7秒後に7が表示されて終わります。

どういうこと？

勘の良い方はすでにお分かりかもしれません。「f()」の処理を「f "$1" &」と呼び出すことでバックグラウンドに回して並列に実行し、それぞれ指定秒数スリープさせた後にechoさせることで、数値のソートを実現しています。

最後のwaitは全部の処理が終了するのを待ち合わせるのに必要となります。シェルのマルチスレッド風処理に関しては、ここなどが参考になるかもしれません。

4chanでつっこまれている通り、数字に218382のような大きい数が含まれていると、最低218382秒かかってしまうため、実用的とはいえないかもしれません。しかしソートに時間の概念を取り入れる発想の柔軟性が素晴らしく、Redditでは他にも実用的ではないけどおもしろいソート方法がないか議論となっています。興味のある方は参照してみてください。