実用性ゼロ！？でも発想だけは天才的な「sleep sort」

アルゴリズム

2011.05.31

はじめに
sleep sortとは？
1. 元ネタ（Bash実装）
2. HSPによるsleep sort実装
おわりに

はじめに

最近、「sleep sort(元ネタ)」という変わり種ソートアルゴリズムを知りました。これは一言でいえば「指定した値だけスリープしてから出力する」というだけの、発想がぶっ飛んでいるソートです。

元ネタは海外の掲示板4chanで紹介されたもので、Bashでの実装が有名です。実用性は……正直ゼロですが、「発想力って大事だなあ」と感心してしまうタイプのネタアルゴリズム。

せっかくなので、HSPでもSetTimerを使って実装してみましたが、掲示板でwait0000さんがすでに同じアイデアで作っていて、普通に被ってしまったので寝かせてました。

でも、5月は1度もブログ更新していなかったので、せっかくだし投稿します！

sleep sortとは？

sleep sortは、各値ごとに「スリープ時間」を設定し、値が小さいものほど早く出力されることを利用してソートを実現する“ジョーク的”なアルゴリズムです。

元ネタ（Bash実装）

#!/bin/bash

# Genius sorting algorithm: Sleep sort
# 1 Name: Anonymous : 2011-01-20 12:22
# Man, am I a genius. Check out this sorting algorithm I just invented.

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

実行すると、1, 3, 3, 3, 4, 5, 6, 6, 7の順に出力されます。
「sleep $1」でスリープした後にechoするので、小さい値ほど先に出力される…というアイデアです。

HSPによるsleep sort実装

HSPではSetTimerを使って、各値に対応したタイマーをセットしてみました。

#uselib "user32.dll"
#func SetTimer "SetTimer" int,int,int,sptr
#func KillTimer "KillTimer" int,int
#define WM_TIMER 0x0113
#define N 20

randomize
dim number, N
oncmd gosub *OnTimer,WM_TIMER
repeat N
	number = rnd(100) + 1
	SetTimer hwnd, number, number * 10, 0
loop
stop

*OnTimer
	KillTimer hwnd, wparam
	mes wparam
	return