こんにちは。KENTEMでフロントエンドを担当しているS・Kです。

あっという間に10月も終わり、今年も残すところあと2ヶ月となりました。時間経つの早すぎじゃない？と思う今日この頃です。

皆さんも残りの２か月、体調管理には気をつけながら一緒にラストスパートを駆け抜けましょう。

はじめに
変わり種ソート4選
まとめ
参考URL
おわりに

はじめに

とつぜんですが皆さんソート使ってますか？実はソートといっても様々な種類があります。

例えば、バブルソートやクイックソート、ヒープソートなどです。これらは皆さん聞いたことがあるかと思います。

今回は、数あるソートの中でも特に個性的な変わり種ソートを４つ紹介します。

変わり種ソート4選

ボゴソート - 運任せのソート

概要

配列全体をランダムにシャッフルし、ソート済みになるまでそれを繰り返します。まさに、運にすべてを任せるソートです。

ちなみに「ボゴ（Bogo）」という名前は「偽の、いんちきの」という意味を持つスラング "bogus" に由来すると言われています。

アルゴリズムの流れ

ソートしたい整数の配列を受け取る。
配列がソート済みかを確認して、ソート済みなら終了する。
配列がソートされていなければ、配列全体をランダムにシャッフルする。
1に戻る。

コード実装例

import random

"""配列がソート済みか確認する関数"""
def is_sorted(data: list):
    for i in range(len(data) - 1):
        if data[i] > data[i+1]:
            return False
    return True

"""ボゴソートを実行する関数（シャッフルした回数も表示する）"""
def bogo_sort(data: list) -> int:
    shuffle_count = 0
    while not is_sorted(data):
        shuffle_count += 1
        random.shuffle(data)
    
    return shuffle_count # 最終的なシャッフル回数を返す

my_list = [5, 1, 4, 2]
print(f"ソート前: {my_list}")

shuffle_count = bogo_sort(my_list) 

print(f"ソート後: {my_list}")
print(f"試行回数: {shuffle_count}")

ソート前: [5, 1, 4, 2]
ソート後: [1, 2, 4, 5]
試行回数: 60     <= この値はボゴソートを実行するたびに代わります。

計算量と実用性

実行結果を見ると最終的にはきちんとソートできていますね。

ただ、このボゴソートは計算量が恐ろしいことになってしまいます。

平均計算量はO(n×n!)で、最悪計算量はO(∞)（無限大）です。シャッフルしてソートできてないといつまでも終わりませんからね。

平均計算量について表にするとこうなります。

データ数 (n)	計算量 (n×n!)
3	18
4	96
5	600
6	4,320
7	35,280
8	322,560
9	3,265,920
10	36,288,000
11	439,084,800
12	5,748,019,200
13	80,951,270,400
14	1,220,496,076,800

ごらんの通りデータ数が13になったあたりから計算量が恐ろしいことになっていることが分かります。もし、データ数が1000になったらおそらく宇宙が終わるまで計算しても終わらないでしょうね。

「ソートは高速であるべき」という常識を覆す、非常に面白いソートアルゴリズムだと思います。

スリープソート - 時間を用いるソート

概要

ソートしたい配列の各数値 n に対して、「n 秒（またはミリ秒）待機（スリープ）する」という動作を同時にスタートさせます。数値が小さいほど待機時間が短く先に動作が終わります。結果として、数値が小さい順に出力されるという仕組みです。

アルゴリズムの流れ

ソートしたい数値の配列を受け取る。
配列の各数値 n について、「n に比例した時間だけ待機し、待機が終わったら n を報告する」という個別の処理を数値の個数分だけ用意する。
各スレッドは自身の持つ数値 n に比例した時間だけスリープ（待機）する。
スリープが終了したら、そのスレッドは自身の数値 n を結果用のリストに追加する。
すべてのスレッドが終了するのを待つ。

コード実装例

import threading
import time

# 各スレッドが行う作業の関数
def worker(num, result_list):
    time.sleep(num * 0.01)
    # スリープが終わったらリストに追加
    result_list.append(num)

def sleep_sort(numbers):
    result = []
    threads = []
    
    for n in numbers:
        # 数値ごとにスレッドを作成し、処理（worker）を割り当て
        t = threading.Thread(target=worker, args=(n, result))
        t.start()
        threads.append(t)
        
    # すべてのスレッドが終了するのを待つ
    for t in threads:
        t.join()
        
    return result

my_list = [5, 1, 8, 3, 2, 10]
    
print(f"ソート前: {my_list}")
sorted_list = sleep_sort(my_list)
print(f"ソート後: {sorted_list}")

ソート前: [5, 1, 8, 3, 2, 10]
ソート後: [1, 2, 3, 5, 8, 10]

t = threading.Thread(target=worker, args=(n, result))

補足ですが、このコードで使われているthreadingは、Pythonで「並列処理」（複数の処理を同時に実行すること）を実現するための標準ライブラリです。

threadingの基本的な概念や詳しい使い方については、以下の記事が非常に分かりやすくまとまっていて、参考にさせていただきました。

【Python】並列処理を理解しよう　【threadingの使い方 01】

実行時間と実用性

もうお分かりかと思いますが、スリープソートの実行時間はデータの中の最大値Mに比例します。例えばですが、ソートしたい配列の中に100000000という数字があると100000000ミリ秒（約28時間）かかるわけです。さすがに遅すぎますよね。

ですので実用性に関してはありませんが、こんな発想があったのかと考えさせられるとてもユニークで面白いソートだと思います。

ビーズソート - 重力を利用するソート

概要

ソートしたい数値のリストをビーズを使って表現し重力で落下させることで並べ替えます。

