public class Main {

    public static void main(String[] args) {
        System.out.println("Hello World!");
        int[][] arraysToSort = {{9, 0, -2, 89, 1, 2, 3, -3, -99, 6},
                {5, 3, 1, 2, 2, 1, 0},
                {1, 1},
                {3, 1, 1},
                {2, 1, 1, 2, 1, 2},
                {2, 5, 3, 1},
                {-1, 3, 2, 4, 0, 1},
                {-1, 0}
        };
        for (int i = 0; i < arraysToSort.length; i++) {
            int[] arrayToSort = arraysToSort[i];
            quickSort(arrayToSort,0,arrayToSort.length-1);
            printArray(arrayToSort);
        }
    }

    private static void printArray(int[] arrayToSort) {
        System.out.println("Start");
        for (int index = 0; index < arrayToSort.length; index++) {
            System.out.print(arrayToSort[index] + " ");
        }
        System.out.println("\nEnd");
    }

    private static void quickSort(int[] array,int start, int end) {
        if (start >= end)
            return;
        int i = start, j = end;
        int cur = i - (i - j) / 2;
        while (i < j) {
            while (i < cur && (array[i] <= array[cur])) {
                i++;
            }
            while (j > cur && (array[cur] <= array[j])) {
                j--;
            }
            if (i < j) {
                swapItems(array,i,j);
                if (i == cur)
                    cur = j;
                else if (j == cur)
                    cur = i;
            }
        }
        quickSort(array,start, cur);
        quickSort(array,cur+1, end);
    }

    private static void swapItems(int[] array, int start, int end) {
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
    }
}