선형 자료 구조 내에 저장된 데이터를 빠르게 정렬하는 방법의 두 번 째 포스팅이다. 지난 번에는 병합 정렬 과정을 구현하고 실행함으로써 중첩 Loop 문으로 진행하는 정렬 알고리즘보다 빠른 정렬이 가능함을 알아보았다. 이번에는 퀵 정렬(Quick Sort)이라고 하는, 이름만 들어도 무진장 빠를 듯한 정렬에 대한 내용이다.
1. 퀵 정렬 (Quick Sort)
퀵 정렬은 의외로 개념은 단순하다(구현은 생각보다 머리가 아프다). 먼저 배열 내 가운데에 위치한 값을 하나 지정한다. 이 값을 Pivot - 농구를 하셨던 분들이라면 익숙할 - 이라고 하는데, 말 그대로 배열 내 원소를 교대하는 일종의 축 또는 기준점을 말한다.
8, 4, 2, 5, 1, 3, 7 -> Pivot으로 배열 한 가운데에 위치한 5를 선택
Pivot이 정해지면, 퀵 정렬은 배열의 양 끝에서 Pivot으로 동시에 배열 내 원소의 스캔을 진행한다.
-> <-
8, 4, 2, 5, 1, 3, 7
양 방향으로 스캔을 진행하면서 값의 교대를 진행하는데, 우측으로 스캔하는 Pivot의 좌측부가 Pivot 값보다 크거나 같은 원소를 좌측으로 스캔하는 Pivot 우측부 값 중 Pivot 값보다 작거나 같은 원소와 교대를 진행한다. 이 과정은 양 방향의 스캔이 엇갈릴 때까지 진행한다. 말로는 항상 설명이 어려우니 아래의 과정을 참고하자.
8, 4, 2, 5, 1, 3, 7 : 8 >= Pivot 이나 7 >= Pivot이므로 자리 교대를 없이, 좌측 방향 스캔의 커서를 좌측으로 이동.
8, 4, 2, 5, 1, 3, 7 : 8 >= Pivot이며 3 <= Pivot이므로 두 원소의 자리를 교대한다.
3, 4, 2, 5, 1, 8, 7 : 4 <= Pivot이므로 우측 방향 스캔의 커서를 우측으로 이동.
3, 4, 2, 5, 1, 8, 7 : 2 <= Pivot이므로 우측 방향 스캔의 커서를 우측으로 이동.
3, 4, 2, 5, 1, 8, 7 : 5 >= Pivot 이며, 1 <= Pivot이므로 두 원소의 자리를 교대한다.
3, 4, 2, 1, 5, 8, 7 : 양 방향으로 이동하는 스캔 커서의 위치가 엇갈렸으므로 정렬 종료.
정렬 안 됐는데요?? 맞다. 정렬 안 되었다. 배열 크기를 조금 줄여서 다시 해보자. 이번에는 배열 크기 3이다.
ex1) 5, 3, 1 -> 1, 3, 5
ex2) 3, 5, 1 -> 3, 5, 1 -> 3, 1, 5
배열 크기 3도 정렬이 완전하지는 않다. 그냥 보기에 퀵 정렬은 모든 원소가 완전 역순이어야 동작하는 것처럼 보인다. 이제 아주 극단적으로 배열의 크기를 2로 줄여 진행해보았다.
5, 3 -> 3, 5
배열의 크기를 2로 줄이니, 그제서야 퀵 정렬이 동작하기 시작한다. 이 말인 즉, 퀵 정렬 역시 동작하는 방식은 이전 포스팅에서 살펴보았던 병합 정렬처럼 배열을 분해하여 정렬하고 합친다(Divide & Conquere)는 개념이다. 그러나 병합 정렬이 분해된 배열을 정렬하고 병합하는 프로세스라면, 퀵 정렬은 분해 전에 정렬을 진행한다는 차이점이 있다.
위에서 첫 예시로 들었던 배열의 첫 퀵 정렬 결과를 들고와서 분해한 뒤, 분해된 배열에 대해 퀵 정렬을 계속 적용해보자.
3, 4, 2, 1, 5, 8, 7 -> Pivot으로 선정된 값을 중심으로 배열 정렬 및 분해
↙ ↘
3, 4, 2, 1 5, 8, 7
↙ ↘
3, 4, 2, 1 5, 8, 7
↓ ↓
1, 4, 2, 3 5, 8, 7
↓ ↓
1, 2, 3, 4 5, 7, 8
위와 같이, 배열의 정 가운데 Index에 위치한 값을 축으로, 배열을 재정렬하고, 기준 값을 중심으로 배열을 나누어 동일한 작업을 계속해서 진행한다는 것이 골자다. 마치 병합정렬은 Bottom Up, 퀵 정렬은 Top Down 방식으로 동작하는 듯한 느낌이다.
그런데, 이러한 궁금증도 조금 든다.
"Pivot 값이 배열의 중간값이 아니라 극 값으로 지정된다면, 배열을 분해하는 깊이가 더 늘어나지 않나요..?"
일리가 있다. 위의 예시에서 사용한 동일한 배열에서 최대값 위치만 배열의 가운데로 변경한 배열로 다시 퀵 정렬을 진행해보자.
5, 4, 2, 8, 1, 3, 7
↓
5, 4, 2, 1, 3, 7, 8
↙ ↘
5, 4, 2, 1, 3, 7 8
↙ ↘
1 5, 4, 2, 3, 7
↙ ↘
2 5, 4, 3, 7
↙ ↘
3 5, 4, 7
↙ ↘
4 5, 7
↙ ↘
5 7
첫 예시에서의 정렬은 배열 분회 깊이가 5인 반면, 바로 위의 예시는 배열 깊이가 7이나 된다. 즉, 퀵 정렬은 Pivot 값으로 무엇이 선택되느냐에 따라 성능이 차이가 날 수 밖에 없다. 보통 배열이 3개 이상인 경우, 임의의 세 값을 선정하고 그 중 중앙값을 Pivot 값으로 사용하는 방법이 있긴 한데, 이 포스팅에서는 다루지 않는다(머리 뽀개질 것 같다...)
본격적으로 코드 작성을 시작해보자..
2. 퀵 정렬 구현 코드 작성
늘 그렇듯이 함수로 뼈대부터 만들 예정이다. 그리고, Pivot 값 선택과 스캔 동작까지는 큰 어려움이 없으니 바로 만들어보려한다. 정렬할 배열은 서두에 예시로 들었던 배열을 사용할 것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
def quick_sort(arr: list, left_idx:int, right_idx:int) -> None:
# Pivot 위치 및 값 변수 저장
pivot_idx: int = (left_idx + right_idx) // 2
pivot_value: int = arr[pivot_idx]
# 커서 생성
left_cursor: int = left_idx
right_cursor: int = right_idx - 1
# 커서 이동 조건 설정: 양 커서가 엇갈리면 스캔 종료
while left_cursor <= right_cursor:
# left_cursor는 Pivot보다 큰 값 또는 동일한 값이 존재하는 Index를 가리킴
while arr[left_cursor] < pivot:
left_cursor += 1
# right_cursor는 Pivot보다 작은 값 또는 동일한 값이 존재하는 Index를 가리킴
while arr[right_cursor] > pivot:
right_cursor -= 1
# 현재 상태에서는 left_idx = 1, right_index = 6 에서 무한루프
|
cs |
이제 left-cursor는 무조건 pivot 보다 작은 값을 가리키고, right_cursor는 pivot 보다 큰 값만 가리키므로, left_cursor와 right_cursor가 결정되면 단순히 두 위치의 원소를 교대해주면 된다. 조건문이 값의 대소 비교가 아니라는 점에 주의하자.
|
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
|
def quick_sort(arr: list , left_idx:int, right_idx:int) -> None:
# Pivot 위치 및 값 변수 저장
pivot_idx: int = (left_idx + right_idx) // 2
pivot_value: int = arr[pivot_idx]
# 커서 생성
left_cursor: int = left_idx
right_cursor: int = right_idx - 1
# 커서 이동 조건 설정: 양 커서가 엇갈리면 스캔 종료
while left_cursor <= right_cursor:
# left_cursor는 Pivot보다 큰 값 또는 동일한 값이 존재하는 Index를 가리킴
while arr[left_cursor] < pivot_value:
left_cursor += 1
# right_cursor는 Pivot보다 작은 값 또는 동일한 값이 존재하는 Index를 가리킴
while arr[right_cursor] > pivot_value:
right_cursor -= 1
if left_cursor <= right_cursor:
arr[left_cursor], arr[right_cursor] = arr[right_cursor], arr[left_cursor]
left_cursor += 1
right_cursor -= 1
|
cs |
위의 코드에서 주의해야 할 부분은 Line 12와 22의 조건문이다. 아무 생각없이 구현 코드를 작성하다보면 단순하게 "left_cursor가 right_cursor랑 만나면 교대할 이유가 없으니 Loop를 종료하면 되겠지"라고 생각을 하는데, 아래와 같이 완전 역순인 배열을 정렬하는 경우라면 while 문을 빠져나올 수 없게 된다.
5, 4, 3, 2, 1
-> Pivot을 중심으로 양 원소간 교대가 이루어 짐
1, 2, 3, 4, 5
-> left_cursor와 right_cursor는 모두 index2인 3에 위치.
-> 같은 값이더라도 교대가 이루어져야 left_cursor와 right_cursor 값이 엇갈리며 이동.
이 상태에서 print() 문을 몇 개 넣어 동작을 잘 하는지 확인해보자.
8, 4, 2, 5, 1, 3, 7 배열에서 left / right 커서는 0, 6번 Index에서 시작한다. 외부 while 문을 들어가면 내부의 두 while 문에 의해 left_cursor는 1, right_cursor는 5을 가리키며 두 값의 교대가 이루어진다.
=> 3, 4, 2, 5, 1, 8, 7
여전히 left_cursor의 위치는 right_cursor보다 좌측에 위치하므로 다시 외부 while 문을 실행하게 되며, left_cursor는 Pivot 위치에, right_cursor는 index 4인 1 값에 위치한다. 다시 자리 교대가 일어나면 반복문이 종료되면서 배열은 아래와 같이 수정된다.
=> 3, 4, 2, 1, 5, 8, 7
이제 Pivot 값을 중심으로 좌측은 Pivot보다 작은 값이, 우측은 Pivot보다 큰 값이 위치한다. 두 그룹으로 배열을 나누어 다시 동일한 과정을 반복해야한다. 여기까지의 변수 상태는 아래와 같다.
* left_idx = 0
* right_idx = len(arr) -1
* left_cursor = 6
* right_cursor = 5
Pivot을 중심으로 좌측의 배열은 Index 0부터 4까지이며, 우측 배열은 5부터 7까지의 Index를 포함한다. 따라서 다시 quick_sort()함수를 수행한다면 인자값을 아래와 같이 작성해 코드를 작성해주어야한다.
|
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
|
def quick_sort(arr:list, left_idx:int, right_idx:int) -> None:
# Pivot 위치 및 값 변수 저장
pivot_idx: int = (left_idx + right_idx) // 2
pivot_value: int = arr[pivot_idx]
# 커서 생성
left_cursor: int = left_idx
right_cursor: int = right_idx - 1
# 커서 이동 조건 설정: 양 커서가 엇갈리면 스캔 종료
while left_cursor <= right_cursor:
# left_cursor는 Pivot보다 큰 값이 존재하는 Index를 가리킴
while arr[left_cursor] < pivot_value:
left_cursor += 1
# right_cursor는 Pivot보다 작은 값이 존재하는 Index를 가리킴
while arr[right_cursor] > pivot_value:
right_cursor -= 1
if left_cursor <= right_cursor:
arr[left_cursor], arr[right_cursor] = arr[right_cursor], arr[left_cursor]
left_cursor += 1
right_cursor -= 1
quick_sort(arr=arr, left_idx=left_idx, right_idx=right_cursor + 1)
quick_sort(arr=arr, left_idx=left_cursor, right_idx =right_idx)
|
cs |
하지만 위 코드를 그대로 수행하면 프로그램이 종료되지 않고 계속 수행되다가 RecursionMaxTry 뭐시기 에러가 발생할 것이다. 왜냐하면 right_cursor와 left_cursor 값이 실제 배열 범위를 초과한 값이 들어가게되면 내부 코드가 전혀 동작하지 않고 계속 재귀함수만 호출하기 때문이다.
따라서 함수 앞단에 재귀 함수를 중단할 조건을 넣거나, 혹은 아래와 같이 cursor의 범위가 left_idx나 right_idx에 도달하지 않은 경우에 한해 재귀함수를 수행하도록 코드를 수정하면 된다. 바로 아래에 있는 코드는 전자를 적용한 코드이며,
|
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
|
def quick_sort(arr:list, left_idx:int, right_idx:int) -> None:
if left_idx == right_idx:
return
# Pivot 위치 및 값 변수 저장
pivot_idx: int = (left_idx + right_idx) // 2
pivot_value: int = arr[pivot_idx]
# 커서 생성
left_cursor: int = left_idx
right_cursor: int = right_idx - 1
# 커서 이동 조건 설정: 양 커서가 엇갈리면 스캔 종료
while left_cursor <= right_cursor:
# left_cursor는 Pivot보다 큰 값이 존재하는 Index를 가리킴
while arr[left_cursor] < pivot_value:
left_cursor += 1
# right_cursor는 Pivot보다 작은 값이 존재하는 Index를 가리킴
while arr[right_cursor] > pivot_value:
right_cursor -= 1
if left_cursor <= right_cursor:
arr[left_cursor], arr[right_cursor] = arr[right_cursor], arr[left_cursor]
left_cursor += 1
right_cursor -= 1
quick_sort(arr=arr, left_idx=left_idx, right_idx=right_cursor + 1)
quick_sort(arr=arr, left_idx=left_cursor, right_idx =right_idx)
|
cs |
이 코드는 후자를 적용한 코드다.
|
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
|
def quick_sort(arr:list, left_idx:int, right_idx:int) -> None:
# Pivot 위치 및 값 변수 저장
pivot_idx: int = (left_idx + right_idx) // 2
pivot_value: int = arr[pivot_idx]
# 커서 생성
left_cursor: int = left_idx
right_cursor: int = right_idx - 1
# 커서 이동 조건 설정: 양 커서가 엇갈리면 스캔 종료
while left_cursor <= right_cursor:
# left_cursor는 Pivot보다 큰 값이 존재하는 Index를 가리킴
while arr[left_cursor] < pivot_value:
left_cursor += 1
# right_cursor는 Pivot보다 작은 값이 존재하는 Index를 가리킴
while arr[right_cursor] > pivot_value:
right_cursor -= 1
if left_cursor <= right_cursor:
arr[left_cursor], arr[right_cursor] = arr[right_cursor], arr[left_cursor]
left_cursor += 1
right_cursor -= 1
if left_idx < right_cursor:
quick_sort(arr=arr, left_idx=left_idx, right_idx=right_cursor + 1)
if left_cursor < right_idx:
quick_sort(arr=arr, left_idx=left_cursor, right_idx =right_idx)
|
cs |
두 코드 모두 정상적으로 배열을 정렬하는 것을 확인할 수 있다.
위 코드의 일부 수행 과정까지 출력하면 아래와 같이 나타난다.
재귀 함수 종료 조건을 함수 초반에 설정하는 것보다 후반부에 설정하는 것이 수행 조건을 획기적으로 줄이는 것을 확인할 수 있다. 전반부에 조건을 설정하는 코드의 경우, cursor의 위치를 참조할 수 없기 때문에 재귀를 멈출 수 있는 유일한 조건은 함수 인자로 받은 left_idx 값과 right_idx 값이 동일한 경우일 뿐이다. 심지어 해당 범위 내에 원소가 존재하지 않더라도 말이다. 따라서 후반부에 재귀 조건을 걸어주는 후자의 코드와 비교했을 때, 정렬해야 할 배열이 1개가 남더라도 quick_sort() 함수를 수행하기 때문에 불필요한 작업이 추가로 진행된다는 단점이 있다.
3. 퀵 정렬의 시간 복잡도
퀵 정렬의 시간 복잡도는 평균적으로 O(N Log N) 값을 가진다. 하나의 Pivot을 선택하여 N개의 배열을 분할하는데 k번이 걸린다고 가정하면,
N = 2^K 이므로 , K = Log N (지수2는 생략)
이다. 절반으로 나뉘어진 배열에서 다시 Pivot 값을 선택하는 것은
N/2 = 2^K 이므로, (K-1) = LogN
이다. 결국 최종적으로.
N^N = 2^K 라는 공식이 튀어나오는데, 이를 정리하면, K = N log N (지수 2는 생략)이 된다.
하지만 실제 구현한 코드 내에는 Loop 문 2개가 중첩된 형태를 띄고 있기 때문에, 서두의 두 번 째 예시처럼 최소값이나 최대값이 계속해서 Pivot으로 설정되는 경우는 시간 복잡도가 N^2이 된다..
마지막으로, 지난 번에 살펴본 병합 정렬과 퀵 정렬의 수행 시간을 비교해보려한다. 지난 번과 마찬가지로 timeit 모듈을 사용해서 측정해보았다. 총 세 개의 길이가 다른 배열로 비교한 결과가 아래와 같이 나타난다.
결과를 종합해보면, 배열의 길이가 짧으면 병합 정렬이 퀵 정렬보다 빠르지만, 배열의 길이가 길면 길 수록 퀵 정렬이 병합 정렬에 비해 더 빠르게 정렬을 수행하는 것을 알 수 있다. 즉, 다량의 정렬되지 않은 데이터를 정렬할 때 퀵 정렬이 합리적인 선택임을 알 수 있다.
다음 포스팅에서는 삽입 정렬을 보완한 쉘 정렬에 대해 알아볼까 한다.
END.
'Python > Python Data Structure and Algorithm' 카테고리의 다른 글
| [자료구조 with Python] 15. 선형 자료 구조 - Stack (0) | 2024.03.19 |
|---|---|
| [자료구조 with Python] 14. 정렬 알고리즘(7), 쉘 정렬(Shell Sort) (0) | 2024.03.18 |
| [자료구조 with Python] 12 - 정렬 알고리즘(5), 병합 정렬(Merge Sort) (0) | 2024.03.13 |
| [자료구조 with Python] 11 - 정렬 알고리즘(4), 선택 정렬(Selection Sort) (0) | 2024.03.12 |
| [자료구조 with Python] 10 - 정렬 알고리즘(3), 삽입 정렬(Insertion Sort) (0) | 2024.03.11 |
댓글