EunSung.log

퀵 정렬

7 min read

개요

퀵 정렬Quick Sort은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘으로, 피벗pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 과정을 반복하는 정렬 방식이다. 평균적으로 매우 빠른 수행 속도를 자랑한다.

병합 정렬처럼 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할-정복법Divide and Conquer을 사용한다. 그러나 병합 정렬과는 달리, 퀵 정렬은 리스트를 비균등하게 분할한다.

동작

  1. 리스트에서 임의의 값을 하나 선택한다.
  2. 선택한 값(피벗)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮긴다.
  3. 피벗을 제외한 왼쪽과 오른쪽에 대해 위 과정을 재귀적으로 반복한다.

시간 복잡도

  • 최선의 경우:
  • 최악의 경우:
  • 평균적인 경우:

분석

최선의 경우

퀵 정렬에서 최선의 경우는 리스트가 항상 절반으로 나뉘는 경우다.

이 경우 분할은 총 번 이루어지고, 각각의 경우에서 평균 번 정도의 비교 연산이 필요하므로 의 시간 복잡도가 된다.

최악의 경우

퀵 정렬에서 최악의 경우는 피벗이 항상 최대값 혹은 최소값이어서, 리스트를 계속 개와 0개의 부분 리스트로 나누는 것이다.

이 경우 분할이 총 번 이루어지고, 각각의 경우에서 평균 번 정도의 비교 연산이 필요하므로 의 시간 복잡도가 된다.

피벗 선택 전략 - Median of Three

퀵 정렬은 리스트를 비균등하게 분할한다. 그리고 시간 복잡도 분석에서 알 수 있듯이, 리스트를 어떻게 나누냐에 따라 퀵 정렬의 효율이 결정된다. 바꿔 말해 피벗을 어떻게 선택하느냐에 따라 퀵 정렬의 효율이 좌우된다고 볼 수 있다.

예를 들어, 항상 리스트의 첫 번째 항목을 피벗으로 선택한다고 해보자.
그렇다면 이미 정렬된 리스트나 역순으로 정렬된 리스트에 대해서는 계속 개와 0개의 부분 리스트로 분할하게 된다. 이는 앞서 다룬 퀵 정렬에서의 최악의 경우다.

이를 피하기 위해 사용하는 피벗 선택 전략 중 하나가 ‘Median of Three’이다.

Median of Three는 피벗으로 리스트의 왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 중간값(median)을 선택하는 방법이다.

중간값을 계산하는 데에 추가 비용이 발생하긴 하지만, 앞서 말한 ‘최악의 경우’를 방지할 수 있다.

특징

  • 불안정 정렬이다.
  • 제자리 정렬이다.
  • 내부 정렬이다.
  • 시간 복잡도가 인 다른 정렬 알고리즘 중 가장 빠르다.
    • 이는 불필요한 데이터 이동을 줄이고, 먼 거리의 데이터를 교환하면서, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 등에 기인한다.

구현

public static class QuickSort {
	public static void sort(int[] array, int left, int right) {
		if (left < right) {
			int q = partition(array, left, right);
			sort(array, left, q - 1);
			sort(array, q + 1, right);
		}
	}
 
	private static int partition(int[] array, int left, int right) {
		int i = left; // 리스트 왼쪽 끝에서 시작
		int j = right + 1; // 리스트 오른쪽 끝에서 시작
		int pivot = array[left];
 
		while (true) {
			// 안쪽으로 이동하면서 피벗보다 큰 값을 찾음
			while (++i <= right && array[i] < pivot)
			// 안쪽으로 이동하면서 피벗보다 작은 값을 찾음
			while (--j >= left && array[j] > pivot)
 
			if (i >= j) // i, j가 엇갈렸다면 루프 종료
				break;
 
			int temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
 
		// pivot과 array[j] 교환
		int temp = pivot;
		pivot = array[j];
		array[j] = temp;
 
		return j; // 피벗 최종 위치 반환
	}
}

위 코드는 Median of Three를 사용하지 않았고, 호어가 처음 제안한 방식으로 퀵 정렬을 구현한 코드이다. (Hoare Partitioning)

이중 포인터(i, j)를 사용해 양 끝 쪽에서 안쪽으로 이동하며 값을 교환한다.

루프 종료 후 피벗과 array[j]를 교환하는 이유는 j가 피벗보다 작거나 같은 값들이 모이는 구간의 경계이기 때문이다.

Hoare Partitioning에서 루프는 포인터 i와 j가 교차하면 종료된다. 그러므로 루프 종료 시점의 리스트는 다음과 같다.

  • array[left] pivot
  • array[left + 1] ~ array[j] pivot
  • array[j + 1] ~ array[right] pivot
    그러므로 array[j]와 pivot을 교환해야 최종적으로 pivot을 기준으로 왼쪽은 pivot보다 작거나 같은 값들이, 오른쪽은 크거나 같은 값들이 모이게 된다.

참고문헌

백링크