Google Interview - Wiggle Sort

Write a function to convert the array into alternate increasing decreasing numbers:

a[0] <= a[1] >= a[2] <= a[3] >=...

Note: You should solve it in place and one pass.

 

Solution 1:

public void wiggle_sort(int[] arr) {
    int n = arr.length;
    if(n <= 1) return;
    boolean inc = true;
    int prev = arr[0];
    for(int i=1; i<n; i++) {
        if((inc && prev <= arr[i]) || (!inc && prev >= arr[i])) {
            arr[i-1] = prev;
            prev = arr[i];
        } else {
            arr[i-1] = arr[i];
        }
        inc = !inc;
    }
}

 

Solution 2:

void wiggle_sort(vector<int>& arr) {  
    if(arr.size() < 2) return;  
    int flag = 1;  
    int prev = arr[0];  
    for(int i=1; i<arr.size(); i++) {  
        if(prev*flag <= arr[i]*flag) {  
            arr[i-1] = prev;  
            prev = arr[i];  
        } else {  
            // arr[i-1] = arr[i];  
            swap(arr[i-1], arr[i]);  
        }  
        flag = -flag;  
    }  
}  

 

Reference:

http://www.mitbbs.com/article_t1/JobHunting/32575573_0_1.html 

http://www.fgdsb.com/2015/01/20/special-sorting/