퀵 정렬

지난 글 : [알고리즘/Do it 알고리즘] - 셸 정렬

 

퀵 정렬 살펴보기

참고 : [알고리즘/알고리즘 도감] - 퀵 정렬

퀵 정렬(quick sort)은 일반적으로 폭 넓게 사용되는 아주 빠른 정렬 알고리즘으로, 직접 개발한 찰스 앤터니 리처드 호어(C. A. R. Hoare)가 알고리즘의 정렬 속도가 매우 빠른 데서 착안해 붙인 이름이다. 

 

위 참고 외에 책에 새로운 내용이 있어 작성한다. 먼저 배열을 두 그룹으로 나누는 순서다. 아래 배열에서 피봇으로 6을 선택해 나눈다. 피봇을 x, 왼쪽 끝 요소의 인덱스 pl을 왼쪽 커서, 오른쪽 끝 요소의 인덱스 pr을 오른쪽 커서라 하자.

5	7	1	4	6	2	3	9	8
pl				x				pr

그룹을 나누려면 피봇 이하의 요소를 배열 왼쪽으로, 피봇 이상의 요소를 배열 오른쪽으로 옮겨야 한다. 이를 위해 아래 작업을 수행한다.

- a[pl] >= x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔한다.
- a[pr] <= x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔한다.

이 과정을 거치면 pl과 pr은 아래 그림의 위치에서 멈추게 된다.

5	7	1	4	6	2	3	9	8
	pl			x		pr

pl이 위치한 지점은 피봇값 이상의  요소가 있는 지점, pr이 위치한 지점은 피봇값 이하의 요소가 있는 지점이다. 여기서 왼쪽(pl)과 오른쪽(pr) 커서가 가리키는 요소 a[pl]과 a[pr]의 값을 교환한다. 그러면 피봇 이하의 값은 왼쪽으로 이동하고, 피봇 이상의 값은 오른쪽으로 이동한다.

				x
5	3	1	4	6	2	7	9	8
				pl	pr

다시 스캔을 계속하면 왼쪽, 오른쪽 커서는 위 그림의 위치에서 멈춘다. 이 두 요소 a[pl]과 a[pr]의 값을 교환한다.

5	7	1	4	2	6	3	9	8
				pr	pl

다시 스캔을 계속하면 위 그림처럼 두 커서( pl, pr)가 교차하게 된다. pl과 pr이 교차하면 그룹을 나누는 과정이 끝나고 배열은 아래처럼 두 그룹으로 나누어진다.

- 피봇 이하의 그룹 : a[0], ..., a[pl - 1]
- 피봇 이상의 그룹 : a[pr + 1], ..., a[n - 1]

또, 그룹을 나누는 작업이 끝난 후 pl > pr + 1이면 아래 같은 그룹이 생길 수 있다.

- 피봇과 같은 값을 갖는 그룹 : a[pr + 1], ..., a[pl - 1]

위 예에서는 피봇과 같은 값을 갖는 그룹이 만들어지지는 않았다.

 

아래는 배열을 나누는 프로그램이다. 배열 가운데에 있는 요소를 피봇으로 정하고 그룹을 나눈다.

이 프로그램에서는 '배열 가운데에 있는 요소'를 피봇으로 했다. 어떤 요소를 피봇으로 선택하는가는 배열을 나누고 정렬하는 성능(performance)에 영향을 미친다.

 

퀵 정렬 구현하기

위에서 배열을 피봇 기준으로 나누기만 했다. 이 방법을 좀 더 발전시키면 퀵 정렬 알고리즘이 된다. 

참고 : [알고리즘/알고리즘 도감] - 퀵 정렬

 

요솟수가 1개인 그룹은 더 이상 그룹을 나눌 필요가 없기에 요솟수가 2개 이상인 그룹만 나누면 된다. 따라서 아래처럼 배열을 반복해 나누게 된다.

