濃縮還元オレンジニュース

画期的(?)ソートアルゴリズム「Sleep Sort」

ソートアルゴリズムにはクイックソートやマージソートといった伝統的なものから、PythonやJava 7のデフォルト実装になっているTimsortまでいろいろな種類があります。中には正しいソート順になるまでひたすらシャッフルし続ける「Bogosort」のようなジョークアルゴリズムもあります。これから紹介するアルゴリズムもそのうちの一つに入るかもしれません。

4chanという2ちゃんねるに似たアメリカの匿名掲示板があり、そのプログラミング板にて「Genius sorting algorithm: Sleep sort」というスレッドが立ちました。2ちゃんねる風に訳すと「ちょwwwすごいソートアルゴリズム思いついたwwwww」といった感じでしょうか。スレッドを立てた1氏は「Sleep Sort」と称したリスト2のようなシェルスクリプト実装を載せています。

ソート対象の数値データを次々にsleepコマンドに渡し、sleepが終わった順に出力すると結果がソートされている、というしくみです。難点は数値しか扱えないことと、2つの数値「1 1000」を渡すと処理に1,000秒かかってしまうことです。あまり実用的ではないものの発想の画期的さ、実装の容易さから瞬く間にいろいろな言語による実装が出てきました。FizzBuzzのようにプログラミング初心者向けの課題として適しているかもしれません。

ちなみに、日本人で2007年に同様のアプローチで「ショットガンソート」と名付けて実装した方がいます

リスト2 Sleep Sortのコード
#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

URLhttp://d.hatena.ne.jp/gfx/20110519/1305810786

おすすめ記事

記事・ニュース一覧