# Short simple C++

• ``````void wiggleSort(vector<int>& nums) {
vector<int> sorted(nums);
sort(sorted.begin(), sorted.end());
for (int i=nums.size()-1, j=0, k=i/2+1; i>=0; i--)
nums[i] = sorted[i&1 ? k++ : j++];
}
``````

Sort and then write the smaller half of the numbers on the even indexes and the larger half of the numbers on the odd indexes, both from the back. Example:

``````Small half:    4 . 3 . 2 . 1 . 0 .
Large half:    . 9 . 8 . 7 . 6 . 5
----------------------------------
Together:      4 9 3 8 2 7 1 6 0 5
``````

So write `nums` from the back, interweaving `sorted[0..4]` (indexed by `j`) and `sorted[5..9]` (indexed by `k`).

For more explanation/proof, see my equivalent Python solution.

• It's computationl complexity is O(n*log(n)) because of the using of sort, not O(n).

• @lijianhui
I know. So what? I never claimed it's O(n).

• I came up with exactly the same idea. But your codes are neater than mine (I used two "for" loops to put two sorted halfs back in nums). Good codes,

• Well I'm sure two loops can be good as well. I'd just find it boring :-P

• I wanted to use exactly this idea when I was doing Wiggle Sort I, but then I dumped it since time complexity is O(nlogn) and space complexity is also not O(1)... And I hate the complicated solution to this problem... Oh Jesus

• nice and clean code

• This post is deleted!

• can you explain why you modify elements from the end instead from the begin?

• @StefanPochmann said in Short simple C++:

for (int i=nums.size()-1, j=0, k=i/2+1; i>=0; i--)
nums[i] = sorted[i&1 ? k++ : j++];

I got it now. didn't find @StefanPochmann 's explain link earlier.
For some guys make the same mistake as mine, here's a head up.
Stefan's insert order makes the middle consecutive two same number M.
Large half M go way back to end but small half M go front. Very clever!

As a tip here to help anyone has the same problem as mine, go check Stefan's link up there.

/////
previous post below
////
Hello, I take the same idea as yours instead of putting value from i==size-1, I start i from 0.
Input:
[4,5,5,6]
Output:
[4,5,5,6]
Expected:
[5,6,4,5]

Does it mean it better assigning value as your order from end to begin? And may I ask what make you choose this order? Thank you!

``````class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> sorted(nums);
sort(sorted.begin(), sorted.end());
//len=1 0
//1
//len=2 0(1)
//
//len=4 01(2)3
//
//len=5 012(3)4
//(len+1)/2=3
//len=6 012(3)45
//(len+1)/2=3
//len=7 0123(4)56
//len+1)/2=4

//[4,5,5,6]
/*
for (int i=nums.size()-1{3}, j=0, k=i/2+1{2}; i>=0; i--){
nums[i] = sorted[i&1 ? k++ : j++];
}*/
//[  [1]5 ,[3]6 ,[0]4, [2]5 ]
/*
for(int i=(nums.size()-1), j=0, k=(nums.size()+1)/2;i>=0;i--){
//cout<<(i&1)<<"j="<<j<<"k="<<k<<endl;
nums[i]= ((i&1)==0)? sorted[j++] : sorted[k++];
//cout<<(i&1)<<"j="<<j<<"k="<<k<<endl;
}*/
for(int i=0, j=0, k=(nums.size()+1)/2;i<nums.size();i++){
nums[i]= ((i&1)==0)? sorted[j++] : sorted[k++];
}

}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.