(자료구조) 퀵 정렬(Quick Sort)

● 퀵 정렬(quick sort) 이란
‘  찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘
   퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.
   분할 정복 알고리즘(Divide and Conquer)의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법

● 퀵정렬 : 정렬 방법 정리
  분할 정복(Divide Conquer)을 활용한 순환호출로 구현한다.
 ○  퀵정렬 과정
    1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
    2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고

      피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮긴다. 
    3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
    4. 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.(부분 리스트에서도 피벗을 선출)
    5. 리스트의 크기가 0이나 1이 될 때까지 반복한다.

 

● 퀵 정렬 : 이해를 위한 변수중심의 코드 구현  방식 설명 

   ※ 변수 정의 
   - left : 정렬대상의 왼쪽 지점
   - right : 정렬대상의 오른쪽 지점
   - pivot : 중심축 지점
   - low : 피벗을 제외한 가장 왼쪽에 위치한 지점
   - high : 피벗을 제외한 가장 오른쪽에 위치한 지점
  (※ 코드의 구현은 left (최좌측 리스트)를 Pivot 으로 지정)

 

 ○ low와 high 는 Pivot 을 기준으로 해당 위치를 움직이는 Index 이다. 
       - low는 오른쪽으로 이동 -> 피벗보다 큰값을 만날 때까지 low Index 는 증가 
       - high는 왼쪽으로 이동 -> 피벗보다 작은 값을 만날 때까지 high Indext 는 감소 

 ○ low와 high 의 Index 조건이 알맞게 되면 해당 위치 리스트들을 swap 한다. 

 ○ 해당 반복은 high와 low가 index가 역전되면 멈추게 된다.

 ○ high와 low가 역전되면, 피벗과 high의 데이터 교환한다. 

 ○ 피봇위치를 기점으로 두개의 영역으로 나누어 반복 실행한다.

 

● 구현

 ○ 퀵 정렬 Partition Function 

int Partition(int arr[],int left,int right){
    int pivot = arr[left];
    int low = left+1;
    int high = right;
    while(low <=high){
    	// pivot이 더 크면 증가 
    	while(pivot >= arr[low]&&low<=right)  //&& 이후는 정렬 범위 명확히 하기위한 조건식
        	low++;
        // pivot이 더 작으면 감소
        while(pivot <= arr[high]&& high>=(left+1))
        	high--;

        if(low <= high)
        	Swap(arr,low,high);
    }
    Swap(arr,left,high);
    return high; // 다음 partition 반환
}

 ○ 퀵 정렬 Quick Sort Function

void QuickSort(int arr[],int left,int right){
	// left 가 right 보다 작을때까지 호출하는 이유는 호출시 pivot의 +-1 씩하기 때문,,,
    if(left<=right){
        int pivot = Partition(arr,left,right);
        QuickSort(arr,left,pivot-1); // pivot 을 기점으로 재귀 호출 (좌)
        QuickSort(arr,pivot+1,right); // pivot 을 기점으로 재귀 호출 (우)
    }
}

● 피벗 선택에 대한 논의
   가급적 중간에 해당하는 값이 선택되면 좋은 성능을 보인다.
   배열의 3개 값중 중간값을 골라서 PIVOT 으로 선정하면 성능적으로 좋은 모습을 보임.

● 퀵 정렬: 성능평가(최선의 경우)

○ 최상 및 평균의 경우(Best & Average Case)
   PIVOT 을 기점으로 순환 호출의 깊이 : log2n 
   n번의 비교연산이 필요하다.(left 와 right)  : n

   big-oh : O(nlog2n)

○ 최악의 경우(Worst Case) 
    둘로 나뉘는 횟수가 : 약 n
    매 단계별 비교 연산의 횟수 : 약 n
    big-oh : O(n^2)