C++でソート済み配列を最大・最小交互の形式に並べ替える方法

問題の概要

ソート済みの配列が与えられます。この配列を「最大・最小形式」に並べ替えることが求められます。具体的には、1番目の要素が最大値、2番目の要素が最小値、3番目の要素が2番目に大きい値、4番目の要素が2番目に小さい値、というように交互に配置していきます。以下に例を示します。

入力 : arr[ ] = { 10, 20, 30, 40, 50, 60 }
出力 : { 60, 10, 50, 20, 40, 30 }
説明 : 配列は「1番目の最大値、1番目の最小値、2番目の最大値、2番目の最小値、3番目の最大値、3番目の最小値」という順序で並べ替えられます。

入力 : arr[ ] = { 15, 17, 19, 23, 36, 67, 69 }
出力 : { 69, 15, 67, 17, 36, 19, 23 }

配列を最大・最小形式に並べ替えるには、次のアプローチが有効です。

解決策のアプローチ

ツーポインタ（双方向ポインタ）アプローチ

まず、最大要素と最小要素を指すための変数 min と max を用意し、並べ替えた結果を格納するために同じサイズの新しい空の配列を作成します。次に配列を走査し、現在のインデックスが偶数の場合は arr[max] の要素を新しい配列に追加して max を1減らします。インデックスが奇数の場合は arr[min] の要素を追加して min を1増やします。この処理を max が min より小さくなるまで繰り返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

int main () {
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int n = sizeof (arr) / sizeof (arr[0]);
    // 並べ替えた配列を格納するための新しい配列を作成
    int final[n];
    // 変数を先頭と末尾の要素のインデックスに設定
    int min = 0, max = n - 1;
    int count = 0;
    // max が min 以上である間、配列を反復処理する
    for (int i = 0; min <= max; i++) {
        // count が偶数の場合は最大側の要素を格納
        if (count % 2 == 0) {
            final[i] = arr[max];
            max--;
        }
        // 奇数の場合は最小側の要素を格納
        else {
            final[i] = arr[min];
            min++;
        }
        count++;
    }
    // 最終的な並べ替え後の配列を出力
    for (int i = 0; i < n; i++)
        cout << final[ i ] << " ";
    return 0;
}

出力結果

6 1 5 2 4 3

コードの解説

• 変数は min = 0、max = 配列長(n) - 1 として初期化されます。
• for (int i = 0; min <= max; i++) により、max が min より小さくなるまで配列を反復処理します。
• カウントが偶数の場合は、max が指す要素を最終配列に追加し、変数 max を1減らします。
• カウントが奇数の場合は、min が指す要素を最終配列に追加し、変数 min を1増やします。
• 最終的に、結果の配列は final[ ] 配列に格納されます。

まとめ

本記事では、与えられた配列を最大・最小形式に並べ替える解決策について解説しました。ツーポインタ法を用いた効率的なアプローチにより、時間計算量 O(n) でこの問題を解くことができます。また、C++による実装コードも紹介しました。同様のプログラムは、C、Java、Python など他の言語でも簡単に記述できます。この記事が皆さんのお役に立てば幸いです。