選択ソートを改良した「双方向選択ソート」とは？仕組みとC++実装例を解説

ここでは、選択ソートに少し手を加えた改良版アルゴリズム「双方向選択ソート（Two-way Selection Sort）」を紹介します。通常の選択ソートは、配列から最小値（または最大値）を取り出して正しい位置へ配置することで並べ替えを行います。本手法ではこれを発展させ、最大値と最小値を同時に取得し、配列を両端から同時に整列させていきます。それでは、理解を深めるためにアルゴリズムの流れを見てみましょう。

アルゴリズム

twoWaySelectionSort(arr, n)

begin
    for i := 0, j := n-1 とし、i を 1 ずつ増加、j を 1 ずつ減少させながら i >= j になるまで繰り返す
        min := インデックス i 〜 j の範囲内の最小値
        max := インデックス i 〜 j の範囲内の最大値
        i_min := 最小値のインデックス
        i_max := 最大値のインデックス
        arr[i] と arr[i_min] を交換する
        もし arr[i_min] が max と等しいならば
            arr[j] と arr[i_min] を交換する
        そうでなければ
            arr[j] と arr[i_max] を交換する
        end if
    end for
end

C++による実装例

#include<iostream>
using namespace std;
void twoWaySelectionSort(int arr[], int n) {
    //i は左端から、j は右端から中央に向かって移動する
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        int min = arr[i], max = arr[i];
        int i_min = i, i_max = i; //i_min と i_max はそれぞれ最小値・最大値のインデックスを保持する
        for (int k = i; k <= j; k++) {
            if (arr[k] > max) {
                max = arr[k];
                i_max = k;
            } else if (arr[k] < min) {
                min = arr[k];
                i_min = k;
            }
        }
        swap(arr[i], arr[i_min]); //最小値をインデックス i の位置へ配置する
        if (arr[i_min] == max) //交換によって最大値が i_min の位置へ移動していた場合
            swap(arr[j], arr[i_min]);
        else
            swap(arr[j], arr[i_max]);
    }
}
main() {
    int arr[] = { 25, 45, 14, 10, 23, 29, 65, 21, 78, 96, 30 };
    int n = sizeof(arr) / sizeof(arr[0]);
    twoWaySelectionSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
    cout << arr[i] << " ";
}

実行結果

Sorted array: 10 14 21 23 25 29 30 45 65 78 96

解説：このアルゴリズムのポイント

1回の走査で最小値と最大値を同時に確定

通常の選択ソートでは、1回の走査につき最小値（または最大値）を1つだけ確定します。一方、双方向選択ソートでは、未ソート領域を1回走査するだけで最小値と最大値の両方が求められます。そのため、ソート済みの領域が配列の両端から同時に広がっていくのが特徴です。

max の位置を確認する理由

コード中の if (arr[i_min] == max) という条件が重要なポイントです。最小値を先頭位置 i へ交換した時点で、もし最大値が元々インデックス i に存在していた場合、その最大値は i_min の位置へ移動してしまいます。この状態で古い i_max を使って交換すると、誤った要素を操作することになるため、「最大値が移動済みかどうか」を判定して処理を切り替えているのです。

計算量について

外側のループの繰り返し回数は約 n/2 回となり、従来の選択ソートの半分のパス数で済みます。ただし、各パスで行う比較処理の総量はほぼ同じであるため、全体の時間計算量は O(n²) のまま変わりません。それでもパス数が減る分、実際の動作はわずかに高速化されます。