public class  QuckSourtDemo
{
        public static void main(String[] args)
        {
               
                int[] list = {19,2,6,8,24,2,37,3,18};
                for(int a : list){
                        System.out.printf("%5d",a);
                }
                partistion(list,0,list.length-1);
                quckSort(list,0,list.length-1);
                System.out.println("\n========================!\n");
                for(int a : list){
                        System.out.printf("%5d",a);
                }

        }
       
        public static void quckSort(int[] list ,int first,int last){
                if(last > first){
                        int pivotIndex = partistion(list,first,last);
                        quckSort(list,first,pivotIndex-1);
                        quckSort(list,pivotIndex+1,last);
                }
        }

        public static int partistion(int[] list,int first ,int last){
                int pivot = list[first];
                int low = first +1;
                int high = last;


                while (high>low)
                {
                        while(low<=high && list[low]<=pivot){
                                low++;
                        }
                        //System.out.print(low);
                        while(low<=high && list[high] > pivot){
                                high--;
                        }
                        //System.out.print(high);
                        if(high > low){
                                int temp = list[high];
                                list[high] = list[low];
                                list[low]  = temp;
                        }
                }

                        while(high > first && list[high] >=pivot)
                        {
                                high--;
                        }

                        if(pivot > list[high]){
                                list[first] = list[high];
                                list[high] = pivot;
                                return high;
                        }else{
                                return first;
                        }
               
        }
}

public class  QuckSourtDemo
{
        public static void main(String[] args)
        {
               
                int[] list = {19,2,6,8,24,2,37,3,18};
                for(int a : list){
                        System.out.printf("%5d",a);
                }
                partistion(list,0,list.length-1);
                quckSort(list,0,list.length-1);
                System.out.println("\n========================!\n");
                for(int a : list){
                        System.out.printf("%5d",a);
                }

        }
       
        public static void quckSort(int[] list ,int first,int last){
                if(last > first){
                        int pivotIndex = partistion(list,first,last);
                        quckSort(list,first,pivotIndex-1);
                        quckSort(list,pivotIndex+1,last);
                }
        }

        public static int partistion(int[] list,int first ,int last){
                int pivot = list[first];
                int low = first +1;
                int high = last;


                while (high>low)
                {
                        while(low<=high && list[low]<=pivot){
                                low++;
                        }
                        //System.out.print(low);
                        while(low<=high && list[high] > pivot){
                                high--;
                        }
                        //System.out.print(high);
                        if(high > low){
                                int temp = list[high];
                                list[high] = list[low];
                                list[low]  = temp;
                        }
                }

                        while(high > first && list[high] >=pivot)
                        {
                                high--;
                        }

                        if(pivot > list[high]){
                                list[first] = list[high];
                                list[high] = pivot;
                                return high;
                        }else{
                                return first;
                        }
               
        }
}