//Create by Inho 2018. 4. 2. 오후 6:44:24
//퀵정렬
/***
* 시간 복잡도 최악O(n^2), O(nlogn)
* 데이터 가운데서 하나의 원소를 고름(pivot 선정)
* povot 앞에는 pivot보다 작은 값이 오고, pivot 뒤에는 pivot보다 큰 값들이 오도록 둘을 분할한다.
* 분할된 두 개의 데이터에 대해 재귀함수를 통해 이 과정을 반복한다.
*/
public class Study_quick_sort {
	public static void main(String[] args) {
	
		Study_quick_sort study = new Study_quick_sort();
		
		int data[] ={5,4,3,2,1,11};
		
		study.sort(data,0,data.length-1);
		
		for (int i = 0; i < data.length; i++) {
			System.out.println("data["+i+"] : "+data[i]);
		}
	}
	
	
	public void sort(int[] data,int l, int r){
		int left = l;
		int right = r;
		int pivot = data[(l+r)/2];
		do{
			while(data[left] < pivot) left++;
			while(data[right] > pivot) right--;
			if(left <= right){
			int temp = data[left];
			data[left] = data[right];
			data[right] = temp;
			left++; right--;
			}
		}while(left <= right);
			
				if(l < right) sort(data,l,right);
				if(r > left) sort(data,left,r);
	}	
}