package com.interview.array;

import java.util.Arrays;

/**
 * Date 03/23/2016
 * @author Tushar Roy
 *
 * Convert an unsorted array into an array of form num[0] < num[1] > nums[2] < num[3]....
 * 
 * Time complexity O(n) - This depends on KthElementInArray time
 * Space complexity O(1)
 *
 * https://leetcode.com/problems/wiggle-sort-ii/
 */
public class WiggleSort {

    public void wiggleSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }
        int k = arr.length/2;
        KthElementInArray kthElementInArray = new KthElementInArray();
        kthElementInArray.kthElement(arr, k);

        int mid = arr[k];
        int n = arr.length;
        int i = 0, j = 0;
        k = n - 1;
        while (j <= k) {
            if (arr[next(j, n)] > mid) {
                swap(arr, next(i++, n), next(j++, n));
            }
            else if (arr[next(j, n)] < mid) {
                swap(arr, next(j, n), next(k--, n));
            }
            else {
                j++;
            }
        }
    }

    private int next(int index, int n) {
        return (2*index + 1) % (n | 1);
    }

    private void swap(int arr[],int low,int high){
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

    public static void main(String args[]) {
        WiggleSort ws = new WiggleSort();
        int input[] =  {6, 2, 1, 6, 8, 9, 6};
        ws.wiggleSort(input);
        System.out.print(Arrays.toString(input));
    }
}

@@ -284,16 +284,62 @@
 O(1)%0A *%0A
+ * https://leetcode.com/problems/wiggle-sort/%0A
  * https
@@ -1069,32 +1069,293 @@
        %7D%0A    %7D%0A%0A
+    public void wiggleSort1(int%5B%5D nums) %7B%0A        for (int i=1; i%3Cnums.length; i++) %7B%0A            int a = nums%5Bi-1%5D;%0A            if ((i%252 == 1) == (a %3E nums%5Bi%5D)) %7B%0A                nums%5Bi-1%5D = nums%5Bi%5D;%0A                nums%5Bi%5D = a;%0A            %7D%0A        %7D%0A    %7D%0A%0A
     private int 

add another version of wiggle sort