지금까지 1) 버블정렬 2) 선택정렬 3) 삽입정렬에 대해 살펴봤다.
오늘은 4) 퀵 정렬에 대해서 알아보자.
컴퓨터 언어에서 배열을 정렬하기 위한 내장함수가 있다.
이 덕분에, 사용자는 예를들어list.reverse()와 같은 방법으로 쉽게 배열을 정렬시킬 수 있다.
컴퓨터 언어 중 대다수에서 채택한 정렬 알고리즘이 바로 '퀵 정렬'이라고 한다.
('누구나 자료구조와 알고리즘'책 참조, 저자 : 제이 웬그로우)
1. '피봇'이란?
퀵 정렬을 구현하기 위해서 알아야할 개념이 있다.
바로 '피봇'과 '재귀'다.
재귀함수가 호출되는 내내 '분할'되는 배열의 크기는 점점 줄어든다.
이때, 배열을 분할하는 기준이 되는 값이 바로 피봇이다.
배열 [0, 5, 2, 1, 6, 3] 이 있다고 하자.
참고로, 피봇을 정의하는 방식은 다양하다.
어떤 사람은 배열의 첫번째 값을,
어떤 사람은 배열의 중간값을,
어떤 사람은 배열의 랜덤값을,
어떤 사람은 배열의 마지막 값을 피봇으로 정하는 등등
이외에도 피봇을 정하는 방법은 다양하다고 한다.
난 배열의 마지막 값을 '피봇'으로 하기로 했다.
예시로 든 배열로 보자면 맨 마지막 값 '3'이 피봇이다.
def quick_sort(list, first_index, last_index):
if first_index >= last_index:
return
# 피봇 정의
pivot = list[last_index]피봇을 제외한 [0, 5, 2, 1, 6]을 살펴볼 단계다.
우선, left_pointer 라는 변수는 인덱스 0을 가리키는 것이 default.
right_pointer라는 변수엔 인덱스 4를 가리키는 것이 default.
(right_pointer : 피봇의 인덱스 바로 이전 인덱스)
핵심은
left_pointer의 값이 피봇(3) 보다 작으면,
left_pointer를 1씩 계속 증가시키는 것이다.
반대로,
right_pointer의 값이 피봇(3) 보다 작다면
right_pointer를 1씩 계속 감소시키는 것이다.
배열 [0, 5, 2, 1, 6, 3]
-
left_pointer의 현재 인덱스는 0이다.
list[left_pointer]이 피봇 3 보다 작으므로
left_pointer는 1을 증가시켜 인덱스 1.
list[left_pointer]는 피봇 3보다 크므로, 인덱스 1 유지 -
right_pointer의 현재 인덱스는 4다.
list[right_pointer]는 피봇 3보다 크므로
인덱스를 1 감소시킨다.(인덱스 3)
list[right_pointer]는 피봇 3보다 작으므로, 인덱스 3 유지.
이렇게 left_pointer와 right_pointer의 위치가 고정되고
left_pointer < right_pointer라면,
서로가 갖고있는 값을 교환한다.
[0, 5, 2, 1, 6, 3]에서
[0, 1, 2, 5, 6, 3]으로 말이다.
아직 끝나지 않았다.
left_pointer < right_pointer이기 때문이다.
(반복하는 이유는 결국 피봇의 적절한 위치를 찾아주기 위함이다.)
현재 상황 정리:
- left_pointer는 인덱스 1 이라는 값을 가지고 있음.
- right_pointer는 인덱스 3 이라는 값을 가지고 있음
아까 진행했던 방법을 계속 반복한다.
list[left_pointer]의 값은 1이고 피봇(3)보다 작으므로
인덱스 1을 늘려준다. (left_pointer는 2)
역시, list[left_pointer]의 값 역시 2로써, 피봇(3)보다 작으므로
인덱스 1 증가. (left_pointer는 3)
right_pointer는 3 그대로다.
서로 같은 인덱스를 가리키고 있다.
이 때!
피봇과 left_pointer가 가리키는 값을 서로 교환한다.
[0, 1, 2, 3, 6, 5] 가 됐다.
여기서 정말정말 중요한 것은
피봇 3을 기준으로
좌측은 3보다 작은 값으로,
우측은 3보다 큰 값들로 나눠졌다는 사실이다.
그래서 피봇이라는 개념을 서두에 언급한 것이고,
left_pointer와 right_pointer의 작동 방식에 대해 언급한 것이다.
길게 설명한 부분을 요약하자면,
배열에 피봇의 값을 적절하게 배치시키기 위함인 것이다.
('적절하게'의 의미는 피봇 좌측은 피봇보다 작은 값들만, 우측은 피봇보다 큰 값들만)
2. '재귀'의 위력
'피봇'을 기준으로 배열을 분할했으니,
이제는 재귀함수의 위력이 나타날 때다.
우리는 방금 전까지 기존의 배열을
[0, 1, 2, 3, 6, 5]로 가공했다.(피봇은 3)
피봇 3 좌측엔 [0, 1, 2]가 있고,
피봇 3 우측엔 [6, 5]가 있는 상황이다.
맨 처음엔 전체 배열([0, 1, 2, 3, 6, 5])에 대해 피봇을 통해 정렬했다면,
이젠 피봇을 기준으로 '분할된' 두 배열에 대해서
우리가 방금했던 과정을 다시 진행해야 한다.(재귀)
[0, 1, 2]에서 다시 피봇은 배열 우측값이 2,
left_pointer는 인덱스 0,
right_pointer는 인덱스 1
잔인하면서도 재밌는 포인트는
[0, 1, 2,]를 진행하다보면 피봇의 위치 2는 그대로 현재 상태를 유지한다.
( 왜냐면 우연히 0, 1, 2라는 오름차순으로 정렬되어 있으니까 )
그럼 다시 [0, 1]에 대해서 재귀함수가 반복되고(피봇은 1)
다시 1이 현재의 위치 그대로 유지하게 되므로
마지막엔 [0] 하나에 대해서 재귀함수를 돌리게 되는 순간까지 간다.
이 모든 것이 끝나면
[0, 1, 2, 3, 6, 5]라는 배열에서
맨 처음 피봇값 3을 기준으로 좌측은 정렬이 완료된 것이다.
'재귀함수의 특성을 이해한다면 왜 그런지 알 수 있다.'
그렇다면 이제 남은 것은???
그렇다.
피봇 3의 우측 배열인 [6, 5]에 대한 재귀함수가 남아있다.
피봇은 5이며, 피봇과의 대소비교를 통해
[5, 6]이라고 정렬될 것이다.
피봇 5의 위치가 결정됐으니,
이제 다시, [6]이라는 배열에 대한 재귀함수가 진행된다.
element가 하나이니 이 때의 재귀함수는 바로 return을 한다.
이제 비로소 '퀵 정렬'이 끝난 것이다.
3. 퀵 정렬 코드
def quick_sort(list, first_index, last_index):
if first_index >= last_index:
return
pivot = list[last_index]
left_pointer = first_index
right_pointer = last_index - 1
while True:
while list[left_pointer] <= pivot and left_pointer < last_index:
left_pointer += 1
while list[right_pointer] > pivot and right_pointer > first_index:
right_pointer -= 1
if left_pointer < right_pointer:
list[left_pointer], list[right_pointer] = list[right_pointer], list[left_pointer]
else:
break
# 피봇 위치 결정
list[left_pointer], list[last_index] = list[last_index], list[left_pointer]
temp = left_pointer
index_pivot = left_pointer
# | 피봇 좌우 정렬 시작 |
# 1) 피봇 좌측 배열 정렬
quick_sort(list, first_index, index_pivot - 1)
# 2) 피봇 우측 배열 정렬
quick_sort(list, index_pivot + 1, last_index)
list = [3, 3, 2, 2, 1, 1, 1, 1, 0, 100, -1, -1 ]
max_index = len(list) - 1
quick_sort(list, 0, max_index)
print(list)다음과 같이
list = [3, 3, 2, 2, 1, 1, 1, 1, 0, 100, -1, -1 ]를 정렬해보겠다.
결과
4. 퀵 정렬에 대한 단상
사실 그 어느때보다 퀵 정렬 구현에 어려움을 느꼈다.
재귀 함수 구조를 이해하는게 쉽진 않았다.
구글링해서 바로 코드를 보고 싶은 마음은 굴뚝 같았지만,
디버깅을 하며 계속 될듯말듯한 배열을 보며
하루 정도는 더 고민해서 결국 해결했다.
개인적으로 퀵 정렬이 아름답다고 생각한다.
좋아하는 말이 하나 있는데, 그건 바로
"How do you eat an elephant?"
아무리 어려운 문제도 잘게잘게 조각내서 풀면
해결할 수 있다는 말이다.
퀵 정렬이 내겐 그렇게 다가왔다.
[3, 3, 2, 2, 1, 1, 1, 1, 0, 100, -1, -1 ] 라는 배열이 있다.
퀵 정렬은
버블정렬처럼 전체 배열을 한 번에 해결하려고 접근하는 방식이 아니다.
[1] 피봇을 하나 정하고 그 값을 기준으로 배열을 좌, 우로 나눈다.
[2] 다시 봤더니 그래도 역시 elephant는 크다.
좌측 배열을 다시 새로운 피봇을 기준으로 좌, 우로 나누다.
[3] 조각이 될 때까지 이를 반복한다.(배열의 크기가 1일 때까지)
[4] 결국 재귀함수의 재귀함수를 계속 호출하다 보면,
나는 단지 크기가 1인 배열을 해결하면 되는 것이었다..
[5] return(재귀함수 탈출)을 통해 최초에 호출했던 함수까지 돌아왔을때,
내 눈앞에는 전부 정렬된 배열이 나타나는 것이다.
마지막으로,
10개의 random한 값을 갖는 list를 임의로 생성하고
오름차순으로 정렬되는 구현 모습을 보이고 마무리하려고 한다.
list = [random.randrange(-20, 100, 2) for _ in range(10) ]
max_index = len(list) - 1
# 퀵 정렬 호출
quick_sort(list, 0, max_index)
print(list)결과
- One step at a time - 