スリープソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/22 09:14 UTC 版)
バケットソートのバケツをメモリ空間の代わりに時間に置き換えたもので、もともと掲示板4chanに投稿されたアイデアである。 「全要素の最大値×スリープさせる単位時間」で実際にソートできてしまう。それが役に立つ事例は例題程度であろう。 面白いジョークであるが、実際のコンピュータシステムでは、起動したプロセスが意図した時間にピタリと正確に終了するという保証はない。すなわち、非同期に複数プロセスを起動したとき、混雑やOSの制御のために値が返ってくる順序が意図した時刻にこないことがあるのはもちろん、ソートで期待する順序とは異なった順序で返ってくる恐れさえある。したがって、デモや冗談ならともかく、実用には絶対使ってはいけない。 OSは、実は一定時間後に起動する要求を到来時間順の待ち行列につないで管理している。そのとき当然到来時間の大小比較が行われる。タイマで見張り、時間の到来した要求を行列から外して要求元の待ちを解除し結果を通知しているのが実体である。ソートアルゴリズムに不可欠のこの“計算”のコストが計算量に算入されていないので、一見計算が要らないように見えるというトリックがある。時間順に並んだ「バケツ」を用意してデータを出し入れしてくれている“裏方さん”がいるのである。 bashによる実装 #!/bin/bashfunction f() { sleep "$1" echo "$1"}while [ -n "$1" ]do f "$1" & shiftdonewait 使用例: $ ./sleepsort.bash 5 3 6 3 6 3 1 4 7133345667 上の結果は正しい。 ところが処理系（Windows 10, Cygwin bash）で何度か実行しただけで、通常の数倍の時間経過したあと、たとえば以下のように一部追い抜きがあったり入力順そのままだったりと、誤った結果が出てくる例が見られた。 $ ./sleepsort.bash 5 3 6 3 6 3 1 4 7356336147
※この「スリープソート」の解説は、「バケットソート」の解説の一部です。
「スリープソート」を含む「バケットソート」の記事については、「バケットソート」の概要を参照ください。
- スリープソートのページへのリンク