詳しく見てみましょう。

（参考）ビーズソート-wikipedia

まず、[2, 4, 1, 3, 3]という配列があるとしてこのようにビーズを通していきます。

通し終わったら重力に任せてビーズを落下させます。

どうでしょうか？横に並んだビーズの数を見ると見事にソートされています。これがビーズソートの仕組みになります。

実際に動かすとこのようになります。

＊GeminiのCanvas機能で作成したものになります。

アルゴリズムの流れ

ソートしたい正の整数の配列（例：[5, 2, 8]）を受け取る。
配列の要素数をn、配列の最大値をmax_valとして、n × max_valの2次元配列を作る。
[5, 2, 8]の場合の2次元配列はこのようになる。

行0 (5): [1, 1, 1, 1, 1, 0, 0, 0]
行1 (2): [1, 1, 0, 0, 0, 0, 0, 0]
行2 (8): [1, 1, 1, 1, 1, 1, 1, 1]

本来なら重力に任せてビーズを落下させるが、コード上では落下させずに列ごとにビーズの数を数えていく。
左の列から順に見ていき、その列のインデックス（0から始まる番号）をjとして、縦に見たビーズの総個数をsum_beadsとする。
j + 1以上の数はsum_beads個あるので、ソート前の配列の後ろから数えてsum_beads個のマスを、値j + 1で上書きしていく。

手順5の説明が少し難しいかと思いますので具体的に見ていきましょう。

j=0 (値 1) の時: sum_beads が3なので元の配列は [1, 1, 1] になる。(後ろ3つが1に上書きされる)
j=1 (値 2) の時: sum_beads が3なので元の配列は [2, 2, 2] になる。(後ろ3つが2に上書きされる)
j=2 (値 3) の時: sum_beads が2なので元の配列は [2, 3, 3] になる。(後ろ2つが3に上書きされる)
j=3 (値 4) の時: sum_beads が2なので元の配列は [2, 4, 4] になる。(後ろ2つが4に上書きされる)
…
j=6 (値 7) の時: sum_beads が1なので元の配列は [2, 5, 7] になる。(後ろ1つが7に上書きされる)
j=7 (値 8) の時: sum_beads が1なので元の配列は [2, 5, 8] になる。(後ろ1つが8に上書きされる)

このようにしてソートされます。

コード実装例

def bead_sort(a):
    n = len(a)
    max_val = max(a)
    
    # 2. ビーズを配置
    beads = [[1 if j < num else 0 for j in range(max_val)] for num in a]
    
    # 3. 列ごとに処理
    for j in range(max_val):
        
        # (A) その列のビーズの合計を数える
        sum_beads = sum(beads[i][j] for i in range(n))
        
        # (B) 元の配列 'a' の末尾 'sum_beads' 個を (j+1) で上書き
        a[n - sum_beads:] = [j + 1] * sum_beads

my_list = [5, 1, 8, 3, 2, 10]
    
print(f"ソート前: {my_list}")
bead_sort(my_list)
print(f"ソート後: {my_list}")

ソート前: [5, 1, 8, 3, 2, 10]
ソート後: [1, 2, 3, 5, 8, 10]

実行時間と実用性

ビーズソートの計算量は、ソートする配列の要素数nと、配列内の最大値max_valに依存するのでO(n × max_val)となります。もし配列の要素の中に大きな数があると計算量が膨れ上がり実行時間は遅くなります。

また、ソートの性質上正の値しか扱えません。

これらの点から、ビーズソートは残念ながら実用的ではありません。ただ、重力という物理的な現象をソートに用いるのはとても面白いですよね。コード上では重力を使っているわけではありませんが…。個人的にはとてもためになったソートでした。

量子ボゴソート - 宇宙を破壊するソート

概要

量子ボゴソートは1つ目で紹介したランダムなシャッフルを繰り返す「ボゴソート」を発展させたジョークアルゴリズムです。

基本的な仕組みは、ボゴソートと同様にまず配列がソート済みか確認します。もしソートされていなければ配列をランダムにシャッフルします。

ここまでは通常のボゴソートと同じですが、量子ボゴソートの決定的な違いは、シャッフル後に配列がソートされていなかった場合、その宇宙を破壊するという点にあります。

もしSF理論における「多世界解釈」が正しいと仮定するならば、観測者が存在し続けることができるのは、配列のシャッフルが偶然成功し宇宙が破壊されなかった世界線だけです。

したがって、観測者が無事である限り、その世界ではソートが完了しているという仕組みです。

コード実装例

ジョークソートなので実際には実装できませんが、仮に実装するとこのようになるかと思います。

import random
import sys

"""配列がソート済みか確認する関数"""
def is_sorted(data: list):
    for i in range(len(data) - 1):
        if data[i] > data[i+1]:
            return False
    return True

"""
量子ボゴソート：
シャッフルし、ソートされていなければ宇宙を破壊する
"""
def quantum_bogo_sort(data: list):
    random.shuffle(data)
    
    # ソートされているか？
    if not is_sorted(data):
        # 失敗した宇宙はここで消滅する
        print("ソートされていません。宇宙は破壊されました。")
        sys.exit(1) # 宇宙を強制終了（コード上で再現）

my_list = [5, 2, 8, 1] 
print(f"ソート前の配列: {my_list}")

quantum_bogo_sort(my_list)

# 以下のコードが実行されるのは、
# "quantum_bogo_sort" が宇宙を破壊しなかった（＝ソートに成功した）場合のみ
print(f"観測結果: {my_list}")
print("おめでとうございます！ソートされた宇宙を観測しました。")