常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)

TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと

[gfx]

blogged

[tockri]

おお、すでになつかしい。僕が発明したショットガンソートじゃないか。しかもforとifを使わない分勝ったな（何に）

[wepon]

「幕末の頃、数では圧倒的に劣る維新志士が使った手段でな、まずはsleepするでござる。プロセスは当然追ってくるが、自然と速い者から順に追いついてくる事になる。そこでソートされるでござるよ」

[chinpeinet]

前に似たもん見たな。「ショットガンソート」で検索したら2007年に既にやってる人がいる。

[betelgeuse]

お前は5だから5秒待て！お前は1だから1秒待て！ｗｗｗ / 買い物行列の人々にロックつきのタイマーを１個づつ配るイメージ

[kmachu]

寝ている間にこびとさんが並び替えてくれるものぐさソートアルゴリズム。面白い。

[qnighy]

「ネタとしては面白いけど、こういうのはアルゴリズムとは言えない」とか言っている人はボゴソートを知らないんだろうか。アルゴリズムは仕様ではなくて手順なのは自明として、その手順が高速化に貢献する必要はない

[nitoyon]

コロンブスの卵なスリープソート。sleep "$1"; echo "$1" をパラレルに実行することでコンソールにはソートされた状態で出力される。実行時間は O(n)！（n は入力の最大値）…

[terazzo]

自分もバケツソートの亜種になるかと思った／実際にはプロセススケジューラのrunqueueの管理方法によるのか

[llill]

普遍化させると、超でかい配列にソート対象の値をindexとして取りつつ格納し、その先頭から参照するアプローチ(バケットソート?)...ってことでしょうか。そこで配列を時間軸上に取ることでほぼ無限の空間を確保、と。

[ite]

ネタとして面白がってたけど、冷静に考えてみると「極端な並列化を前提とすることで、ものすごく簡単になる問題が存在する」ということの良い例に思えてきた。他にも何かできそう。

[zetamatta]

すごい、sleep を使ったソートなど誰が思いつくだろうか！

[nwpct1]

ブクマ読んでやっと理解できた。これは天才

[girled]

最近、改めてソートアルゴリズムの勉強してんだけどその中で見つけたネタで案外面白かった。というか、自分でも真面目な顔してこれ作りそうな気がして変に同感してしまった。

[slash_01]

これはwww

[kimunny]

これで笑ったら疲れている証拠な

[kenomi]

O(n) のソート。素晴らしい。

[isaisstillalive]

この発想はなかった。天才すぎる

[kiyo_hiko]

このソートをほんのちょっぴりだが体験した、いや体験したというよりはまったく理解を超えていたのだが…『要素がその値分だけsleepしたと思ったらいつのまにかソートされていた』何を言ってるのかわからねーと思うが

[kireifish]

何いってるのかわからん

[kurumigi]

まあ、スケジューラに丸投げしているだけの話ではあるのだが面白い。／cf. http://tockri.blog78.fc2.com/blog-entry-44.html

[kenkitii]

天才かも

[hogem]

おもすれ

[yamashi_tam]

おおおおおおっ！！！

[mellow-mikan]

富豪的プログラミングすばらしい！

[tosebro]

楽しいな。こんな発想力がほしい。

[higedice]

この短いコードのアルゴリズムを理解できなくて2日前から落ち込んでいたけど今やっと理解しました。これは天才のなせる発想だな。教科書に載せないと。

[ww_zero]

実用性が無い点がステキ

[Show]

発想が斬新すぎる

[moimoi76]

単に時分割をバケットとみなしたバケットソートじゃん…イマイチ面白さがわかんない

[HISAMATSU]

おもしろい．

[usamyu56]

並列思考が出来ないオイラには思いつけないロジックorz

[wataboh2000]

常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream

[tomity]

ワラタｗ

[mystandard1979]

常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream

[takkaw]

色々条件付きだけど、少ないコードで動くのが斬新。

[t01353ak]

分かりやすさが凄いなぁ。

[ma_ko]

最適化で不覚にもﾌｲﾀがすげー発想だ。なんで思いついたんだろう?

[Arison]

寝ているときはソーっトしておいてあげよう。時間がかかるもんなんだよ。

[mzyg]

うひゃひゃ。

[t-tanaka]

その発想はなかったｗ。こんどMixiの課題丸投げコミュでつかお。