C++で配列を最大・最小交互形式に並べ替えるプログラム

整数型の配列が与えられます。この配列はソート済みの場合もあれば、未ソートの場合もあります。求められるタスクは、まず配列が未ソートであれば昇順にソートし、その後、配列を次のような順序で並べ替えることです。

つまり、1番目の要素には最大値、2番目の要素には最小値、3番目の要素には2番目に大きい値、4番目の要素には2番目に小さい値……というように、最大と最小を交互に配置していきます。

入出力シナリオの例

入力 − int arr[] = {7, 5, 2, 3, 4, 9, 10, 5}

出力 − 並べ替え前の配列: 2 3 4 5 5 7 9 10
最大最小形式に再配置した配列: 10 2 9 3 7 4 5 5

解説 − 整数型の配列 {7, 5, 2, 3, 4, 9, 10, 5} が与えられています。まず配列をソートすると {2 3 4 5 5 7 9 10} になります。次に、最大要素の10を arr[0] へ、最小要素の2を arr[1] へ、2番目に大きい要素の9を arr[2] へ……という順で配置します。最終的な結果の配列は「10 2 9 3 7 4 5 5」となります。

入力 − int arr[] = {2, 4, 1, 6, 7}

出力 − 並べ替え前の配列: 1 2 4 6 7
最大最小形式に再配置した配列: 7 1 6 2 4

解説 − 整数型の配列 {2, 4, 1, 6, 7} が与えられています。まず配列をソートすると {1, 2, 4, 6, 7} になります。次に、最大要素の7を arr[0] へ、最小要素の1を arr[1] へ、2番目に大きい要素の6を arr[2] へ……という順で配置します。最終的な結果の配列は「7 1 6 2 4」となります。

プログラムで使用するアプローチ

• 整数型の配列を入力として受け取り、配列のサイズを計算します。C++ STL の sort 関数を呼び出し、引数として arr[] と配列のサイズを渡して配列をソートします。

• 並べ替え前の配列を出力した後、関数 Rearr_Max_Min(arr, size) を呼び出します。

• 関数 Rearr_Max_Min(arr, size) の内部では以下の処理を行います。

  • 変数 max を宣言して size - 1 で初期化し、別の変数 min を宣言して 0 で初期化します。さらに変数 max_val を宣言し、arr[size - 1] + 1 を代入します。

  • i を 0 から size 未満まで回す for ループを開始します。ループ内で i % 2 == 0 であるかを判定し、真であれば arr[i] = arr[i] + (arr[max] % max_val) * max_val を実行して max をデクリメントします。

  • そうでなければ、arr[i] = arr[i] + (arr[min] % max_val) * max_val を実行して min をインクリメントします。

  • 再度、i を 0 から size 未満まで回す for ループを開始し、ループ内で arr[i] = arr[i] / max_val を実行して元の値を取り出します。

この手法のポイントは、余り演算（%）を使えば元の値が復元でき、除算（/）を使えば新しく埋め込んだ値が取り出せるという性質を利用している点です。これにより、追加の配列を使わずに O(1) の余分な空間で並べ替えが可能になります。

コード例

#include <bits/stdc++.h>
using namespace std;
void Rearr_Max_Min(int arr[], int size){
    int max = size - 1;
    int min = 0;
    int max_val = arr[size - 1] + 1;
    for (int i = 0; i < size; i++){
        if (i % 2 == 0){
            arr[i] += (arr[max] % max_val) * max_val;
            max--;
        }
        else{
            arr[i] += (arr[min] % max_val) * max_val;
            min++;
        }
    }
    for(int i = 0; i < size; i++){
        arr[i] = arr[i] / max_val;
    }
}
int main(){
    // 配列の入力
    int arr[] = {7, 5, 2, 3, 4, 9, 10, 5 };
    int size = sizeof(arr) / sizeof(arr[0]);
    // 配列をソート
    sort(arr, arr + size);
    // ソート後の元の配列を出力
    cout<<"Array before Arrangement: ";
    for (int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    // 配列を再配置する関数を呼び出し
    Rearr_Max_Min(arr, size);
    // 再配置後の配列を出力
    cout<<"\nRearrangement of an array in maximum minimum form is: ";
    for(int i = 0; i < size; i++){
        cout<< arr[i] << " ";
    }
    return 0;
}

出力結果

上記のコードを実行すると、次の出力が生成されます。

Array before Arrangement: 2 3 4 5 5 7 9 10
Rearrangement of an array in maximum minimum form is: 10 2 9 3 7 4 5 5