# 280 Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void wiggleSort(vector<int> *wiggleIt)
{
int size = (*wiggleIt).size();
sort((*wiggleIt).begin(), (*wiggleIt).end()); // lazy :(
// if even, ignore last element to make this alg simpler
int temp = (*wiggleIt).at(size - 1);
if (size % 2 == 0) (*wiggleIt).erase((*wiggleIt).begin()+size-1);
for (int i = 1; i < size - 1; i+=2) iter_swap((*wiggleIt).begin() + i, (*wiggleIt).begin() + i + 1);
if (size % 2 == 0) (*wiggleIt).insert((*wiggleIt).end(), temp);
}
int main()
{
vector<int> wiggleIt{ 29, 45, 2, 37, 11,
64, 80, 9, 68, 38,
85, 46, 22, 5, 39,
11, 51, 1, 45, 7 ,
27, 65, 5, 83, 92,
99, 33, 50, 28, 42,
99, 56, 59, 3, 73,
50, 86, 88, 4, 22,
59, 29, 47, 87, 71,
16, 56, 72, 48, 65,
86, 19, 8, 88, 70,
30, 66, 20, 10, 97,
68, 30, 62, 2, 72,
41, 3, 57, 87, 99,
94, 77, 49, 25, 52,
1 , 66, 34, 61, 86,
49, 4, 53, 77, 5 ,
87, 29, 18, 75, 48,
19, 80, 7, 16, 22,
58, 68, 37, 77, 56 };
wiggleSort(&wiggleIt);
for (auto i : wiggleIt) cout << i << ", ";
}