C++-এ Wiggle Sort: অ্যারে কে Wiggle ক্রমে সাজানো (nums[0] <= nums[1] >= nums[2]...)

একটি আনসোর্টেড অ্যারে nums দেওয়া আছে। এটিকে ইন-প্লেস (in-place) রি-অর্ডার করতে হবে যেন nums[0] <= nums[1] >= nums[2] <= nums[3]... প্যাটার্ন মেনে চলে।

উদাহরণ

ইনপুট: nums = [3,5,2,1,6,4]

আউটপুট: [3,5,1,6,2,4] (অন্যান্য বৈধ আউটপুটও সম্ভব)।

সমাধানের পদ্ধতি (Greedy Single Pass)

1. n = nums.size()।
2. i = 0 থেকে n-2 পর্যন্ত লুপ চালান:
   • যদি i জোড় (even) এবং nums[i] > nums[i+1] হয়, তবে সওয়্যাপ করুন।
   • যদি i বিজোড় (odd) এবং nums[i] < nums[i+1] হয়, তবে সওয়্যাপ করুন।
   • সামনে এটি এক লাইনে: if ((i % 2 == 0) == (nums[i] > nums[i+1])) swap(nums[i], nums[i+1])।
3. অ্যারে এখন wiggle সর্টেড।

এই গ্রিডি পদ্ধতিটি O(n) টাইম এবং O(1) স্পেসে কাজ করে।

C++ কোড উদাহরণ

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

void print_vector(vector<int> 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]);
            }
        }
    }
};

int main() {
    vector<int> v = {3,5,2,1,6,4};
    Solution ob;
    ob.wiggleSort(v);
    print_vector(v);
    return 0;
}

ইনপুট

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

আউটপুট

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