#### Description

Given an unsorted array nums, reorder it in-place such that:nums[0] \(\leqslant\) nums[1] \(\geqslant\) nums[2] \(\leqslant\) nums[3] …

#### Excample

Given nums = [3,5,2,1,6,4], one possible answer is [1,6,2,5,3,4]#### Solution

This problem has a very straighforward solution. We start from the index 1 and check if the current number in that index satisfies the condition. If not, we swap that number and the the number before it.Here is the code

```
class Solution:
"""
@param: nums: A list of integers
@return: nothing
"""
def wiggleSort(self, nums):
# write your code here
for i in range(1, len(nums)):
if i % 2 == 0:
if nums[i] > nums[i - 1]:
self.swap(nums, i, i-1)
if i % 2 == 1:
if nums[i] < nums[i-1]:
self.swap(nums, i, i-1)
def swap(self, nums, i, j):
nums[i],nums[j] = nums[j], nums[i]
```

The question is why this method works? In fact, we can prove it by induction.**Proof.**It is easy to check the approch works for n=1,2. for n = 3, we note that after two passes, the maximum number is at index 1, hence the array is wiggle sorted.

Now, assume the approach works for array of size less than or equal to n and we prove it also works for n+1. For simplicity, we will work on a concrete example and let n = 5.

The index starts from 1. When it arrives at index 4, we have

- \(a_5\) is the maximum number
- \(a_5\) is no the maximum number

In the first case, we are all good. In the second case, for

Now take a look at state of array when the index was 2. It is equivalent to start a new sort for array \([a_1,a_2,…,a_5]\) and the array \([a_0,a_1]\) is already sorted. Because we have a_1 be the largest number, when we starts sorting \([a_1,a_2,…,a_5]\), we will not change the position of a_1. Now we finish the proof by observing that size of array \([a_1,a_2,…,a_5]\) is n and by induction we know after the process is finished, \([a_1,a_2,…,a_5]\) will be wiggle sorted.

\( \square \)

----- END -----

©2019 - 2021 all rights reserved

## Comments