Wiggle Sort

Wiggle Sort!?

All my readers must’ve found the name of today’s problem very funny. However, it is a very smart problem that tests our understanding of a varied range of concepts.

Let us jump straight to the problem without any further confusion.

Example

You have an array

Input: [1,5,1,6,4]

Expected Output : [1,6,4,1,5]

How?

As for wiggle sorting:

The array’s elements shall be ordered such that arr[0]<arr[1]>arr[2]<arr[3] and so on in wiggle sort.

Approach

I will go on the approach I find the easiest. Taking into consideration the following example

Array:[1,5,1,1,6,4]

Let us make a copy of that array and sort it

Blue: Original array Red: Sorted Copy array

Length of the array: 6

Let us place the smaller elements from the copy array to the original array.

The original array after copying the small elements

Now. Let us place the larger elements into the leftover places

Voila. The array has wiggle sorted!

We would change the passes a bit for an array containing the odd number of elements.

Let us look into it.

We would start from the last element instead of the second last one.

After the first pass

We now put the greater elements

A similar problem we have with us can be checked on to gain a good understanding.

Now that we have understood it. Let’s get to the code

Java Code for wiggle sort

class Solution 
{
    int index=0;
    public void assemble(int[] nums,int copy[],int start)
    {
        //The assemble function 
        for(int i=start;i>-1;i=i-2)
        {
            nums[i]=copy[index];
            index++;
        }
    }
    public void wiggleSort(int[] nums) 
    {
        int copy[]=new int[nums.length];
        for(int i=0;i<nums.length;i++)
            copy[i]=nums[i];
        Arrays.sort(copy);
        if(nums.length%2==0)
        {
            assemble(nums,copy,nums.length-2);
            assemble(nums,copy,nums.length-1);
        }
        else
        {
            assemble(nums,copy,nums.length-1);
            assemble(nums,copy,nums.length-2);
        }
    }
}

C++ Code for wiggle sort

class Solution 
{
    public:
    int index=0;
    public:
    void assemble(vector<int>& nums,vector<int>& copy,int start)
    {
        int i=0;
        for(i=start;i>-1;i=i-2)
        {
            nums[i]=copy[index];
            index++;
        }
    }
    public:
    void wiggleSort(vector<int>& nums) 
    {
        vector<int>copy(nums);
        sort(copy.begin(), copy.end());
        if(nums.size()%2==0)
        {
            assemble(nums,copy,nums.size()-2);
            assemble(nums,copy,nums.size()-1);
        }
        else
        {
            assemble(nums,copy,nums.size()-1);
            assemble(nums,copy,nums.size()-2);
        }
    }
};

Complexity Analysis for wiggle sort

Time Complexity For Above Problem=O(n log n)

Space Complexity For Wiggle Sorting by the above method=O(n)

How?

• The sort operation used is the inbuilt merge sort with time complexity of O(n logn)
• In each call to the assemble function
  • We run over the alternate elements and accordingly put them from the copy to the original array
• We thus, in a way go over each and every element in the array until the elements are all put in place
• Moving to the array gives a time complexity of O(n)
• However, the sort operation, in this case, turns out to be more expensive bringing the time complexity to O(n logn)
• As we created a copy array with the elements.The space complexity zeros on to O(n) i.e linear