Wiggle Sort

Given an array, and re-arrange it to wiggle style in one pass.

Example

• [1] A0 >= A1 <= A2 >= A3 .... .... An

• [2] A0 <= A1 >= A2 <= A3 .... .... An

Think

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

Suppose , .... satisfy the rules, and , .... are in their desired positions. We want to show that when we consider the pair and , 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) > . We are good in this case. is its desired position, and no rules are violated so far.

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

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

Solution

public void wiggleSort(int[] arr, boolean swither){
    int idx = 0;
    while(idx < arr.length - 1){
        if((switcher && arr[idx] < arr[idx + 1])||(!switcher && arr[idx] > arr[idx + 1])){
            int tmp = arr[idx];
            arr[idx] = arr[idx + 1];
            arr[idx+1] = tmp;
            switcher ^= true;
        }
      idx ++;
    }
}