wave_array.cpp

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


 // } Driver Code Ends
class Solution{
    public:
    // arr: input array
    // n: size of array
    //Function to sort the array into a wave-like array.
    void convertToWave(vector<int>& arr, int n){
        
        map <int,int> mp;
        for(int i=0;i<n;i++)
        {
            mp[arr[i]]++;
        }
        vector <int> ans;
        auto it=mp.begin();
        while(it!=mp.end())
        {
            while(it->second>0)
            {
                ans.push_back(it->first);
                it->second--;
            }
            it++;
        }
        for(int i=1;i<n;i+=2)
        {
            int temp=ans[i];
            ans[i]=ans[i-1];
            ans[i-1]=temp;
        }
     
        for(int i=0;i<n;i++)
        {
           arr[i]=ans[i];
        }
    }
};

// { Driver Code Starts.

int main()
{
    int t,n;
    cin>>t; //Input testcases
    while(t--) //While testcases exist
    {
        cin>>n; //input size of array
        vector<int> a(n); //declare vector of size n
        for(int i=0;i<n;i++)
            cin>>a[i]; //input elements of array
        Solution ob;
        ob.convertToWave(a, n);

        for(int i=0;i<n;i++)
            cout<<a[i]<<" "; //print array
            
        cout<<endl;
    }
}  // } Driver Code Ends