[정렬]06.퀵 정렬

1. 기본 컨셉

 - 병합 정렬과 마찬가지로 분할/정복 알고리즘에 기반한 정렬 방식

 - 요소를 분할할 원소인 pivot을 선정

 - pivot보다 작은 값은 왼쪽, pivot보다 큰 값은 오른쪽에 오도록 재배치해서 분할

 - 분할된 두 개의 리스트에 대해 재귀 함수를 통해 과정 반복

 - 시간 복잡도는 worst case가 O(n^2),  평균 O(nlogn)인데 무려 퀵 정렬이라니!! 왜일까?

 - https://www.youtube.com/watch?v=ywWBy6J5gz8

 

2. 정렬 과정

퀵소트의 과정은 피봇을 이용해서 요소를 두 개로 그룹으로 나누는 파티셔닝 과정과 두 개의 그룹을 각각 다시 정렬하는 재귀 형태로 쪼개서 살펴볼 수 있다.

 

int [] src = {4,2,8,6,0,5,1,7,3,9}를 정렬시켜보자.

 

먼저 파티셔닝 부터 살펴보자.

 

배열의 맨 왼쪽 요소를 pl(pivot left), 맨 오른쪽 요소를 pr(pivot right)이라고 할때 맨 처음 값인 4를 pi(pivot index)로 잡자. 어차피 배열 내의 요소들이 정렬되지 않았기 때문에 pivot index는 어떤 값을 잡아도 무방하다. 어떤 값을 잡았을 때 효율적인가는 순전히 "운빨"이다.

 

 

이제 pivot을 중심으로 pivot보다 작은 값은 pivot의 왼쪽에, pivot보다 큰 값은 pivot의 오른쪽으로 위치시킨다. 

이를 위해 pl에서 오른쪽으로 쭉 증가하면서 pivot보다 작은 값이면 자리 이동을 하지 않으니 단순히 pl을 ++하면서 증가시킨다. 아니라면 그 값을 변경(스왑)해야한다. 마찬가지로 pr은 왼쪽으로 감소하면서 pivot보다 큰 값이면 단순히 pr을 -- 하면서 감소시키고 아니라면 그 값을 pl 처리 과정에서 찾은 값과 스왑한다.

아래 그림에서는 좌측에서 pl=0인 4가 4이상의 값이고 우측에서 pr=8인 3이 4미만이므로 둘을 위치 이동 시킨다.

 

스왑 후 현재의 pl과 pr은 처리가 끝났으므로 pl은 ++, pr은 -- 처리한 후 다시 탐색 하는 과정을 반복한다.

아래 그림에서 pl=1일 경우는 4보다 작으므로 통과, pl=2일 경우 8이므로 교체 대상이다. 우측에서는 pr=7인 경우는 4보다 크니까 통과, pr=6에서 1은 4보다 작으므로 pl=2와 swap 대상이 된다.

 

다시 pl=3인 6은 4보다 크니 이동대상, pr=5인 0은 4보다 작으니 이동대상이 되고 swap한다.

 

진행하다보면 pl과 pr이 교차하는 시점이 발생하는데 이 후로는 더 이상 교체할 대상이 없어진다. 따라서 이 단계의 파티션 작업은 종료가 된다.

 

종료되면서 이제 기존의 배열은 pl을 기준으로 두 개로 나눠볼 수 있다.

 

파티셔닝이 끝났다면 퀵 정렬은 반정도가 끝났다.

이제 큰 배열이 작은 두 개의 배열로 쪼개졌으므로 작은 배열 두개를 재귀를 통해서 계속 파티셔닝 해주면 된다.

재귀의 탈출 시점은 하나의 요소로만 남게 될 때 즉 pl과 pr이 같아지는 시점이다.

 

왼쪽 부분인 {3,2,1,0}의 처리 과정을 더 살펴보자.

 

 

파티셔닝 과정을 거쳐 {0,2,1}, 과 {3}으로 쪼개지고 {3}은 pl과 pr이 같으므로 모든 정렬이 끝난 상태다.

다시 {0,2,1}은 다음 과정을 거칠 것이다.

 

3. 자바 코드

@Test
@Order(4)
public void quickSortTest() {
	data = new int[] { 4, 2, 8, 6, 0, 5, 1, 7, 3, 9 };
	quickSort(data, 0, data.length - 1);
	System.out.printf("정렬 완료: %s%n", Arrays.toString(data));
}

// left와 right는 inclusive한 경계 값
public static void quickSort(int[] a, int left, int right) {
	// 정렬할 범위가 2개 이상의 데이터이면
	if (left != right) {
		// 분할(divide): partition을 이용해서 피봇을 기준으로 리스트 비균등 분할
		int pivotIdx = partition(a, left, right);
		//System.out.println("피봇 위치: " + pivotIdx + ">>" + Arrays.toString(a));
		// 정복(conquer): 피봇을 제외한 두 개의 부분 리스트를 대상으로 순환 호출
		quickSort(a, left, pivotIdx - 1);
		quickSort(a, pivotIdx, right);
	}
}

private static int partition(int[] a, int pl, int pr) {
	int pivot = a[pl];
	// pl과 pr이 겹칠 때까지 반복한다. --> 이상 진행하는것은 의미 없는일
	while (pl <= pr) {
		// a[pl]이 pivot보다 작으면 pl 증가, 아니면 반복을 멈추고 자리 바꿈 준비
		while (a[pl] < pivot) {
			pl++;
		}
		// a[pr]이 pivot 보다 크면 R 감소, 아니면 반복을 멈추고 자리 바꿈 준비
		while (a[pr] > pivot) {
			pr--;
		}
		// 바꿔야할 녀석들이 나왔으면 자리 바꿈, 이후 자리 바꾼 다음 요소부터 비교
		if (pl <= pr) {
			int temp = a[pr];
			a[pr] = a[pl];
			a[pl] = temp;
			pl++;
			pr--;
		}
		System.out.println("교체 결과: " + Arrays.toString(a));
	}
	return pl;
}

 

4. 정리

퀵 정렬은 병합 정렬과 마찬가지로 분할/정복 기반의 알고리즘이다. 

퀵 정렬은 분할정렬이기 때문에 일반적으로 O(nlogn)의 시간 복잡도를 가지지만 pivot으로 어떤 값이 선택되느냐, 배열 요소의 상태가 무엇이냐에 따라 성능이 크게 달라질 수 있다.

최악의 경우는 이미 모든 요소들이 정렬되어있고 첫 번째 요소가 pivot으로 선택되는 경우는 무려 O(n^2)의 시간 복잡도를 갖는다.

 

그런데도 왜 이 방법이 병합정렬을 제치고 퀵 정렬이라는 이름을 거머쥐게 되었을까?

일단 최악의 경우는 거의 발생하지 않는다는것이 첫번째 요인이다.(하지만 알고리즘 문제에서는 이런 상황을 만들기도 한다.ㅠㅠ)

두 번째 요인은 빅오 표기법의 특성상 상수가 무시되기 때문이다. 전혀 다른 시간 복잡도를 비교할 때는 상수가 거의 영향을 주지 않지만 동일한 시간 복잡도에서는 상수의 영향을 무시할 수 없다. 병합정렬과 퀵 정렬이 모두 O(nlogn)의 시간복잡도를 갖지만 병합정렬의 상수가 훨씬 커서 일반적으로 실제 속도는 퀵 정렬이 약간 빠르다.