- pr이 맨 앞보다 오른쪽에 있으면(left < pr) 왼쪽 그룹을 나눈다.
- pl이 맨 뒤보다 왼쪽에 있으면(pl > right) 오른쪽 그룹을 나눈다.

 

퀵 정렬은 이전에 공부한 8퀸 문제와 마찬가지로 분할 정복 알고리즘이므로 재귀 호출을 사용해 간결히 구현할 수 있다. 아래는 퀵 정렬 프로그램이다. quickSort 메서드는 배열 a, 나눌 구간의 맨 앞 요소(left), 맨 뒤 요소(right)의 인덱스를 매개변수로 받는다.

 

비재귀적인 퀵 정렬 구현하기

이전에 recur 메서드를 비재귀적으로 구현해 봤었다. 마찬가지로 quickSort 메서드도 비재귀적으로 구현할 수 있다.

이전에 배운 recur 메서드는 데이터를 일시적으로 저장하기 위해 '스택'을 사용했다. 이번 퀵 정렬도 마찬가지로 '스택'을 사용한다. quickSort 메서드는 아래 2개의 스택을 사용한다.

- lstack ... 나눌 범위의 왼쪽 끝(맨 앞) 요소의 인덱스를 저장하는 스택이다.
- rstack ... 나눌 범위의 오른쪽 끝(맨 뒤) 요소의 인덱스를 저장하는 스택이다.

 

스택의 크기 구하기

위 프로그램은 스택의 크기를 배열의 요솟수로 초기화한다. 그럼 스택의 용령은 어느 정도의 크기여야 하는지 알아보자. 

 

스택에 푸시하는 순서는 아래 2가지 방법으로 수행할 수 있다.

방법 1. 요솟수가 많은 그룹을 먼저 푸시한다.
방법 2. 요솟수가 적은 그룹을 먼저 푸시한다.

 

방법 1) 요솟수가 많은 그룹을 먼저 푸시하는 경우

6	5	4	2	7	3	1	8

위 배열을 통해 방법1을 살펴보자. 먼저 스택에 a[0] ~ a[7]({0, 7})을 넣는다. 그리고 {0, 7}(a[0] ~ a[7])을 a[0] ~ a[1], a[2] ~ a[7]로 나눈다. 요솟수가 많은 {2, 7}을 먼저 푸시하므로 스택은 {2, 7}, {0, 1} 순으로 쌓인다. 먼저 팝되어 나누어지는 배열은 요솟수가 적은 {0, 1}이다. 이렇게 계속 진행하면 스택에 쌓여 있는 데이터의 최대 개수는 2가 된다.

 

방법 2) 요솟수가 적은 그룹을 먼저 푸시하는 경우

위와 마찬가지로 꺼낸 a[0] ~ a[7]을 a[0] ~ a[1], a[2] ~ a[7]로 나눈다. 요솟수가 적은 {0, 1}을 먼저 푸시하면 먼저 팝되어 나누어지는 배열은 요솟수가 많은 그룹 {2, 7}이다. 이렇게 계속하면 스택에 쌓여 있는 데이터의 최대 개수는 4가 된다. 

 

일반적으로 요솟수가 적은 배열일수록 적은 횟수로 분할을 종료할 수 있다. 따라서 방법 1과 같이 요솟수가 많은 그룹을 나누기보다 요솟수가 적은 그룹을 먼저 분할하면 스택에 동시에 쌓이는 데이터의 최대 개수가 적어진다. 이때 방법 1, 2 둘 다 스택에 넣고 꺼내는 횟수는 같지만, 동시에 스택에 쌓이는 데이터의 최대 개수는 다르다. 방법 1의 경우 배열의 요솟수가 n이라면 스택에 쌓이는 데이터의 최대 개수는 log n보다 적다. 그러므로 요솟수가 백만 개라 해도 스택의 용량은 20이면 충분하다.

 

피봇 선택하기

