【変なソートアルゴリズム】ビーズを落としてソートをするじゃの巻
ビードソートって知ってますか
Bead sort(ビードソート)はbeads(ビーズ細工のビーズ)というようにビーズを使うソートアルゴリズムです。
ソートアルゴリズムの中でもいろんな意味で色が強めです。
ビードソートのアルゴリズム
[2, 4, 1, 3, 3]の数列をソートしたい場合を考えます。
まず、数列の数に応じてビーズを以下のように通していきます。
そして、ビーズを重力にまかして落とす。
するとなんということでしょう。
勝手にソートされてますね!すごい!
見たほうがわかりやすい方はこちら
Extended Bead-Sort - YouTube(クリックすると見れます)
詳しく知りたい方はこちら
Bead sort - Wikipediaより
計算量
Wikipediaをご覧ください。
Bead sort - Wikipedia #Complexity
出展は不明ですが、確かハードウェア上にソートアルゴリズム実装するときに使われるものらしいです(?)
Pythonでの実装
import numpy as np
def beadsort(series, max_num=10):
len_series = len(series)
array = np.array([[True]*num + [False]*(max_num-num) for num in series])
array = np.array([[True]*sum(array[:,idx]) + [False]*(len_series-sum(array[:,idx])) for idx in range(max_num)])
return [sum(array[:,idx]) for idx in range(len_series)]
a = [2,4,1,3,3]
print(beadsort(a)) # [4, 3, 3, 2, 1]
import numpy as np
def beadsort(series, max_num=10):
len_series = len(series)
array = np.array([[True]*num + [False]*(max_num-num) for num in series])
array = np.array([[True]*sum(array[:,idx]) + [False]*(len_series-sum(array[:,idx])) for idx in range(max_num)])
return [sum(array[:,idx]) for idx in range(len_series)]
a = [2,4,1,3,3]
print(beadsort(a)) # [4, 3, 3, 2, 1]
Author And Source
この問題について(【変なソートアルゴリズム】ビーズを落としてソートをするじゃの巻), 我々は、より多くの情報をここで見つけました https://qiita.com/redshoga/items/b8ca80a4f56d137fd9ba著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .