package Sort;

public class QuickSort {
	public static void main(String[] args){
    	int[] list={0,5,9,2,6,8,1,4};
    	quickSort(list);
    	for(int i=0;i<list.length;i++){
    		System.out.print(list[i]+"¡¡");
    	}
    }
	
	public static  void quickSort(int[] list){
	    quickSort(list,0,list.length-1);
	}
	
	private static  void quickSort(int[] list,int first,int last){
		if(last>first){
			int index=partition(list,first,last);
			quickSort(list,first,index-1);
			quickSort(list,index+1,last);
		}
	}
	
	private static int partition(int[] list,int first,int last){
		int pivot=list[first];
		int low=first+1;
		int high=last;
		
		while(high>low){
			while(list[low]<=pivot&&low<=high&&low<list.length-1){
				low++;
			}
			while(list[high]>pivot&&low<=high&&high>0){
				high--;
			}
			if(high>low){
				int temp=list[low];
				list[low]=list[high];
				list[high]=temp;
			}
		}
		
		while(high>first&&list[high]>=pivot){
			high--;
		}
		
		if(pivot>list[high]){
			list[first]=list[high];
			list[high]=pivot;
			return high;
			
		}
		else
			 return first;
	}
}