import java.util.Arrays;
import java.util.Random;

public class TestSort1 {
    public static int partition1(int[] array,int start,int end) {
        int tmp=array[start];
        while(start<end) {
            while(start<end && array[end]>=tmp) {
                end--;
            }
            array[start]=array[end];
            while (start<end && array[start]<=tmp) {
                start++;
            }
            array[end]=array[start];
        }
        array[start]=tmp;
        return start;
    }
    public static void quick(int[] array,int left,int right) {
        if(left>=right) {
            return;
        }
        int pivot=partition1(array,left,right);

        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    public static void quickSo(int[] array) {
        quick(array,0,array.length-1);
    }

    public static void main(String[] args) {
        int[] array = {6,2,1,5,9};
        System.out.println(Arrays.toString(array));
        quickSo(array);
        System.out.println(Arrays.toString(array));
    }
}