퀵 정렬(Quick Sort)

퀵 정렬은 합병 정렬과 함께 대표적인 분할 정복 알고리즘 중 하나이다. 여기서 분할 정복 알고리즘이란 하나의 큰 문제를 여러 개의 작은 문제로 나누어 문제를 해결하는 알고리즘을 뜻한다. 퀵 정렬은 특정 값을 기준으로 작은 값과 큰 값을 나눈다. 이때의 기준값을 피벗(pivot)이라 한다. 예시를 통해 살펴보자.

예시

다음 숫자들을 오름차순으로 정렬하라.

1. 분할

오름차순으로 정렬하기 위해서는 피벗보다 작은 값은 피벗 왼쪽에 피벗보다 큰 값은 피벗의 오른쪽에 와야 한다. 그리고 이를 위해서 배열 양쪽에 포인터를 두고, 왼쪽 포인터는 피벗보다 큰 값이 나올 때까지 이동하고 오른쪽 포인터는 피벗보다 작은 값이 나올 때까지 왼쪽으로 이동하며 값을 교환한다.

 

아래 그림을 보면 왼쪽 포인터는 피벗보다 큰 값을 찾을 때까지 계속 오른쪽으로 이동하면서 8에서 멈추고, 오른쪽 포인터는 반대로 피벗보다 작은 값을 찾을 때까지 왼쪽으로 이동하다가 2에서 멈추게 된다. 이때 두 포인터에 위치한 값을 교환한다.

2. 분할 종료 시점

분할 종료 시점은 피벗을 기준으로 작은 값과 큰 값이 나눠질 때이다.

아래 그림을 보면 왼쪽 포인터는 이동하다가 7에서 멈춘다. 오른쪽 포인터는 피벗보다 작은 값을 찾기위해 이동하다가 왼쪽 포인터를 교차하게 된다. 이때 피벗보다 작은 값과 큰 값이 분리되었음을 확인할 수 있다. 마지막으로 피벗을 오른쪽 포인터의 값과 교환하면 피벗을 기준으로 분할이 완료된다

 

3. 재귀 호출

피벗은 이미 정렬된 상태이므로 피벗을 제외한 두 영역에 대해 재귀호출을 수행한다.

코드 구현

class Sort {
	private static void quickSort(int[] arr, int start, int end) {
    	// 분할할 영역이 한 개 이하인 경우
    	if (start >= end) {
        	return;
        }
        
        int pivot = arr[start]; // pivot을 첫 번째 값으로 설정한다.
        int left = start + 1; // 분할을 위한 왼쪽 포인터
        int right = end; // 분할을 위한 오른쪽 포인터
        
        while (left < right) { 
        	// pivot 보다 큰 값이 나타낼 때까지 우측으로 이동한다.
        	while (arr[left] < pivot) left++;            
            // pivot 보다 작은 값이 나타낼 때까지 좌측으로 이동하며, 
            // right가 left보다 작아진 경우는 분할 대상이 더이상 없는 경우이다.
            while (arr[right] > pivot && left < right) right--; 
            // 분할을 위해 서로 교환
            if (left < right) {
            	int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
    		}
        }
		arr[start] = arr[right];
		arr[right] = pivot;
        
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }
}

시간복잡도

퀵 정렬은 피벗의 선정 기준과 배열의 상태에 따라 최악의 경우 O(N^2)의 시간 복잡도를 가지며, 평균적으로 O(NlogN)의 시간복잡도를 가진다.