들어가며
사람은 사려서 사귀자.
10.0. 속도를 높이는 재귀 알고리즘
앞서 살펴봤듯이 재귀를 이해하면
파일 시스템 검색과 같은
새로운 알고리즘을 많이 사용할
수 있다.
10장에서는 코드를 훨씬 더 빠르게
실행시킬 수 있는 알고리즘에서도
재귀가 핵심 기술임을 배우겠다.
9장에서 버블 정렬과 선택 정렬,
삽입 정렬 같은
많은 정렬 알고리즘을 살펴봤다.
하지만 실제로 배열을 정렬할 때는
이러한 방법을 쓰지 않는다.
컴퓨터 언어에는 대부분 내장 정렬
함수가 있어
사용자가 스스로 구현하는 데
드는 시간과 노력을 아껴준다.
컴퓨터 언어 중 대다수가 내부적으로
채택한 정렬 알고리즘이
바로 퀵 정렬이다.
많은 컴퓨터 언어에 퀵 정렬이
내장되어 있음에도 불구하고
퀵 정렬을 깊이 알아보려는 이유는
퀵 정렬의 동작 방식을 공부함으로써
재귀를 사용해 어떻게 알고리즘의
속도를 크게 향상시키는지 배우고,
실제 쓰이고 있는 다른 실용적인
알고리즘에도
똑같이 적용할 수 있기 때문이다.
퀵 정렬은 매우 빠른 정렬 알고리즘으로,
특히 평균 시나리오에서 효율적이다.
최악의 시나리오*에서는 삽입 정렬이나
선택 정렬과 성능이 유사하지만
* 역순으로 정렬된 배열
대부분의 경우 일어나는 평균
시나리오에서는 훨씬 빠르다.
퀵 정렬은 분할이라는 개념에
기반하므로 분할을 먼저 알아보자.
10.1. 분할
배열을 분할한다는 것은 배열로부터
임의의 수*를 가져와
* 이후 이 수를 피벗이라 부른다.
피벗보다 작은 모든 수는 피벗의
왼쪽에,
피벗보다 큰 모든 수는 피벗의
오른쪽에 두는 것이다.
이어지는 예제에서 설명할 간단한
알고리즘으로 분할을 수행한다.
다음과 같은 배열이 있다고 하자.
| 0 | 5 | 2 | 1 | 6 | 3 |
일관된 설명을 위해 가장 오른쪽에
있는 값을 항상 피벗으로 하겠다.
물론 기술적으로 다른 값을 고를
수도 있다.
피벗은 다음과 같이 표시하겠다.
| 피벗(Pivot) | |||||
| 0 | 5 | 2 | 1 | 6 | 3 |
이어서 두 "포인터"를 사용해 하나는
배열 가장 왼쪽의 값에,
다른 하나는 피벗을 제외한 배열의
가장 오른쪽의 값에 할당한다.
| ↓(Pointer-L) | ↓(Pointer-R) | 피벗(Pivot) | |||
| 0 | 5 | 2 | 1 | 6 | 3 |
이제 다음과 같은 단계를 따라
실제 분할을 할 수 있다.
- 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옳기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.
- 이어서 오른쪽 포인터를 한 셀씩 계속 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다.
- 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한다.
- 두 포인터가 가리키는 값이 같거나 왼쪽 포인터가 오른쪽 포인터 바로 오른쪽으로 이동할 때까지 위 과정을 반복한다.
- 끝으로 왼쪽 포인터가 현재 가리키고 있는 값과 피벗을 교환한다.
분할이 끝나면 피벗 왼쪽에 있는
값은 모두 피벗보다 작고,
피벗 오른쪽에 있는 값은 모두
피벗보다 크다고 확신할 수 있다.
또한, 다른 값들은 아직 완전히
정렬되지 않았지만
피벗 자체는 이제 배열 내에서
올바른 위치에 있다는 뜻이다.
이게 대체 머선 소린지 모루겠다.
위 절차를 예제에 적용해 보자.
1-1단계: 왼쪽 포인터(현재 0을 가리킴)와 피벗(값 3)을 비교하여 작은지 판단한다.
| ↓(Pointer-L) | ↓(Pointer-R) | 피벗(Pivot) | |||
| 0 | 5 | 2 | 1 | 6 | 3 |
1-2단계: 0은 피벗보다 작으므로(0<3) 다음 단계에서 왼쪽 포인터를 이동시킨다.
2-0단계: 왼쪽 포인터를 이동시킨다.
2-1단계: 왼쪽 포인터(현재 5를 가리킴)와 피벗(값 3)을 비교하여 작은지 판단한다.
| ↓(Pointer-L) | ↓(Pointer-R) | 피벗(Pivot) | |||
| 0 | 5 | 2 | 1 | 6 | 3 |
2-2단계: 5는 피벗보다 크므로(5>3) 왼쪽 포인터의 이동을 멈추고
2-3단계: 다음 단계에서 오른쪽 포인터를 비교시킨다.
3-1단계: 오른쪽 포인터(현재 6를 가리킴)와 피벗(값 3)을 비교하여 큰지 판단한다.
| ↓(Pointer-L) | ↓(Pointer-R) | 피벗(Pivot) | |||
| 0 | 5 | 2 | 1 | 6 | 3 |
3-2단계: 6은 피벗보다 크므로(6>3) 다음 단계에서 오른쪽 포인터를 이동시킨다.
4-0단계: 오른쪽 포인터를 이동시킨다.
4-1단계: 오른쪽 포인터(현재 1를 가리킴)와 피벗(값 3)을 비교하여 큰지 판단한다.
| ↓(Pointer-L) | ↓(Pointer-R) | 피벗(Pivot) | |||
| 0 | 5 | 2 | 1 | 6 | 3 |
4-2단계: 1은 피벗보다 작으므로(1<3) 오른쪽 포인터의 이동을 멈추고
4-3단계: 다음 단계에서 좌우 포인터의 값을 교환한다.
5-1단계: 두 포인터가 모두 멈췄으므로 두 포인터의 값을 교환한다.
| ↓(Pointer-L) | ↓(Pointer-R) | 피벗(Pivot) | |||
| 0 | 1 | 2 | 5 | 6 | 3 |
5-2단계: 다음 단계에서 다시 왼쪽 포인터를 이동시킨다.
6-0단계: 왼쪽 포인터 옮긴다.
6-1단계: 왼쪽 포인터(현재 2를 가리킴)와 피벗(값 3)을 비교하여 작은지 판단한다.
| ↓(Pointer-L) | ↓(Pointer-R) | 피벗(Pivot) | |||
| 0 | 1 | 2 | 5 | 6 | 3 |
6-2단계: 2는 피벗보다 작으므로(2<3) 다음 단계에서 왼쪽 포인터를 이동시킨다.
7-0단계: 왼쪽 포인터를 옮긴다.
7-1단계: 왼쪽 포인터(현재 5를 가리킴)와 피벗(값 3)을 비교하여 작은지 판단한다.
| ↓(Pointer-L, R) | 피벗(Pivot) | ||||
| 0 | 1 | 2 | 5 | 6 | 3 |
7-2단계: 5는 피벗보다 크므로(5>3) 왼쪽 포인터의 이동을 멈춘다.
7-3단계: 이때 왼쪽 포인터가 오른쪽 포인터에 도달했으므로 모든 포인터의 이동을 멈춘다.
8-0단계: 왼쪽의 포인터가 가리키고 있는 값과 피벗을 교환한다.
| 피벗(Pivot) | ↓(Pointer-L, R) | ||||
| 0 | 1 | 2 | 3 | 6 | 5 |
배열은 완전히 정렬되지 않았지만
분할은 성공적으로 끝냈다.
즉, 피벗이 숫자 3이었으므로 3보다
작은 수는 모두 왼쪽에,
3보다 큰 모든 수는 3의 오른쪽에 있다.
또한 3이 이제 배열 내에서 올바른
위치에 있게 됐다.
| 피벗(Pivot) | |||||
| 0 | 1 | 2 | 3 | 6 | 5 |
다음은 루비로 구현한 SortableArray
클래스로
지금까지 설명한 방법대로 배열을
분할하는 parition! 메서드를 포함한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
class SortableArray
attr_reader :array
def initialize(array)
@array = array
end
def partition!(left_pointer, right_pointer)
# 항상 가장 오른쪽에 있는 값을 피벗으로 선택한다.
pivot_position = right_pointer
pivot = @array[pivot_position]
# 피벗 바로 왼쪽에서 오른쪽 포인터를 시작한다.
right_pointer -= 1
while true do
while @array[left_pointer] < pivot do
left_pointer += 1
end
while @array[right_pointer] > pivot do
right_pointer -= 1
end
if left_pointer >= right_pointer
break
else
swap(left_pointer, right_pointer)
end
end
swap(left_pointer, right_pointer)
# 이어지는 예제에서 나올 퀵 소트 메서드를 위해 왼쪽 포인터를 반환한다.
return left_pointer
end
def swap(pointer_1, pointer_2)
temp_value = @array[pointer_1]
@array[pointer_1] = @array[pointer_2]
@array[pointer_2] = temp_value
end
end
|
cs |
partition! 메서드는,
왼쪽 포인터와 오른쪽 포인터의
시작점을 매개변수로 받아
왼쪽 포인터가 끝났을 때의 최종
위치를 반환한다.
지금까지 알아본 내용은 전부
다음으로 알아볼
퀵 정렬 구현에 필요한 것들이다.
10.2 퀵 정렬
퀵 정렬 알고리즘에는 분할이
매우 중요하다.
알고리즘은 다음과 같이 동작한다.
- 배열을 분할한다. 피벗은 이제 올바른 위치에 있다.
- 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각각 또 다른 배열로 보고 1단계와 2단계를 재귀적으로 반복한다. 즉, 하위 배열을 분할하고 각 하위 배열에 있는 피벗의 왼쪽과 오른쪽에서 더 작아진 하위 배열을 얻는다. 이어서 이러한 하위 배열을 다시 분할하는 과정을 반복한다.
- 하위 배열이 원소 0개 또는 1개만 포함하면 기저 조건이므로 아무것도 하지 않는다.
퀵 정렬을 성공적으로 끝내려면
다음 quicksort! 메서드를
앞서 보인 SortableArray 클래스에
추가한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def quicksort!(left_index, right_index)
# 기저 조건: 하위 배열에 원소가 0개 또는 1개일 경우
if right_index - left_index <= 0
return
end
# 배열을 분할하고 피벗의 위치를 가져온다.
pivot_position = partition!(left_index, right_index)
# 피벗의 왼쪽 배열에 대해 quicksort! 메서드를 재귀적으로 호출한다.
quicksort!(left_index, pivot_position - 1)
# 피벗의 오른쪽 배열에 대해 quicksort! 메서드를 재귀적으로 호출한다.
quicksort!(pivot_position + 1, right_index)
end
|
cs |
다음과 같은 코드를 실행해서
실제로 동작하는지 확인한다.
|
1
2
3
4
|
array = [0, 5, 2, 1, 6, 3]
sortable_array = SortableArray.new(array)
sortable_array.quicksort!(0, array.length - 1)
p sortable_array.array
|
cs |
예제로 돌아가 보자.
배열 [0, 5, 2, 1, 6, 3]으로 시작해서
전체 배열에 대해
한 번의 분할을 수행했었다.
퀵 정렬은 분할로 시작하므로
이미 퀵 정렬 과정을
일부 수행해 본 것이다.
다음의 상황까지 알아봤었다.
| 피벗(Pivot) | |||||
| 0 | 1 | 2 | 3 | 6 | 5 |
그림에서 볼 수 있듯이 값 3이
피벗이었다.
피벗은 올바른 위치에 있으므로
피벗의 왼쪽과 오른쪽을 정렬해야
한다.
어쩌다 보니 피벗 왼쪽은 이미
정렬되어 있지만,
컴퓨터는 아직 모른다.
분할이 끝나면 다음으로 피벗
왼쪽에 있는 모든 값을
하나의 배열로 보고 분할한다.
현재로서는 배열의 나머지 부분에
관심이 없으므로
당분간 다음과 같이 표시하겠다.
| 피벗(Pivot) | |||||
| 0 | 1 | 2 | 3 | 6 | 5 |
하위 배열 [0, 1, 2] 중에서 가장
오른쪽 원소를 피벗으로 하겠다.
즉, 숫자 2다.
| 피벗(Pivot) | 피벗(Pivot) | ||||
| 0 | 1 | 2 | 3 | 6 | 5 |
왼쪽과 오른쪽 포인터를
설정한다.
| ↓(Pointer-L) | ↓(Pointer-R) | 피벗(Pivot) | 피벗(Pivot) | ||
| 0 | 1 | 2 | 3 | 6 | 5 |
이제 이 하위 배열을 분할할
준비가 되었다.
이전에 중지했던 8단계 이후부터
살펴보자.
9-1단계: 왼쪽 포인터(현재 0을 가리킴)와 피벗(값 2)을 비교하여 작은지 판단한다.
| ↓(Pointer-L) | ↓(Pointer-R) | 피벗(Pivot) | 피벗(Pivot) | ||
| 0 | 1 | 2 | 3 | 6 | 5 |
9-2단계: 0은 피벗보다 작으므로(0<2) 다음 단계에서 왼쪽 포인터를 이동시킨다.
10-0단계: 왼쪽 포인터를 이동시킨다.
10-1단계: 왼쪽 포인터(현재 1를 가리킴)와 피벗(값 2)을 비교하여 작은지 판단한다.
| ↓(Pointer-L, R) | 피벗(Pivot) | 피벗(Pivot) | |||
| 0 | 1 | 2 | 3 | 6 | 5 |
10-2단계: 1는 피벗보다 작으므로(1<2) 다음 단계에서 왼쪽 포인터를 이동시킨다.
11-0단계: 왼쪽 포인터를 이동시킨다.
11-1단계: 왼쪽 포인터(현재 2를 가리킴)와 피벗(값 2)을 비교하여 작은지 판단한다.
| ↓(Pointer-R) | ↓(Pointer-L) 피벗(Pivot) |
피벗(Pivot) | |||
| 0 | 1 | 2 | 3 | 6 | 5 |
11-2단계: 2는 피벗과 동일하므로(2=2) 왼쪽 포인터의 이동을 멈추고
11-3단계: 다음 단계에서 오른쪽 포인터를 비교시킨다.
12-1단계: 오른쪽 포인터(현재 1를 가리킴)와 피벗(값 2)을 비교하여 큰지 판단한다.
| ↓(Pointer-R) | ↓(Pointer-L) 피벗(Pivot) |
피벗(Pivot) | |||
| 0 | 1 | 2 | 3 | 6 | 5 |
12-2단계: 1은 피벗보다 작으므로(1<2) 오른쪽 포인터의 이동을 멈추고
12-3단계: 왼쪽 포인터가 오른쪽 포인터를 지나쳤으므로, 이번 분할에서는 모든 포인터의 이동을 멈춘다.
13-1단계: 왼쪽의 포인터가 가리키고 있는 값과 피벗을 교환한다.
| ↓(Pointer-R) | ↓(Pointer-L) 피벗(Pivot) |
피벗(Pivot) | |||
| 0 | 1 | 2 | 3 | 6 | 5 |
우연히 왼쪽 포인터가 피벗을
가리키게 됐으므로
스스로를 교환한다.
따라서 아무런 변화가 없다.
이제 분할은 끝이 났으며, 피벗(2)은
올바른 위치에 놓여있다.
| 피벗(Pivot) | 피벗(Pivot) | ||||
| 0 | 1 | 2 | 3 | 6 | 5 |
피벗(2) 왼쪽에는 하위 배열인
[0, 1]이 있고,
오른쪽에는 어떤 하위 배열도
없다.
다음 단계는 피벗 왼쪽에 있는
하위 배열,
즉 [0, 1]을 재귀적으로 분할하는
것이다.
피벗 오른쪽에는 하위 배열이
없으므로 처리할 필요가 없다.
다음 단계에서는 하위 배열인
[0, 1]에만 초점을 맞추므로
배열의 나머지 부분은 다음처럼
표시하겠다.
| 피벗(Pivot) | 피벗(Pivot) | ||||
| 0 | 1 | 2 | 3 | 6 | 5 |
하위 배열인 [0, 1]을 분할하기 위해,
가장 오른쪽에 있는 원소를 피벗으로
하겠다.
왼쪽과 오른쪽 포인터는 어디에
둘 것인가?
왼쪽 포인터는 당연히 0을 가리키겠지만
오른쪽 포인터는 피벗의 한 셀
왼쪽에서 시작하므로
오른쪽 포인터도 0을 가리킬 것이다.
따라서 다음과 같다.
| ↓(Pointer-L, R) | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | ||
| 0 | 1 | 2 | 3 | 6 | 5 |
그럼 이제 분할을 시작할 수 있다.
14-1단계: 왼쪽 포인터(현재 0을 가리킴)와 피벗(값 1)을 비교하여 작은지 판단한다.
| ↓(Pointer-L, R) | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | ||
| 0 | 1 | 2 | 3 | 6 | 5 |
14-2단계: 0은 피벗보다 작으므로(0<1) 다음 단계에서 왼쪽 포인터를 이동시킨다.
15-0단계: 왼쪽 포인터를 이동시킨다.
15-1단계: 왼쪽 포인터(현재 1을 가리킴)와 피벗(값 1)을 비교하여 작은지 판단한다.
| ↓(Pointer-R) | ↓(Pointer-L) 피벗(Pivot) |
피벗(Pivot) | 피벗(Pivot) | ||
| 0 | 1 | 2 | 3 | 6 | 5 |
15-2단계: 1은 피벗과 동일하므로(1=1) 왼쪽 포인터의 이동을 멈추고
15-3단계: 다음 단계에서 오른쪽 포인터를 비교시킨다.
16-1단계: 오른쪽 포인터(현재 0을 가리킴)와 피벗(값 1)을 비교하여 작은지 판단한다.
| ↓(Pointer-R) | ↓(Pointer-L) 피벗(Pivot) |
피벗(Pivot) | 피벗(Pivot) | ||
| 0 | 1 | 2 | 3 | 6 | 5 |
16-2단계: 0은 피벗보다 작으므로(0<1) 오른쪽 포인터의 이동을 멈추고
16-3단계: 왼쪽 포인터가 오른쪽 포인터를 지나쳤으므로, 이번 분할에서는 모든 포인터의 이동을 멈춘다.
13-1단계: 왼쪽의 포인터가 가리키고 있는 값과 피벗을 교환한다.
| ↓(Pointer-R) | ↓(Pointer-L) 피벗(Pivot) |
피벗(Pivot) | 피벗(Pivot) | ||
| 0 | 1 | 2 | 3 | 6 | 5 |
이번에도 마찬가지로 왼쪽 포인터가
피벗을 가리키게 됐으므로
교환에 따른 아무런 변화가 없다.
피벗은 이제 올바른 위치에 있으며,
분할은 여기서 종료된다.
결과는 다음과 같다.
| 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | |||
| 0 | 1 | 2 | 3 | 6 | 5 |
다음으로 가장 최근 피벗의 왼쪽에
있는 하위 배열을 분할해야 한다.
현재 이 하위 배열은 단 하나의
원소로 이루어진 [0]이다.
원소가 0 or 1개로 이루어진 배열은
기저 조건이므로 여기서 종료한다.
이 원소는 자동으로 올바른 위치에
있다고 간주되며,
따라서 다음과 같다.
| 기저 조건 |
피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | ||
| 0 | 1 | 2 | 3 | 6 | 5 |
3을 피벗으로 선택해서 3의 왼쪽
하위 배열을 분할했다.
앞서 설명했듯이 이제 3의 오른쪽에
있는 하위 배열을 분할해야 한다.
[0, 1, 2, 3]은 이미 정렬되었으므로
흐리게 표시하고
[6, 5]에 초점을 두겠다.
| 기저 조건 |
피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | ||
| 0 | 1 | 2 | 3 | 6 | 5 |
이번 분할에서는 가장 오른쪽 원소
5를 피벗으로 한다.
| 기저 조건 | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | |
| 0 | 1 | 2 | 3 | 6 | 5 |
분할을 준비하면 왼쪽과 오른쪽
포인터 모두 6을 가리키게 된다.
18-1단계: 왼쪽 포인터(현재 6을 가리킴)와 피벗(값 5)을 비교하여 작은지 판단한다.
| 기저 조건 | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | ↓(Pointer-L, R) | 피벗(Pivot) |
| 0 | 1 | 2 | 3 | 6 | 5 |
18-2단계: 6은 피벗보다 크므로(6>5) 왼쪽 포인터의 이동을 멈추고
18-3단계: 다음 단계에서 오른쪽 포인터를 비교시킨다.
19-1단계: 오른쪽 포인터(현재 6을 가리킴)와 피벗(값 5)을 비교하여 큰지 판단한다.
| 기저 조건 | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | ↓(Pointer-L, R) | 피벗(Pivot) |
| 0 | 1 | 2 | 3 | 6 | 5 |
19-2단계: 6은 피벗보다 크므로(6>5) 다음 단계에서 오른쪽 포인터를 이동시켜야 하지만
19-3단계: 이동할 수 있는 셀이 없으므로 이동을 멈춘다.
19-4단계: 이때 왼쪽 포인터가 오른쪽 포인터에 도달했으므로 모든 포인터의 이동을 멈춘다.
20-1단계: 왼쪽의 포인터가 가리키고 있는 값과 피벗을 교환한다.
| 기저 조건 | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | ↓(Pointer-L, R) |
| 0 | 1 | 2 | 3 | 5 | 6 |
이제 피벗(5)는 다음과 같이
올바른 위치에 놓여있다.
| 기저 조건 | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | |
| 0 | 1 | 2 | 3 | 5 | 6 |
기술적으로 다음에 해야 할
작업은 하위 배열 [5, 6]의
왼쪽과 오른쪽 하위 배열을
재귀적으로 분할하는 것이다.
왼쪽에는 하위 배열이 없으므로
오른쪽 하위 배열만 분할하면 된다.
5의 오른쪽에 있는 하위 배열은
원소가 하나인 [6]이므로
기저 조건을 중촉하며, 따라서
아무 것도 하지 않는다.
그렇기 때문에 6은 올바른
위치에 있다.
| 기저 조건 | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | 피벗(Pivot) | 기저 조건 |
| 0 | 1 | 2 | 3 | 5 | 6 |
드디어 퀵 정렬의 끝이 났다.
10.3. 퀵 정렬의 효율성
퀵 정렬의 효율성을 알아내려면
먼저 분할의 효율성을 밝혀야 한다.
분할에 필요한 단계를 분류해 보면
단계가 2종류임을 알 수 있다.
- 비교: 각 값과 피벗을 비교한다.
- 교환: 적절한 때에 왼쪽과 오른쪽 포인터가 가리키고 있는 값을 교환한다.
각 분할마다 배열 내 각 원소를
피벗과 비교하므로
따라서 최소 N번* 비교한다.
* 피벗을 제외한 각각의 원소를 피벗과 비교(N-1번) + (두 포인터가 겹친 상태에서 피벗과 비교) or (피벗이 피벗과 비교)(1번) = N번 비교
분할을 할 때마다 왼쪽과 오른쪽
포인터가 서로 만날 때까지
각 셀을 이동하기 때문이다.
교환 횟수는 데이터가 얼마나
정렬되어 있느냐에 달려있다.
각 분할마다 최소 한 번 교환을
진행하며,
가능한 값을 모두 교환한다 해도
왼쪽 반과 오른쪽 반에 있는 값을
교환하므로
한 분할에서 최소 (N/2)번 교환한다.
다음을 보자.
| ⓒ | ⓑ | ⓐ | ⓐ | ⓑ | ⓒ | 피벗(Pivot) |
| 7 | 6 | 5 | 3 | 2 | 1 | 4 |
무작위로 정렬된 데이터가 있을 때,
대략 (N/2)의 절반,
즉 (N/4)번 정도 교환할 것이다.
따라서 비교 N번과 (N/4)를 합하면
대략 (1.25N)단계가 걸린다.
빅 오 표기법은 상수를 무시하므로
O(N) 시간에 분할을 실행한다고
말할 수 있다.
이는 한 번 분할할 때의 효율성이다.
하지만 퀵 정렬은 다양한 크기의
배열과 하위 배열을
여러번 분할하므로 퀵 정렬의
효율성을 알아내려면
좀 더 분석해야 한다.
시각적으로 보다 쉽게 이해할 수 있도록
다음 그림에서 원소가 8개인 배열에
대해서
전형적인 퀵 정렬을 한 눈에 알아볼
수 있게 묘사했다.
특히 이 그림은 얼마나 많은 원소에
대해
각각 분할을 수행했는지를 보여준다.
어떤 수를 정렬했느냐는 중요하지
않으므로
실제 수는 배열에서 제외했다.
다음 그림에서 흐리게 표시하지
않은 셀 그룹이
정렬중인 하위 배열이다.
■: 피벗으로, 올바른 위치에 놓여진 수
■: 기저 조건이 충족되어 올바른 위치에 놓여진 수
■: 아직 정렬되지 않은 수
분할1: 8개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할2: 3개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할3: 1개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할4: 1개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할5: 4개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할6: 2개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할7: 1개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할8: 1개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
보다시피 분할이 8개지만 분할마다
하위 배열의 크기가 다르다.
원소가 하나뿐인 하위 배열이면
기저 조건이며,
어떤 교환이나 비교도 수행하지
않으므로
원소가 둘 이상인 하위 배열에서
일어나는 분할이 중요하다.
위 예제는 평균적인 경우를
설명하므로
각 분할에 대략 (1.25N)단계가
걸린다고 가정하다.
이렇게 하면 결과는 다음과 같다.
8개 원소 * 1.25단계 = 10단계
3개 원소 * 1.25단계 = 3.75단계
4개 원소 * 1.25단계 = 5단계
+ 2개 원소 * 1.25단계 = 2.5단계
━━━━━━━━━━━━━━━
합계 = 약 21단계
배열의 크기가 다양하다는
가정 하에 분석하면
원소가 N 개일 때, 약 (N * log N)
단계임을 알 수 있다.
(N * log N)이 어느 정도인지 감을
잡으려면
다음 표를 확인한다.
앞선 예제에서 배열의 크기가
8일 때 퀵 정렬에
약 21단계가 걸렸다.
즉, 대략적으로 '8 * log(8)'이다.
처음 배워보는 알고리즘 분류로,
빅 오에서는 O(N log N)으로
표현한다.
퀵 정렬의 단계 수가 'N * log N'에
부합하는 것은 우연이 아니다.
보다 광범위하게 퀵정렬을 생각해
보면 이유를 알 수 있다.
퀵 정렬을 시작하면서 전체 배열을
분할한다.
배열 중간 어딘가를 피벗이라
가정하면*,
* 평균적인 경우에 일어나는 상황
배열을 반으로 나눠 두 반쪽을
각각 분할한다.
이어서 두 반쪽 각각을 가져와 ¼로
나누고, 다시 각각의 ¼을 분할한다.
이 과정이 반복된다.
요컨데 원소가 한 개인 하위 배열이
될 때까지
각 하위 배열을 계속 반으로 나눈다.
이런 식으로 배열을 몇번 나눠야 할까?
크기가 N인 배열이면 log N번을
나눌 수 있다.
즉 크기가 8인 배열은 원소 한 개가
될 때까지 반으로 3번 나눌 수 있다.
이진 검색을 배웠으니, 이러한 개념에
익숙할 것이다.
각 하위 배열을 반으로 나눌 때마다
원래 배열의 모든 원소를 다시
분할한다.
다음 그림을 보자
원래 배열을 같은 크기의 하위 배열로
log N번 나눌 수 있고
나눌 때마다 원래 배열의 N개의
셀 전부를 분할해야 하므로
총 (N * log N)단계다.
지금까지 본 많은 알고리즘에서
최선의 경우는
배열이 이미 정렬됐을 때였다.
하지만 퀵 정렬에서 최선의
시나리오는
분할 후 피벗이 하위 배열의
한 가운데 있을 때다.
10.4 최악의 시나리오
퀵 정렬에서 최악의 시나리오는
피벗이 항상 하위 배열의 정중앙이
아닌 한쪽 끝에 있을 때다.
배열이 완전히 오름차순 또는
내림차순일 때를 포함해
몇몇 상황에서 일어날 수 있다.
다음은 이러한 절차를 보여준다.
■: 피벗으로, 올바른 위치에 놓여진 수
■: 기저 조건이 충족되어 올바른 위치에 놓여진 수
■: 아직 정렬되지 않은 수
분할1: 8개 원소분할1: 8개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할2: 7개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할3: 6개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할4: 5개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할5: 4개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할6: 3개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할7: 2개 원소
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
각 분할마다 교환은 한 번 뿐이지만
비교가 너무 많으면 손해다.
첫 번째 예제에서의 피벗은 항상
중간 즈음에 있었고
첫 번째 분할 후에는 비교적
작은 하위 배열에 대해
각 분할을 수행했다.
하지만 위 예제는 처음 다섯 번의
분할을
크기가 4 이상인 하위 배열에 대해
수행한다.
또한, 각 분할마다 하위 배열에
있는 원소 수 만큼 비교한다.
따라서 최악의 시나리오에서
(8+7+6+5+4+3+2)개의 원소를
분할하고, 총 35번 비교한다.
공식으로 표현하면 원소가 N개일 때
(N + (N-1) + ··· + 2)단계가 걸린다.
다음 그림에서 볼 수 있듯이,
이 값은 항상 약 (N²/2)*다.
* 정확하게는 (N+2) * ½(N-1) ＝ ½(N²+N-2) ≒ N²/2 이다.
빅 오는 상수를 무시하므로,
최악의 시나리오에서 퀵 정렬의
효율성은 O(N²)이다.
퀵 정렬을 알았으니 삽입 정렬과
비교해 보자.
최악의 시나리오에서는 동일하고,
최선의 시나리오에서는 퀵 정렬보다
삽입 정렬이 실제로 더 빠르다.
하지만 퀵 정렬이 삽입 정렬보다
훨씬 우수한 까닭은 평균 시나리오,
다시 말해 대부분의 경우 일어나는
시나리오 때문이다.
평균적인 경우에 삽입 정렬은
O(N²)이 걸ㄹ리는 반면
퀵 정렬은 훨씬 빠른 O(N logN)이다.
평균적인 상황에서 퀵 정렬이
우수하므로
내부적으로 퀵 정렬을 사용해
자신만의 정렬 함수를 구현하는
언어가 많다.
따라서 퀵 정렬을 직접 구현할
일은 거의 없다.
하지만 퀵 셀렉트라 불리는 매우
유사한 알고리즘이
실용적으로 쓸모가 있을 수 있다.
10.5 퀵 셀렉트
무작위로 정렬된 배열이 있을 때,
정렬은 안 해도 되지만 배열에서
10번째로 작은 값,
혹은 15번째로 큰 값을 알고 싶다고
가정하자.
가령 수많은 시험 점수가 있을 때
25번째 백분위수나 중간 점수를
알고 싶을 때 도움이 될 것이다.
전체 배열을 정렬한 후 적절한
셀을 바로 찾아보면
확실히 이 문제를 풀 수 있다.
하지만 퀵 정렬처럼 빠른 알고리즘을
사용한다 해도
이 알고리즘에는 최소 평균적으로
O(N logN)이 걸리는데
나쁜 방법은 아니지만 퀵 셀렉트라
알려진 뛰어난 작은 알고리즘으로
훨씬 더 나은 성능을 낼 수 있다.
퀵 셀렉트도 퀵 정렬처럼 분할에
기반하며,
퀵 정렬과 이진 검색의 하이브리드
정도로 생각할 수 있다.
10장 앞부분에서 살펴봤듯이
분할이 끝나면 피벗 값은 배열 내
올바른 위치에 있게 된다.
퀵 셀렉트는 다음과 같은 방법으로
이 정보를 활용한다.
값이 8개인 배열이 있을 때,
이 배열 내에서 2번째로 작은 값을
찾고 싶다고 가정하자.
먼제 전체 배열을 분할한다.
| (대충 분할 중) | |||||||
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할 후 피벗은 바라건대 중간
부분에 있을 것이다.
| 피벗(pivot) | |||||||
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
이제 피벗은 올바른 위치에 있고
5번째 셀이므로 어떤 값이 배열
내에서 5번째로 작은지 알게 됐다.
예제는 2번째로 작은 값을 찾고 있다.
우리는 2번째로 작은 값이 피벗의
왼쪽 어딘가에 있음도 안다.
이제 피벗의 오른쪽에 있는 모든
수는 무시하고
왼쪽 하위 배열에만 집중할 수 있다.
이 점에서 퀵 셀렉트와 이진 검색이
유사하다 볼 수 있다.
즉, 배열을 계속 반으로 나누되,
찾고자 하는 값이 있을 반쪽에만
집중하는 것이다.
다음으로 피벗 왼쪽에 있는
하위 배열을 분할한다.
| (대충 분할 중) | 피벗(pivot) | ||||||
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
이 하위 배열의 새 피벗을 임의로
3번째 셀로 정하겠다.
| 피벗(pivot) | 피벗(pivot) | ||||||
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
이제 3번째 셀의 값이 올바른
위치에 있게 됐고,
이 값이 배열에서 3번째로
작은 값임을 알아냈다.
정의에 의하면 2번째로 작은 값은
이 피벗의 왼쪽 어딘가에 있다.
이제 3번째 셀의 왼쪽에 있는
하위 배열을 분할한다.
| (대충 분할 중) | 피벗(pivot) | 피벗(pivot) | |||||
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
분할이 끝나면 가장 작은 값과
2번째로 작은 값이
배열 내에서 올바른 위치에 있게 된다.
| 기저 조건 | 피벗(pivot) | 피벗(pivot) | 피벗(pivot) | ||||
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
이제 2번째 셀에 있는 값을
가져와서
자신있게 이 값이 전체 배열 중
2번째로 작은 값이라고 할 수 있다.
퀵 셀렉트의 훌륭한 점 중 하나는
전체 배열을 정렬하지 않고도
올바른 값을 찾을 수 있다는 것이다.
퀵 정렬은 배열을 반으로 나눌 때마다
원래의 배열의 모든 셀을 다시
분할해야 하므로 시간*이 걸린다.
* O(N logN)
반면 퀵 셀렉트는 배열을 반으로
나눌 때마다 필요한 반쪽,
즉 찾고 있는 값이 있을 하위 배열만
분할하면 된다.
퀵 셀렉트의 효율성을 분석해 보면
평균 시나리오에서 O(N)이다.
앞선 예제에서 각 분할이 일어날
때마다
분할 중인 하위 배열에 대해
N단계가 걸렸다.
따라서 원소가 8개인 배열이면,
퀵 셀렉트는 8개의 원소로 이뤄진
배열과 4개의 원소로 이뤄진 배열,
그리고 2개 원소로 이뤄진 배열에
대해 3번 분할을 실행한다.
총 '8 + 4 + 2 = 14(단계)'다.
따라서 원소가 8개인 배열에는
대략 14단계가 걸린다.
원소가 64개인 배열은
64+32+16+8+4+2 = 126단계를
실행한다.
원소가 128개면 254단계일 것이다.
또한 원소가 256개면 510단계일 것이다.
공식으로 표현하면 원소가 N개일 때,
'N + (N/2) + (N/4) + ··· + 2'단계다.
합하면 항상 약 2N단계*다.
* 정확하게는 2N-2가 된다.
S = 1/2 + 1/4 + 1/8 + ··· + 0 이고
2S = 2/2 + 2/4 + 2/8 + ··· + 0 이므로,
2S-S = 2/2 + (1/2 + 1/4 + 1/8 + ··· + 0) - (1/2 + 1/4 + 1/8 + ··· + 0)
S = 2/2 = 1 이다.
위의 경우에는, 2에서 멈췄기 때문에 1과 1에서 0까지의 S를 합에서 제외한다.
따라서 N + (N-2)가 되므로, 2N-2이다.
빅 오는 상수를 무시하므로
퀵 셀렉트의 효율성은 O(N)이다.
다음 코드는 앞서 설명한
SortableArray 클래스 안에 넣을 수
있는 quickselect! 메서드 구현이다.
quicksort! 메서드와 매우 유사함을
알게 될 것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def quickselect!(kth_lowest_value, left_index, right_index)
# 기저 조건이면, 즉 하위 배열에 셀이 하나면 찾고 있던 값을 찾은 것이다.
if right_index - left_index <= 0
return @array[left_index]
end
# 배열을 분할하고 피벗의 위치를 가져 온다.
pivot_position = partition!(left_index, right_index)
if kth_lowest_value < pivot_position
quickselect!(kth_lowest_value, left_index, pivot_position - 1)
elsif kth_lowest_value > pivot_position
quickselect!(kth_lowest_value, pivot_position + 1, right_index)
else # kth_lowest_value == pivot_position
# 분할 후 피벗의 위치가 k번째 작은 값과 같으면
# 찾고 있던 값을 찾은 것이다.
return @array[pivot_position]
end
end
|
cs |
정렬되지 않은 배열에서 두 번째로
작은 값을 찾고 싶다면
다음 코드를 실행한다.
|
1
2
3
|
array = [0, 50, 20, 10, 60, 30]
sortable_array = SortableArray.new(array)
p sortable_array.quickselect!(1, 0, array.length - 1)
|
cs |
quickselect! 메서드는 1번째 인자에서
0부터 시작하는 인덱스 위치를 받는다.
2번째로 작은 값을 원하면 1을 넘긴다.
10.6. 마무리
퀵 정렬과 퀵 셀렉트 알고리즘은
골치아픈 문제를 푸는
멋지고 효율적인 해결법을 제시하는
재귀 알고리즘이다.
이해하기는 어렵지만 깊은 생각 끝에
나온 알고리즘이
얼마나 성능을 높일 수 있는지
보여주는 좋은 예다.
알고리즘만 재귀적인 것은 아니다.
자료 구조도 재귀적일 수 있다.
연결 리스트와 이진 트리, 그래프 등
이어지는 챕터들에서 살펴볼 자료 구조는
재귀적인 특징을 사용해
저마다의 기발한 방법으로 데이터에
빠르게 접근한다.
참고 및 출처
 |
|
