Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]….

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4], another could be [3, 5, 1, 6, 2, 4].

Basically, A[0] <= A[1] >= A[2] <= A[3] >= A[4] <= A[5] Let’s look into the problem closely. We can see if two consecutive elements are in wiggle sort order i.e. A[i-1]<=A[i]>=A[i+1] then it’s neighbors are also in wiggle order. So we could actually check by even and odd positions –

A[even] <= A[odd],
A[odd] >= A[even].

Therefore we could go through the array and check this condition does not hold, just swap. Below is a o(n) implementation with swap only.

public static void wiggleSort(int a[]){
	for(int i = 0; i<a.length; i++){
		int odd = i&1;
		if(odd == 1){
			if(a[i-1]>a[i]){
				swap(a, i-1, i);
			}
		}
		else{
			if(i!=0 && a[i-1]<a[i]){
				swap(a, i-1, i);
			}
		}
	}
}

Wiggle Sort 2: no adjacent duplicates

Given an unsorted array nums, reorder it in-place such that nums[0] < nums[1] > nums[2] < nums[3]….

For example,
(1) Given nums = [1, 1, 1, 2, 2, 2], only possible answer is [1, 2, 1, 2, 1, 2].
(2) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(3) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Clearly the previous solution won’t work as we can’t put equal numbers in adjacent to each other. Then how do we solve this problem?

If we look into an example, let’s say a sorted array [1,2,3,4,5,6,7,8,9]. Then we can actually create a wiggle order by taking one element from lower half and one from higher half around the middle element. For example, around the median the array can be partitioned into 3 : lower part contains greater than median, middle part is equal to median, and right part contains less than median. Then we will see [9,8,7,6 5, 4,3,2,1]. Now if we take one element from each partition i.e one from middle, then one from left , and then one from right. For example, one possible solution could be : [5, 9, 4, 8, 3, 7, 2, 6, 1].

So, the idea is straightforward –

1. Find the median of the input array
2. 3-way partition the array around median so that left contains greater than median , middle contains equal to median, and right contains less than median.
3. Take one from each partition in the order of middle --> left --> right (as middle < left > right is wiggle order). 

Question is how to find the median efficiently? We can actually use QuickSelect algorithm to find median of an unsorted array in O(n) time. I discussed this approach in my previous post. So I’ll skip this.

Next, how to do the 3-way partitioning? This is similar to Dutch National Flag (DNF) Sorting problem I described in a previous here. The only difference is that the sort order is reversed i.e. we put greater element on left instead of right partition and vice versa. This will take O(n) time and O(1) space.

Next, how to get the final answer? If we are allowed to have extra O(n) memory then we could simply have an extra array where we put final result by taking elements from each partition in the order of middle, left, right. This is easy. But what if we asked for constant space solution? We need to do it in-place. How?

Note that in the previous step we are doing a 3-way partitioning (DNF Sort) by moving elements in proper partition using swapping. For example, reverse DNF order of [1,2,3,4,5,6,7,8,9] around median 5 is [9,8,7,6 5, 4,3,2,1]. But we need the final arrangement as [5, 9, 4, 8, 3, 7, 2, 6, 1]. Can we leverage the use of DNF swaps to put elements in the final order instead of intermediate DNF order during the DNF sort itself?

Here comes the fun part. We actually can do a wiggle sort in the shadow of DNF sort if we carefully map the index of DNF sort into index of wiggle sort. For example,

DNF order: [9,8,7,6  5,  4,3,2,1]
DNF Index: [0,1,2,3, 4,  5,6,7,8]

Wiggle order: [5, 9, 4, 8, 3, 7, 2, 6, 1]
Wiggle Index: [0, 1, 2, 3, 4, 5, 6, 7, 8]

Index Mapping: 
---------------
DNF --> Wiggle (value)
-----------------------
0 --> 1 (9)
1 --> 3 (8)
2 --> 5 (7)
3 --> 7 (6)
4 --> 0 (5)
5 --> 2 (4)
6 --> 4 (3)
7 --> 6 (2)
8 --> 8 (1) 

that is DNF(i) = WIGGLE((1+2*i)%n)

It is clear from the above mapping that we can map DNF index i to wiggle index (1+2*i)%n, where n = total numbers in the array. We can do a index mapping during DNF compare-and-sort operations and sue the mapped index instead of original index to do the swapping. This will yield the final wiggle sorted order in O(n) time and O(1) space. Below is the implementation of this algorithm.

public static void wiggleSort2(int[] nums){
	int mid = 0;
	//O(n) time and O(1) space quick select algorithm
	mid = kthSmallest(nums.clone(), 0, nums.length-1, (nums.length+1)>>1);
	
	class MappedIndex{
		int n;
		
		public MappedIndex(int n){
			this.n = n;
		}
		
		public int _(int i){
			return (1+2*i)%(n|1);
		}
	}
	
	
	MappedIndex idx = new MappedIndex(nums.length);
	int i = 0, j = 0, k = nums.length-1;
	//DNF sort -- O(n) time O(1) space
	while(j <= k){
		if(nums[idx._(j)] > mid){
			swap(nums, idx._(i++), idx._(j++));
		}
		else if(nums[idx._(j)] < mid){
			swap(nums, idx._(j++), idx._(k--));
		}
		else{
			j++;
		}
	}
	System.out.println("wiggle sort 2: "+Arrays.toString(nums));
}