피봇은 선택하는 방법은 퀵 정렬의 실행 효율에 큰 영향을 준다. 이번에는 피봇 선택 방법을 아래 배열을 예로 들어 살펴보자.

8	7	6	5	4	3	2	1	0

피봇으로 왼쪽 끝 요소(8)을 선택한다면 이 배열은 피봇값(8)만 있는 그룹과 나머지 그룹으로 나누어진다. 하나의 요소와 나머지 요소로 나누어지는(한쪽으로 치우친) 분할을 반복하는 방법으로는 정렬 속도를 빠르게 할 수 없다. 정렬을 빠르게 하고 싶다면 배열을 정렬한 다음의 중앙값, 곧 값을 기준으로 한 중앙값을 피봇으로 하면 된다. 배열이 고르게 절반으로 나누어지기에 정렬을 빠르게 할 수 있다. 그러나 중앙값을 구하려면 그에 대한 별도의 처리가 필요하고, 이 처리에 많은 계산 시간이 요구되므로 배보다 배꼽이 커진다. 이런 문제를 해결하기 위해 아래 방법을 사용하면 적어도 최악은 면한다.

방법 1. 나눌 배열의 요솟수가 3 이상이면 임의로 요소 3개를 선택하고, 그 중 중앙값인 요소를 피봇으로 선택한다.

예로 위 배열에서 첫 요소(8), 가운데 요소(4), 끝 요소(0) 중 중간 크기의 값(4)을 피봇으로 하면 그룹이 최악으로 나누어지는 경우는 면할 수 있다.

 

이 생각을 조금 더 발전시킨 것이 아래 방법 2다.

방법 2. 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 후 가운데 요소와 끝에서 두 번째 요소를 교환한다. 피봇으로
	끝에서 두 번째 요솟값(a[right - 1])을 선택하고 나눌 대상의 범위를 a[left + 1] ~ a[right - 2]로 한다.

이 과정을 거치면 스캔하는 커서의 시작 위치는 아래처럼 변경된다.(나눌 대상의 범위가 좁아진다)

교환 전
8	7	6	5	4	3	2	1	0
==================================================================
방법 2 실행 후
0	7	6	5	1	3	2	4	8

왼쪽 끝 요소(맨 앞, 8)과 오른쪽 끝 요소(맨 뒤, 0)를 정렬(교환)하고, 중앙값(4)을 오른쪽 끝에서 두 번째 요소(1)
과 교환한다.

- 왼쪽 커서 pl의 시작 위치 ... left -> left + 1(오른쪽으로 1만큼 이동)
- 오른쪽 커서 pr의 시작 위치 ... right -> right - 2(왼쪽으로 2만큼 이동)

이 방법은 나누는 그룹의 크기가 한쪽으로 치우치는 것을 피하면서도 나눌 때 스캔하는 요소를 3개 줄일 수 있다.

 

아래는 방법 2를 바탕으로 수정한 프로그램이다. 이 프로그램에서 새로 추가한 sort3elem 메서드는 배열 x 안의 세 요소인 x[a], x[b], x[c]의 요솟값을 정렬(크기순으로 교환)한 뒤 b값을 그대로 반환한다. 퀵 정렬을 수행하는 quickSort 메서드에서 변경 내용은 배열을 나누기 전 아래 코드를 실행하는 것이다.

 

퀵 정렬의 시간 복잡도 구하기

퀵 정렬은 배열을 차례로 나눠 보다 작은 문제를 해결하는 과정을 반복하므로 시간 복잡도는 O(n long n)이다. 다만 정렬할 배열의 초깃값이나 피봇의 선택 방법에 따라 시간 복잡도가 증가하는 경우도 있다. 예로 매번 단 하나의 요소와 나머지 요소로 나눈다면 나누는 횟수는 n번이 된다. 따라서 최악의 시간 복잡도는 O(n2)이 된다.

 

참고 서적 :