Pythonで学ぶ奇偶転置ソート（ブリックソート）の実装方法

この記事では、以下の問題に対する解決策について詳しく解説します。

問題の概要

問題文： 与えられた配列を、ブリックソート（奇偶転置ソート）を用いて昇順に並べ替えます。

このアルゴリズムには「奇数フェーズ」と「偶数フェーズ」という2つの段階があります。奇数フェーズでは奇数番目のインデックスの要素に対してバブルソートを行い、偶数フェーズでは偶数番目のインデックスの要素に対してバブルソートを行います。これらを交互に繰り返すことで、配列全体が整列される仕組みです。

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

サンプルコード

def oddEvenSort(arr, n):
    # ソート完了を判定するフラグ
    isSorted = 0
    while isSorted == 0:
        isSorted = 1
        temp = 0
        # 奇数フェーズ：奇数インデックスの要素を比較・交換
        for i in range(1, n-1, 2):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                isSorted = 0
        # 偶数フェーズ：偶数インデックスの要素を比較・交換
        for i in range(0, n-1, 2):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                isSorted = 0
    return

arr = [1,4,2,3,6,5,8,7]
n = len(arr)
oddEvenSort(arr, n)
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

処理の流れとポイント

すべての変数はローカルスコープ内で宣言されており、各ループ処理の中で参照されます。isSorted フラグは、一度も交換が発生しなくなった時点（つまり配列が完全に整列された時点）で while ループを抜けるための重要な役割を担っています。

なお、奇偶転置ソートは並列化しやすいアルゴリズムとして知られており、マルチプロセッサ環境でのソート処理にも応用されています。計算量は平均・最悪ともに O(n²) となるため、大規模なデータには不向きですが、シンプルな実装で理解しやすいのが特徴です。

まとめ

本記事では、Pythonを使って奇偶転置ソート（ブリックソート）を実装する方法を学びました。奇数フェーズと偶数フェーズを交互に繰り返すというシンプルな考え方で、バブルソートの変種として動作するこのアルゴリズムは、ソートアルゴリズムの基礎を理解するうえで非常に良い題材です。ぜひ自分のコードでも試してみてください。