C++で配列をジグザグ順に並べ替えるアルゴリズムを解説

はじめに

このチュートリアルでは、配列をジグザグ形式（zig-zag fashion）に変換するC++プログラムについて解説します。

ここでは、重複のない要素からなる配列が与えられます。私たちのタスクは、隣接する要素どうしが「小さい → 大きい → 小さい → 大きい…」と交互になるように、配列の要素を並べ替えることです。

例えば、入力配列が {4, 3, 7, 8, 6, 2, 1} の場合、期待される出力は {3, 7, 4, 8, 2, 6, 1} となります。この結果では arr[0] < arr[1] > arr[2] < arr[3] … という大小関係が交互に成り立っています。

アルゴリズムの考え方

この問題は、ブール型のフラグを1つ用意するだけで、追加の配列を使わずに線形時間で解くことができます。手順は以下の通りです。

1. フラグ flag を true で初期化します。true は「現在の要素が次の要素以下であるべき」ことを意味します。
2. 配列を先頭から順に走査し、flag が true のときに arr[i] > arr[i+1] であれば2つの要素を交換します。
3. flag が false のときは、arr[i] < arr[i+1] であれば交換します。
4. 各反復の最後で flag を反転させ、大小の関係を交互に切り替えます。

C++による実装例

#include <iostream>
using namespace std;

// ジグザグ形式への変換
void convert_zigzag(int arr[], int n) {
    // flagは大小関係を表す（trueなら「小さい」が先）
    bool flag = true;
    for (int i = 0; i <= n - 2; i++) {
        if (flag) {
            // 現在の要素が次より大きければ交換
            if (arr[i] > arr[i + 1])
                swap(arr[i], arr[i + 1]);
        } else {
            // 現在の要素が次より小さければ交換
            if (arr[i] < arr[i + 1])
                swap(arr[i], arr[i + 1]);
        }
        flag = !flag;
    }
}

int main() {
    int arr[] = {4, 3, 7, 8, 6, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    convert_zigzag(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

実行結果

3 7 4 8 2 6 1

処理の流れを確認しよう

入力 {4, 3, 7, 8, 6, 2, 1} を例に、各ステップでの動きを見てみましょう。

• i = 0（flag = true）: 4 > 3 なので交換 → {3, 4, 7, 8, 6, 2, 1}
• i = 1（flag = false）: 4 < 7 なのでそのまま
• i = 2（flag = true）: 7 > 4…ではなく 7 < 8 なのでそのまま（7 > 8 は偽）→ 実際には 7 > 8 が成立しないため無交換
• i = 3（flag = false）: 8 > 6 なので条件 arr[i] < arr[i+1] は不成立、しかし 8 > 6 のため交換 → {3, 4, 7, 6, 8, 2, 1}
• i = 4（flag = true）: 8 > 2 なので交換 → {3, 4, 7, 6, 2, 8, 1}
• i = 5（flag = false）: 8 > 1 なので交換 → {3, 4, 7, 6, 2, 1, 8}…最終的に 3 7 4 8 2 6 1 となります。

ポイントは、各位置で必要な場合だけ隣接要素を交換すればよいことです。すでに条件を満たしているペアには触れないため、全体として最小限の操作で済みます。

計算量

• 時間計算量： O(n) — 配列を一度だけ走査すればよいため非常に高速です。
• 空間計算量： O(1) — フラグ1つだけで処理でき、追加のメモリは不要です。

まとめ

ジグザグへの並べ替えは、ソートのような複雑な処理を必要とせず、ブールフラグによる隣接要素の交換だけで実現できます。O(n) 時間・O(1) 空間という優れた効率を持つため、面接や競技プログラミングでも頻出の定番アルゴリズムです。ぜひ自分のコードにも取り入れてみてください。