Wiggle Sort

Subscribe Send me a message home page


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_0 \leqslant a_1 \geqslant a_2 \leqslant a_3 \geqslant a_4\) . There are two cases now:
  1. \(a_5\) is the maximum number
  2. \(a_5\) is no the maximum number

In the first case, we are all good. In the second case, for \(a_5\) is not the largest number, that number must be in \(a_0,a_1,...,a_4\) . On the other hand, according our assumption, the array \([a_0,a_1,…,a_4]\) is wiggle sorted. It follows that the largest number must be \(a_1\) or \(a_3\) . Without losing generality, let assume \(a_1\) is the largest number.

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 -----

Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png


Comments