C++での交互ソート（代替ソート）の実装方法

交互ソートとは

交互ソートとは、整数配列の要素を「最大値・最小値・2番目に小さい値・2番目に大きい値…」という順序で並べ替える手法です。つまり、大きい値と小さい値が交互に出力されるような並び方になります。

具体例を見てみましょう。

入力 : 4 1 8 2 9 3 7
出力 : 9 1 8 2 7 3 4
説明 : 配列を昇順にソートすると「1 2 3 4 7 8 9」になります。
これを交互ソートの形式に並べ替えると、まず最大値の9、
次に最小値の1、続いて8、2、7、3、4 の順に出力されます。

この概念を理解したところで、解決策を考えてみましょう。最もシンプルなアプローチは、まず配列を通常通りソートし、その後ソート済み配列の末尾（最大値）と先頭（最小値）から交互に要素を出力するというものです。この方針に基づいたアルゴリズムを作成します。

アルゴリズム

ステップ1 : 配列をソートする。
ステップ2 : 先頭から走査するポインタと、末尾から走査するポインタの2つを用意する。
ステップ3 : 2つのポインタが指す値を交互に出力し、それぞれのポインタを内側へ進める。

C++による実装例

以下のコードでは、選択ソート（selection sort）で配列を整列させた後、両端から交互に要素を出力しています。要素数が奇数の場合は、中央の要素を最後に1回だけ出力する点に注意してください。

#include <iostream>
using namespace std;
void alternateSort(int arr[], int n) ;
void swap(int *xp, int *yp) ;
void selectionSort(int arr[], int n) ;
int main(){
    int arr[] = { 4,1,8,2,9,3,7};
    int n = sizeof(arr)/sizeof(arr[0]);
    alternateSort(arr, n);
    return 0;
}
void alternateSort(int arr[], int n){
    selectionSort(arr, n);
    int i = 0, j = n-1;
    while (i < j) {
        cout << arr[j--] << " ";
        cout << arr[i++] << " ";
    }
    if (n % 2 != 0)
        cout << arr[i];
}
void swap(int *xp, int *yp){
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
void selectionSort(int arr[], int n){
    int i, j, min_idx;
    for (i = 0; i < n-1; i++){
        min_idx = i;
        for (j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        swap(&arr[min_idx], &arr[i]);
    }
}

実行結果

9 1 8 2 7 3 4

処理の流れと計算量

このプログラムの動作を整理すると以下のようになります。

1. ソート処理： 選択ソートにより配列を昇順に整列します。時間計算量は O(n²) です。
2. 交互出力： ポインタ i（先頭）と j（末尾）を使い、arr[j] → arr[i] の順に出力しながら互いに接近させていきます。これは O(n) で完了します。
3. 奇数個への対応： 要素数が奇数の場合、i と j が出会う位置（中央）の要素が残るため、ループ終了後にその値を出力します。

全体の時間計算量はソート部分が支配的となるため O(n²)、追加のメモリ使用量は O(1) となります。より高速にしたい場合は、std::sort を使えば平均 O(n log n) に改善できます。また、C++では std::swap や範囲ベースのイテレータ（rbegin / rend）を活用することで、コードをさらに簡潔に記述することも可能です。