[Algorithm] 퀵 정렬

1. 퀵 정렬: 분할 정복(divide and conquer) 정렬 방법 중 하나

  - 방법: 배열 a[m:n]의 한 원소를 pivot으로 선정 -> pivot 기준으로 두개의 파티션으로 분할(왼쪽: 작은 값 원소들, 오른쪽: 큰 값의 원소들) 

  - 시간 복잡도: O(nlogn)

  -  QuickSort Algorithm

quickSort(a[], m, n)
				// 배열 a의 부분 배열 a[m:n]을 오름차순 정렬
	if(m>=n) then return; // 정렬 원소 수가 0이거나 1일때는 복귀
    p = partition(a,m,n)  // p는 파티션이 끝난 뒤 사용된 pivot 인덱스
    quickSort(a[], m, p-1);
    quickSort(a[], p+1, n);

 ※ patition 알고리즘: 부분 배열 a[i:j]의 중앙 원소를 pivot 값을 정하고 왼쪽과 오른쪽 파티션으로 분할함

   - 과정:

 a[i: j]의 중앙 mid 인덱스 선정해 x를 분할 기준 값 pivot으로 정한다. (pivot = x)

 -> a[mid]의 원소 x와 a[]의 제일 왼쪽인 a[i] 원소인 y를 서로 교환

   - partition 알고리즘 

partition(a[], i, j)
	mid <- (i,j)/2;  // a[]의 중앙 인덱스
    pivot <- a[mid]; // a[]의 중앙 원소 값을 pivot으로 설정
    a[mid] <- a[i];  // a[i]와 a[mid]를 서로 교환
    a[i] <- pivot;   // a[i]는 pivot 값을 보관
    p <- i;			 // p는 두 파티션 경계 지시하는 인덱스
    for(k<-i+1; k<=j; k<-k+1) do {
    				// a[i]를 제외한 a[i+1: j]에 있는 모든 원소 a[k]를 검사
    	if(a[k]<pivot) then{
        	p <- p+1;		// p를 +1한 뒤 a[k]를 p인덱스 범위 안으로 포함되게 함
            temp <- a[p];
            a[p] <- a[k];
            a[k] <- temp;
        }
    }
    temp <- a[i];	// a[i]와 a[p]를 교환
    a[i] <- a[p];
    a[p] <- temp;
    return p;

2. 퀵 정렬 수행 과정

  - a = [3 1 4 5 9 8 7], 초기 배열 a[i: j], i=0, j=6일때

     ---- ----- 그림 정리 -----