Wiggle Sort

Difficulty Level Medium
Sorting

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