Quick Sort

퀵 정렬이란?
 - 퀵 정렬(Quick Sort)은 정렬할 전체 값들을 정렬을 수행하지 않고 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다.
 - 왼쪽 부분 집합에는 기준값보다 작은 원소들을, 오른쪽 부분집합에는 기준값보다 큰 원소들을 이동.
 - 이 때 사용하는 기준값 = Pivot(피봇) 이라고 칭한다.
*퀵 정렬의 핵심
 1) 분할 : 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할한다.
 2) 정복 : 기준보다 작은 값은 왼쪽, 기준보다 큰 값은 오른쪽 부분집합으로 정렬, 부분집합의 크기가 1 이하가 아니면 순환 호출을 이용해 다시 분할.
*퀵 정렬 방법 
Pivot을 중심으로 L 과 R 값을 지정해준다. L은 Pivot보다 큰 값, R은 Pivot보다 작은 값을 지정한다. 두 개 모두 선택됐다면 자리교환을 해주면 된다.
만약 한쪽이 선택된 L이나 R이 없다면 선택된 값과 Pivot을 교환하도록 한다.
* 퀵 정렬의 시간 복잡도
퀵 정렬 알고리즘에서 실행 성능은 Pivot에 의해 결정된다. 성능이 가장 좋은 경우는 정확히 n/2로 나뉘었을 때 이다. 
이 때, 최소이기 때문이다. 반대로 n, n-1개로 나뉠 경우 한 쪽으로 치우쳐 수행 단계가 최대로 올라갈 경우 실행 성능이 최저로 떨어진다. 
평균 시간 복잡도는 아래와 같다.
O(nlog₂n)

package Sort;

import java.util.Arrays;

public class Quick_Sort {
	static int partition(int[] array,int start, int end) {
		int pivot = array[(start+end)/2]; 
		while(start<=end) { 
			while(array[start]<pivot) start++; 
			while(array[end]>pivot) end--; 
			if(start<=end) { 
				int tmp = array[start]; 
				array[start]=array[end]; 
				array[end]=tmp; start++; 
				end--;
				} 
			} 
		return start;
		} 
	static int[] quickSort(int[] array,int start, int end) { 
		int p = partition(array, start, end); 
		if(start<p-1) 
			quickSort(array,start,p-1); 
		if(p<end) 
			quickSort(array,p,end); 
		return array; } 
	public static void main(String[] args) { 
		int[] array = {4,2,3,5,9}; 
		array = quickSort(array,0,array.length-1); 
		System.out.println(Arrays.toString(array)); }


}