C++で学ぶ配列の並べ替え – 最小値・最大値・2番目に小さい値・2番目に大きい値を交互に配置する方法

配列が与えられたとき、最初の要素を最小値、2番目の要素を最大値、3番目の要素を2番目に小さい値、4番目の要素を2番目に大きい値…というように、小さい値と大きい値を交互に並べ替えることを考えます。具体例は以下のとおりです。

入力 : arr[ ] = { 13, 34, 30, 56, 78, 3 }
出力 : { 3, 78, 13, 56, 34, 30 }
説明 : 配列は { 1番目に小さい値, 1番目に大きい値, 2番目に小さい値, 2番目に大きい値, 3番目に小さい値, 3番目に大きい値 } の順に並べ替えられます

入力 : arr[ ] = { 2, 4, 6, 8, 11, 13, 15 }
出力 : { 2, 15, 4, 13, 6, 11, 8 }

解決策へのアプローチ

この問題は、最小要素と最大要素をそれぞれ指す2つの変数「x」と「y」を使うことで解決できます。ただし、そのためには配列がソート済みである必要があるため、まず元の配列を昇順にソートします。続いて、同じサイズの新しい空の配列を用意し、並べ替えた結果をそこに格納していきます。配列を先頭から走査し、現在のインデックス i が偶数の場合は arr[x](最小側)の要素を新しい配列に格納して x を1増やし、i が奇数の場合は arr[y](最大側)の要素を格納して y を1減らします。この処理を y が x より小さくなるまで繰り返します。

この手法の計算量は、ソートに O(n log n)、並べ替えの走査に O(n) となるため、全体の計算量は O(n log n) となります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int main () {
    int arr[] = { 2, 4, 6, 8, 11, 13, 15 };
    int n = sizeof (arr) / sizeof (arr[0]);

    // 並べ替えた配列を格納するための新しい配列を作成
    int reordered_array[n];

    // 元の配列を昇順にソート
    sort(arr, arr + n);

    // 最小要素と最大要素のインデックスを指す変数を初期化
    int x = 0, y = n - 1;
    int i = 0;

    // x が y 以下である限り配列を走査
    while (x <= y) {
        // i が偶数の場合は最小側の要素を格納
        if (i % 2 == 0) {
            reordered_array[i] = arr[x];
            x++;
        }
        // i が奇数の場合は最大側の要素を格納
        else {
            reordered_array[i] = arr[y];
            y--;
        }
        i++;
    }
    // 並べ替えた配列を出力
    for (int i = 0; i < n; i++)
        cout << reordered_array[i] << " ";

    // もしくは、元の配列を更新してもよい
    // for (int i = 0; i < n; i++)
    // arr[i] = reordered_array[i];
    return 0;
}

出力

2 15 4 13 6 11 8

コードの解説

• 変数は x = 0、y = 配列の長さ(n) - 1 として初期化されます。
• while (x <= y) ループによって、x が y より大きくなるまで配列を走査します。
• インデックス i が偶数の場合、最小側の要素(arr[x])を結果の配列に格納し、変数 x を1増やします。
• インデックス i が奇数の場合、最大側の要素(arr[y])を結果の配列に格納し、変数 y を1減らします。
• 最終的に、並べ替えられた配列が reordered_array[ ] に格納されます。

まとめ

本記事では、与えられた配列を「最小値 → 最大値 → 2番目に小さい値 → 2番目に大きい値…」という形で交互に並べ替えるアルゴリズムについて解説し、あわせてC++での実装例を紹介しました。ソート後に2つのポインタを両端から動かすだけというシンプルな手法で、実装も非常に容易です。同じロジックはC、Java、Pythonなど他の言語でも同様に実装できます。本記事が皆さんの学習の一助となれば幸いです。