C++で解くWiggle Sort II：大小が交互になる並べ替えアルゴリズムの実装

問題概要

ソートされていない整数配列 nums が与えられます。これを並べ替えて、nums[0] < nums[1] > nums[2] < nums[3] のように、隣接する要素の大小関係が交互に入れ替わる「揺らぎ（wiggle）」構造を作ります。
例えば、入力が [1,5,1,1,6,4] の場合、出力は [1,6,1,5,1,4] のようになります。なお、条件を満たす答えは複数存在する場合があります。

アルゴリズムのアプローチ

この問題は、ソート済み配列を「小さい半分」と「大きい半分」に分け、それぞれを逆順で偶数番目・奇数番目のインデックスへ配置することで効率的に解けます。具体的な手順は以下の通りです。

1. 元の配列 nums と同じ要素を持つコピー配列 x を作成する
2. 配列 x を昇順にソートする
3. i := x.size() - 1、j := (x.size() - 1) / 2、n := nums.size() を初期値として設定する
4. 偶数インデックス（l = 0, 2, 4, ...）には、ソート済み配列の中央部分から x[j] を順に代入し、j を1ずつ減らしていく
5. 奇数インデックス（l = 1, 3, 5, ...）には、ソート済み配列の末尾から x[i] を順に代入し、i を1ずつ減らしていく

この手法により、小さい方の半分が偶数位置へ、大きい方の半分が奇数位置へ逆順で配置されるため、結果的に大小が交互に並ぶ配列が得られます。

C++での実装例

以下のコードは、上記のアルゴリズムをC++で実装したものです。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    void wiggleSort(vector<int>& nums) {
        vector <int> x(nums);
        sort(x.begin(), x.end());
        int i = x.size() - 1 ;
        int j = (x.size() - 1)/2;
        int n = nums.size();
        for(int l = 0; l < n; l +=2){
            nums[l] = x[j--];
        }
        for(int l = 1; l < n; l +=2){
            nums[l] = x[i--];
        }
    }
};
main(){
    vector<int> v = {1,5,1,1,6,4};
    Solution ob;
    (ob.wiggleSort(v));
    print_vector(v);
}

入力

[1,5,1,1,6,4]

出力

[1, 6, 1, 5, 1, 4]

計算量の評価

時間計算量はソート処理が支配的となるため O(n log n)、コピー配列を使用するため空間計算量は O(n) となります。より高度な解法としては、中央値（median）を基準に仮想インデックスと三分割法（Dutch National Flag）を組み合わせ、O(n) 時間・O(1) 追加空間で解く方法も知られていますが、本記事で紹介した手法はロジックがシンプルで理解しやすい点が大きな魅力です。