[알고리즘] 퀵정렬(Quick sort)

퀵정렬이란

• 찰스 앤터니 리처드 호어가 개발한 정렬 방법으로, 평균적으로 매우 빠른 정렬 방법이다.
• 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 분할 리스트를 다시 퀵정렬하는 전형적인 분할-정복법을 사용한다.
• 합병 정렬과 달리 리스트를 비균등하게 분할한다.

퀵정렬 수행 순서

• 리스트 안에 있는 한 원소를 피벗으로 선택한다.
• 피벗보다 작은 원소는 피벗의 왼쪽에, 피벗보다 큰 원소는 피벗의 오른쪽에 배치한다.
• 피벗을 제외하고 피벗의 왼쪽과 오른쪽을 2개의 부분집합으로 보고 이 두 부분집합에 대해서 위 방법을 반복한다.

피벗을 왼쪽 끝으로 할 경우의 퀵정렬 

1. 왼쪽 끝에서 움직이면서 크기를 비교하여 피벗보다 큰 원소를 찾아 low로 표시한다.
2. 오른쪽 끝에서 왼쪽으로 움직이면서 피벗보다 작은 원소를 찾아 high로 표시한다.
3. low와 high을 서로 교환한다.
4. low가 high보다 큰 인덱스값을 갖게 되면 두 원소를 교환하지 않는다. (이미 역전된 상태이기 때문에) 
5. 피벗과 high를 교환하고 원래 high였던 자리가 피벗이 된다.
6. 피벗을 기준으로 좌 우 2개의 부분집합이 생겼다. 이 부분집합에 대해 다시 위 과정을 수행한다.

분할: 정렬할 자료들을 기준 값을 중심으로 2개의 부분 집합으로 분할한다.

 

정복: 부분집합의 원소들 중에서 기준값보다 작은 원소들은 왼쪽 부분집합, 큰 원소들을 오른쪼 부분집합으로 정렬한다. 부분집합의 크기가 1 이하로 충분히 작지 않을 경우 재귀호출을 이용하여 다시 분할한다. 이처럼 분할-정복법을 사용한다.

 

퀵정렬 수행 과정

정렬되지 않은 {28, 30, 4, 1, 19, 8, 11}를 퀵정렬 방법으로 과정을 살펴보자.

 

피벗은 왼쪽을 기준으로 한다.

 

28	30	4	1	19	8	11
피벗	low					high

 

 

 

1. low가 오른쪽으로 이동하면서 피벗보다  원소를 찾는다.

28	30	4	1	19	8	11
피벗	low					high

 

30이 28보다 크므로 제자리에 있는다.

 

 

2. high가 왼쪽으로 이동하면서 피벗보다 작은 원소를 찾는다.

28	30	4	1	19	8	11
피벗	low					high

마찬가지로 11이 28보다 작으므로 제자리에 있는다.

 

 

3. low와 high 자리의 원소를 교환한다.

28	11	4	1	19	8	30
피벗	low					high

 

 

4. low가 오른쪽으로 피벗보다 큰 원소를 찾는다.

28	11	4	1	19	8	30
피벗						low, high

 

 

5. high가 왼쪽으로 피벗보다 작은 원소를 찾는다.

28	11	4	1	19	8	30
피벗					high	low

low의 자리가 high의 자리보다 커졌으므로 원소를 교환하지 않는다. 

 

 

6. 피벗과 high의 위치를 교환하고 원래 high의 위치를 피벗으로 설정한다.

8	11	4	1	19	28	30
					피벗	low

 

 

 

7. 피벗을 기준으로 부분집합이 만들어졌다. 이 두 부분집합에 대해 위 과정을 반복한다.

{ 8	11	4	1	19 }	28	{ 30 }

 

 

퀵정렬 코드

int partition(int list[], int left, int right){
    int pivot, temp;
    int low,high;
    
    low = left;     // left는 아래 right처럼 +1을 해주지 않는 이유는 맨 왼쪽 원소는 피벗이 되기 때문이다.
    high = right+1; // do를 먼저 실행하기 때문에 맨 오른쪽 원소를 비교하기 위해서는 +1을 해주어야 한다.
    pivot = list[left];
    
    do {
        do{
            low++;
        }while(low<=right &&list[low]<pivot);
        
        do{
        high--;
        }while(high>=left && list[high]>pivot);
        
        if(low<high){
            SWAP(list[low], list[high], temp);
        }
        
    } while(low<high);

    SWAP(list[left], list[high], temp); 
    return high;
}

 

partition 함수는 피벗을 설정하고 피벗을 기준으로 양쪽으로 부분집합을 만들어주는 역할을 한다.

 

 

void quick_sort(int list[], int left, int right){
	if(left<right){
		int q=partition(list, left, right);
		quick_sort(list, left, q-1); 
        quick_sort(list, q+1, right); 
	}
}

quick_sort 함수는 인자로 배열과 맨 왼쪽, 맨 오른쪽 인덱스를 받는다. 부분집합이 1개가 될 때까지 partition 함수를 수행한다.

 

퀵 정렬 복잡도 분석

• n개의 원소에 대해 n개의 메모리를 사용한다.
• 평균 시간 복잡도는 O(nlogn)이다.