Wiggle Sort

Wiggle Sort

Given an array, and re-arrange it to wiggle style in one pass.
i.e. [1] A0 >= A1 <= A2 >= A3 .... .... An.
      [2] A0 <= A1 >= A2 <= A3 .... .... An.

Solution: Greedy.

Look at each two neighbors from left to right, if they violate the rules, swap them. Continue until we are done.

Correctness: By induction.

Base case. The first two elements A0, A1 satisfy the rules, and A0 is in its desired position.

Suppose A0, .... Ak satisfy the rules, and A0, .... A(k-1) are in their desired positions. We want to show that when we consider the pair Ak and A(k+1), the rules are not violated, and the new k-th element will be in its desired position. Without loss of generality, assume that the k-th element should be higher than both of its neighbors. Two cases:

1) Ak > A(k + 1).
We are good in this case. Ak is its desired position, and no rules are violated so far.

2) Ak < A(k + 1).
We swap Ak and A(k + 1). Note that this does not violate A(k - 1), since A(k - 1) < Ak < A(k + 1). And the new k-th element (previous A(k + 1)) satisfies the rules, and is in its desired position.

So throughout the process, we do not violate any rules. The algorithm is correct.

Complexity: O(n).

Remarks:

If this array is sorted, then one only needs to directly (without checking the if() condition) swap each two neighboring elements.

Given [1, 2, 3, 4, 5, 6, 7, 8]:

For [1] A0 >= A1 <= A2 >= A3 .... .... An, we swap 1 and 2, 3 and 4, 5 and 6, 7 and 8. We get the desired wiggle-sorted order: [2, 1, 4, 3, 6, 5, 8, 7].

For [2] A0 <= A1 >= A2 <= A3 .... .... An, we swap 2 and 3, 4 and 5, 6 and 7. We get the desired wiggle-sorted order: [1, 3, 2, 5, 4, 7, 6, 8].

Code: See below for a code screenshot. Code link.

Output: 

[9, 1, 6, 2, 7, 3, 5, 4]

[1, 9, 2, 7, 3, 6, 4, 5]

Output interpretation:
[9, 1, 6, 2, 7, 3, 5, 4] is the wiggle sort type [1] of [6, 9, 1, 2, 5, 7, 3, 4].
[1, 9, 2, 7, 3, 6, 4, 5] is the wiggle sort type [2] of [9, 1, 6, 2, 7, 3, 5, 4].