퀵 정렬 알고리즘은 정렬 대상을 분할하여 해결하는 알고리즘입니다. 하나의 기준값(pivot)을 정해서 정해진 기준값을 기준으로 분류하는데 아래 처럼 여러가지 방법이 있습니다.
- 항상 첫번째 요소를 기준값으로 선택한다.
- 항상 마지막 요소를 기준값으로 선택한다.
- 무작위 요소를 기준값으로 선택한다.
- 가운데 요소를 기준값으로 선택한다.
그리고 퀵 정렬의 핵심은 분류(partition)입니다. 분류는 배열과 기준 값이 주어지면 기준값 보다 작은값의 요소는 앞쪽에 큰 값의 요소들은 기준값보다 뒤쪽에 위치하도록 해야하며 이러한 작업은 선형시간(linear time)안에 이루어져야 합니다.
분류(partition) 알고리즘
분류 알고리즘은 다양한 방법이 있을 수 있지만 그 중 하나인 왼쪽끝의 요소부터 모든 요소를 기준값과 비교해 작거나 같은 값만 왼쪽으로 위치를 변경하는 방법으로 구현해보겠습니다.
def partition(arr, low, high):
# 인덱스: 처음에는 low 보다 작은 값으로 초기화
# 정렬값보다 작은 값의 위치를 좌측으로 변경시키기 위한 위치 값 인덱스임.
i = low - 1
# 기준값이자 올바른 위치로 정렬할 값
pivot = arr[high]
for j in range(low, high):
# 만약 현재 요소가 기준 값보다 작다면
if arr[j] < pivot:
# 값을 정렬하기 위해 인덱스를 1 증가
i = i + 1
# 인덱스의 위치값과 현재 요소의 값의 위치 교환
arr[i], arr[j] = arr[j], arr[i]
# 모든 분류가 완료되면 마지막 인덱스 바로 뒤의 값과 기준값의 위치 교환
arr[i + 1], arr[high] = arr[high], arr[i + 1]
# 기준값의 최종 변경된 위치 값을 리턴
return i + 1분류가 완료되면 기준값보다 왼쪽에는 모두 작은 값이 위치해있으므로 가장 마지막 인덱스(기준값보다 작은 값들의 마지막 인덱스)의 다음 인덱스(+1)이 기준값이 올바르게 정렬된 위치가 됩니다. ( 주의할 점은 기준값보다 작은 요소들까지 올바르게 정렬된 게 아니라 기준값만 정렬된 것입니다.)
분류가 처음 실행되는 시점의 예시를 그림과 함께 살펴보며 상세하게 이해해보겠습니다.
분류 함수를 실행하는 경우 아래의 순서를 따라 기준값이 올바른 위치로 이동됩니다.
- j = 0, i = -1
0번 요소(20)이 기준값(70)보다 작으므로 좌측 최종 인덱스 i 를 1 증가시키고 i번 요소와 0번 요소의 위치를 교환
=> arr[-1+1], arr[0] = arr[0], arr[-1+1]
=> arr[0], arr[0] = arr[0], arr[0] - j = 1, i = 0
1번 요소(80)이 기준값(70)보다 크므로 무시 - j = 2, i = 0
2번 요소(50)이 기준값(70)보다 작으므로 좌측 최종 인덱스 i를 1 증가시키고 i번 요소와 2번 요소의 위치를 교환
=> arr[0+1], arr[2] = arr[2], arr[0+1]
=> arr[2], arr[1] = arr[1], arr[2] - j =3, i = 1
3번 요소(40)이 기준값(70)보다 작으므로 좌측 최종 인덱스 i를 1 증가시키고 i번 요소와 3번 요소의 위치를 교환
=> arr[1+1], arr[3] = arr[3], arr[1+1]
=> arr[2], arr[3] = arr[3], arr[2] - j = 4, i = 2
4번 요소(30)이 기준값(70)보다 작으므로 좌측 최종 인덱스 i를 1 증가시키고 i번 요소와 4번 요소의 위치를 교환
=>arr[2+1], arr[4] = arr[4], arr[2+1]
=>arr[3], arr[4] = arr[4], arr[3] - 모든 요소를 순회하였으므로 최종적으로 기준값(70)보다 작은 값들이 arr[0] ~ arr[i] 위치에 존재하게 된다.
이제 기준값은 arr[i+1] 위치(작은값들 바로 뒤)가 올바른 위치이므로 arr[i+1] 과 arr[high] 요소를 교환한다
( 여기서 i는 5번 순서를 거쳐 최종적으로 3(2+1) 이 된 상태. )
=> arr[3+1], arr[5] = arr[5], arr[3+1]
=> arr[3], arr[5] = arr[5], arr[3] - 기준값(70)은 기준값보다 작은 요소들의 바로 뒤의 위치로 올바르게 이동되었으며
함수는 기준값이 이동한 올바른 위치 인덱스 i + 1 을 리턴하며 종료한다.
결국, 퀵 정렬은 분류 작업을 모든 요소에 반복하며 정렬하는 방법이 되는 것입니다.
최종 퀵 정렬 구현 코드
def quick_sort(arr, low, high):
if low < high:
# pi는 arr[high]가 파티션 처리 후 올바르게 정렬된 위치 인덱스(즉 arr[pi]는 올바른 위치에 정렬된 요소)
pi = partition(arr, low, high)
# 배열의 기준값 이전(좌측) 요소와 이후(우측) 요소들을 분리해서 정렬한다.
# partition 처리를 재귀적으로 호출.
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
if __name__ == '__main__':
arr1 = [20, 80, 50, 40, 30, 70]
quick_sort(arr1, 0, len(arr1) - 1)
print("Sorted array is:", arr1)
# 결과: Sorted array is: [20, 30, 40, 50, 70, 80]마치며
마지막으로 퀵 정렬의 특징에 대해 살펴보겠습니다.
- 시간복잡도
최상의경우: \(O(n\log_2{}n)\)
최악의경우: \(O(n^2)\) - 공간복잡도
\(O(n\log_2{}n)\) - 불완전 정렬 ( unstable sort )
기존의 키 값이 유지되지 않으므로 키값을 유지해야 하는경우에는 사용하면 안된다. - 정렬된 리스트에서의 속도 저하
정렬된 리스트에 대한 퀵 정렬은 수행 시간이 더 늘어날 가능성이 있다.
이상으로 퀵정렬에 대해 알아보았습니다. 감사합니다.