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 << ", ";
  }

Last updated