package algo;

import java.util.Arrays;

public class Quick {
    public static void main(String[] args) {
        Quick.sort(new int[] { 2, 4, 3, 5, 1, 6 });
    }

    public static void sort(int[] nums) {
        partition(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    public static void partition(int[] nums, int left, int right) {
        if (left < right) {
            int base = nums[left], i = left, j = right;
            while (i < j) {
                while (i < j && nums[j] >= base) {
                    j--;
                }
                if (i < j) {
                    nums[i] = nums[j];
                }
                while (i < j && nums[i] <= base) {
                    i++;
                }
                if (i < j) {
                    nums[j] = nums[i];
                }
            }
            nums[i] = base;
            partition(nums, left, i);
            partition(nums, i + 1, right);
        }
    }
}