퀵 정렬(Quick Sort)

이번에 배워볼 정렬 알고리즘은 퀵 정렬(Quick Sort)이다.

퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬도 앞서 배운 합병 정렬처럼 분할 정복(Divide and Conquer) 방법에 근거한다.

하지만 합병 정렬은 항상 리스트를 절반으로 균등하게 나누는 반면에, 퀵 정렬은 피벗(Pivot)이라는 것을 사용하여 비균등하게 분할한다.

피벗을 기준으로 좌측에는 크기가 작은 요소, 우측에는 크기가 큰 요소들을 옮기면서 분할한다. Mid를 기준으로 좌, 우측으로 분할하는 합병 정렬과 조금 차이가 있다.

피벗을 기준으로 분할된 상태에서 피벗을 제외한 좌측, 우측 요소들을 정렬하면 정렬된 리스트를 얻게 된다. 그럼 퀵 정렬은 분할된 상태에서 어떤 방법으로 리스트를 정렬할까? 피벗의 위치를 어디에 잡느냐에 따라 조금 달라지지만 여기선 첫 번째 요소를 피벗으로 잡고 설명하겠다.

 

첫 번째 요소가 피벗이므로 고정해두고, 두 번째 요소를 가리키는 Low, 마지막 요소를 가리키는 High, 총 2개의 추가적인 변수를 사용한다.

Low는 왼쪽 부분 리스트를 만드는 데 사용되고, High는 오른쪽 부분 리스트를 만드는데 사용된다. Low는 피벗이 가리키는 요소보다 큰 요소를 만나면 가리키도록 하고, High는 피벗이 가리키는 요소보다 작은 요소를 만나게 되면 가리키도록 한다.

두 변수가 요소를 가리키게 된다면 두 요소는 적합한 위치가 아니기 때문에 교환한다. 이 과정을 Low와 High가 서로 엇갈리기 전까지 진행한다. 엇갈리는 순간 피벗이 가리키는 요소와 High가 가리키는 요소를 교환한다. 이렇게 되면 피벗이 가리키는 요소를 기준으로 좌측은 피벗보다 작은 요소들, 우측은 피벗보다 큰 요소들이 놓이게 된다.

 

위 과정을 반복하여 합병 정렬처럼 빠른 시간 내에 정렬된 리스트를 얻을 수 있다. 다만 퀵 정렬은 이미 정렬된 리스트인 경우 상당히 느린 정렬 속도를 가진다.

퀵 정렬(Quick Sort)의 시간 복잡도는 O(N logN)이다.
다만, 리스트가 이미 정렬되어 있는 상태라면 O(N^2)의 시간 복잡도를 가진다.

 

그럼에도 불구하고 평균적으로 퀵 정렬은 합병 정렬보다도 빠른 속도를 가진다. 또한, 추가적인 메모리를 필요로 하지 않기 때문에 메모리 상에서도 장점이 있다. 피벗에 따른 불균형 분할 때문에 정렬된 리스트에서는 수행 시간이 더 많이 걸리는 등의 단점이 있다.

이를 개선하기 위해 피벗을 선택할 때 단순히 리스트의 왼쪽 데이터를 사용하는 대신에 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택하도록 한다. 많이 사용되는 방법은 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값(Median)을 피벗으로 선택하는 것이다. 일반적으로 리스트의 왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 크기순으로 중간 값을 선택하는 방법(Median of Three)이 많이 사용된다.

​

퀵 정렬을 Java로 구현한 코드는 다음과 같다. 첫 번째 요소를 피벗으로 설정하였다.

public class Main {

	public static void main(String[] args) {
		int[] arr = {5,3,7,2,8,6,4,1};

		quick_Sort(0, arr.length - 1, arr);

		for (int a : arr) {
			System.out.print(a+" ");
		}
	}

	public static void quick_Sort(int left, int right, int[] arr) {
		if (left >= right) return;
		
		int pivot = left;
		int low = left + 1;
		int high = right;
		int temp;
		
		while (low <= high) {
			//좌측부터 시작해서 피벗보다 큰 값을 찾음
			while (low <= right && arr[low] < arr[pivot]) {
				low++;
			}
			
			//우측부터 시작해서 피벗보다 작은 값을 찾음
			while (high > left && arr[high] >= arr[pivot]) {
				high--;
			}
			
			if (low > high) { //엇갈렸으면 피벗과 high 교환
				
				temp = arr[high];
				arr[high] = arr[pivot];
				arr[pivot] = temp;
			} else { //엇갈리지 않았으면 low와 high 교환	
				temp = arr[low];
				arr[low] = arr[high];
				arr[high] = temp;
			}
		}
		
		//분할된 배열을 다시 분할 및 정렬
		quick_Sort(left, high - 1, arr);
		quick_Sort(high + 1, right, arr);
	}
}