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

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

この記事を読むのに必要な時間:およそ 0.5 分

ソートアルゴリズムにはクイックソートやマージソートといった伝統的なものから,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

著者プロフィール

角田直行(かくだなおゆき)

普段はお仕事でPHPやJavaを使ってWeb開発をしています。一部でセレブエンジニアとか言われてますが,全然セレブじゃありません。

コメント

コメントの記入