Pythonで実装するストゥージソート：アルゴリズムの手順とコード例を徹底解説

本記事では、ストゥージソート(Stooge Sort)を用いて配列を並べ替えるPythonプログラムの実装方法について解説します。

問題文

与えられた配列を、ストゥージソートというアルゴリズムを使って昇順に並べ替えることが課題です。

ストゥージソートとは

ストゥージソートは、配列の一部を再帰的に繰り返しソートすることで全体を整列させる、非常にシンプルな比較ソートアルゴリズムです。計算量は O(n^log3/log1.5) ≒ O(n^2.71) となり、バブルソートなどよりもさらに非効率ですが、再帰処理やアルゴリズム設計の仕組みを理解するための学習教材として知られています。

アルゴリズムの手順

1. 配列の先頭要素が末尾の要素より大きい場合、両者を交換する。
2. 配列の先頭から約2/3の部分を再帰的にソートする。
3. 配列の末尾から約2/3の部分を再帰的にソートする。
4. 確認のため、もう一度先頭側の2/3をソートする。

それでは、実際の実装を見ていきましょう。

実装例(Pythonコード)

def stoogesort(arr, l, h):
    if l >= h:
        return
    # 要素の交換
    if arr[l] > arr[h]:
        t = arr[l]
        arr[l] = arr[h]
        arr[h] = t
    # 要素数が3以上の場合
    if h-l+1 > 2:
        t = (int)((h-l+1)/3)
        # 先頭側の2/3をソート
        stoogesort(arr, l, (h-t))
        # 末尾側の2/3をソート
        stoogesort(arr, l+t, h)
        # 再度、先頭側の2/3をソート
        stoogesort(arr, l, (h-t))

# メイン処理
arr = [1,4,2,3,6,5,8,7]
n = len(arr)
stoogesort(arr, 0, n-1)
print ("Sorted sequence is:")
for i in range(0, n):
    print(arr[i], end = " ")

出力結果

Sorted sequence is:
1 2 3 4 5 6 7 8

コードの解説

関数 stoogesort(arr, l, h) は、配列 arr のインデックス l から h までの範囲を対象にソートを実行します。まず範囲の両端の要素を比較し、先頭が大きければ交換します。続いて、範囲の長さが3より大きい場合は、長さの1/3を t として求め、「前2/3 → 後2/3 → 再び前2/3」の順に再帰呼び出しを行うことで、範囲全体が整列される仕組みです。すべての変数はローカルスコープ内で宣言されており、関数外へ影響を与えません。

まとめ

本記事では、Pythonによるストゥージソートの実装方法を学びました。コードは非常に簡潔で再帰の動作を理解しやすい一方、計算量が大きいため実務での利用には向いていません。あくまで学習目的のアルゴリズムである点を押さえておきましょう。