C++でWiggleソート（波状ソート）を実装する方法

問題概要

ソートされていない整数型の配列 nums が与えられます。この配列をインプレース（追加メモリを使用せず）で並べ替え、次の条件を満たすようにします。

nums[0] <= nums[1] >= nums[2] <= nums[3] ...

つまり、隣り合う要素の大小関係が「小さい・大きい・小さい…」と交互に波打つように（wiggle＝揺らぐように）配置するのが目標です。

例として、入力が nums = [3,5,2,1,6,4] の場合、出力は [3,5,1,6,2,4] のようになります。なお、条件を満たす答えは複数存在する可能性があります。

解法のアプローチ

この問題は貪欲法により、配列を1回走査するだけで解くことができます。先頭から順に隣接する2要素を比較し、その位置に求められる大小パターンに反している場合のみスワップを行います。

具体的な手順は以下の通りです。

• n := nums のサイズとする
• i := 0 から始め、i < n - 1 の間、i を1ずつ増やしながら以下を繰り返す
  • i が偶数なのに nums[i] > nums[i+1] となっている場合、または i が奇数なのに nums[i] <= nums[i+1] となっている場合（＝期待される順序と逆の場合）、swap(nums[i], nums[i + 1]) を実行する

偶数番目には「≤」、奇数番目には「≥」の関係が必要です。各位置で条件違反があれば即座に入れ替えることで、配列全体が必然的にWiggleパターンへと整っていきます。

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) {
        int n = nums.size();
        for(int i = 0; i < n - 1; i+=1){
            if((i % 2 == 0) == (nums[i] > nums[i + 1])){
                swap(nums[i], nums[i + 1]);
            }
        }
    }
};
main(){
    vector<int> v = {3,5,2,1,6,4};
    Solution ob;
    ob.wiggleSort(v);
    print_vector(v);
}

入力

{3,5,2,1,6,4}

出力

[3, 5, 1, 6, 2, 4]

計算量

時間計算量は配列を1回だけ走査するため O(n)、追加領域を一切使用しないため空間計算量は O(1) となります。シンプルでありながら効率的な解法と言えるでしょう。