【変なソートアルゴリズム】ビーズを落としてソートをするじゃの巻

↑ビーズの写真

ビードソートって知ってますか

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]