C++で配列の要素を昇順・降順交互に出力する方法

この問題では、数値の配列が与えられ、その要素を昇順と降順を交互に切り替えながら出力する必要があります。出力の順序は、最初の2要素を昇順、次の3要素を降順、さらにその次の4要素を昇順というように、グループごとに昇順・降順が交互に切り替わるルールに従います。

具体例を見ながら、問題をより深く理解しましょう。

入力  : {1, 4, 0, 2, 7, 9, 3}
出力  : 0 1 9 7 4 2 3

解説 − 配列を昇順にソートすると「0 1 2 3 4 7 9」となります。最初の2要素は「0 1」、次に末尾から3要素は「9 7 4」、さらに次の4要素として残りの「2 3」を出力します(残りが2要素しかないため、4要素分は取得できません)。

解決のアプローチ

この問題を解くには、まず配列を昇順にソートします。その後、先頭側から出力するためのポインタ(left)と、末尾側から出力するためのポインタ(right)の2つを使用します。さらに、先頭から出力するか末尾から出力するかを判定するためのフラグ変数(flag)も用意し、これを交互に切り替えながら要素を出力していきます。

アルゴリズム

ステップ1 : 配列の要素をソートする。
ステップ2 : left = 0、right = n-1、flag = 2 で初期化する。
ステップ3 : left <= right の間、以下を繰り返す。
ステップ4 : flag % 2 == 0 の場合 :
    ステップ4.1 : i = left から left + flag までループし、arr[i] を出力する。
    ステップ4.2 : left = i と更新し、flag をインクリメントする。
ステップ5 : それ以外の場合 :
    ステップ5.1 : i = right から right - flag までループし、arr[i] を出力する。
    ステップ5.2 : right = i と更新し、flag をインクリメントする。
ステップ6 : 終了

実装例

それでは、このアルゴリズムの動作を確認するためのプログラムを作成してみましょう。

#include <bits/stdc++.h>
using namespace std;
void printAlternateSeq(int arr[], int n){
    sort(arr, arr + n);
    int left = 0, right = n - 1, flag = 2, i;
    while (left <= right) {
        if (flag%2 == 0) {
            for (i = left; i < left + flag && i <= right; i++)
            cout<<arr[i]<<" ";
            left = i;
        } else {
            for (i = right; i > right - flag && i >= left; i--)
                cout<<arr[i]<<" ";
            right = i;
        }
        flag++;
    }
}
int main(){
    int n = 6;
    int arr[] = {23, 45, 78, 32, 89, 10 };
    printAlternateSeq(arr, n);
    return 0;
}

出力

10 23 89 78 45 32

出力の解説

入力配列「{23, 45, 78, 32, 89, 10}」を昇順にソートすると「10 23 32 45 78 89」となります。まずflag=2(偶数)なので、先頭から2要素「10 23」を出力します。次にflag=3(奇数)となるため、末尾から3要素「89 78 45」を出力します。最後にflag=4(偶数)で先頭から出力しようとしますが、残りは1要素「32」のみなので、これが出力されて処理が完了します。

計算量

このアルゴリズムの計算量は、ソート処理が支配的となるため O(n log n) です。要素の出力部分は各要素を一度だけ処理するため O(n) となり、全体として効率的な解法と言えます。