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.
Read full article from Happy Coding: Wiggle Sort
No comments:
Post a Comment