スリープソート

「スリープソート」は、実際にはあまり使われていないが興味深い奇妙なアルゴリズムである。
ソートに使いたいメトリックに比例する時間だけ待ち、その後自分自身をリストに挿入していく。値の比較をまったく伴わないアルゴリズム。
スリープソートには大きな欠点がいくつかある。そのうちの３つは、負の数字を扱えないこと、スリープソートの実行時間がリスト内の最大値ｘ秒数かかること、全要素のスレッドが完全な同時並列で実行されない場合、近い数字同士が間違った順番でリストに挿入される可能性がある。

Pythonプログラム例：

#スリープソートプログラム例
import threading #threadingモジュールを使用して、同時に複数のタスクを実行
from time import sleep

def sleep_sort(i):
sleep(i)
global sortedlist
sortedlist.append(i)
return(i)

items = list(map(int, input(“ソートしたい数字列(0以上の数)を半角でスペースで区切って記載してください。結果が出るまで最大値 x 秒数かかります。　”).split()))
# 4 1 3 2 6 3 10 2 9 7 3 1 2 5 ← 入力例
sortedlist =[]
ignore_rusult = [threading.Thread(target = sleep_sort, args = (i,)).start()for i in items]

sleep(max(items)+1)
print(“ソートした数字列　”,sortedlist) #結果出力

かります。　”).split()))

# 4 1 3 2 6 3 10 2 9 7 3 1 2 5 ← 入力例

print(“ソートした数字列　”,sleep_sort(array)) #スリープソート実施、結果出力

 

参考とした書籍
署名：アルゴリズムをめぐる冒険–勇敢な初学者のためのPythonアドベンチャー
著者：Bradford Tuckfield
訳者：竹川文則、川上悦子、高柳愼一
発行所：共立出版(株)

以上