Goal
- Quick Sort에 대해 설명할 수 있습니다.
- Quick Sort 과정에 대해 설명할 수 있습니다.
- Quick Sort 를 구현할 수 있습니다.
- Quick Sort의 시간복잡도와 공간복잡도를 계산할 수 있습니다.
- Quick Sort의 처악의 경우를 개선시킬 수 있습니다.
Abstract
Quick Sort는 분할 정복(divide and conquer) 방법 을 통해 주어진 배열을 정렬합니다.
Quick Sort는 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속합니다. 또한 Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할합니다.
Process (Ascending)
- 배열 가운데서 하나의 원소를 고릅니다. 이렇게 고른 원소를 피봇(pivot) 이라고 합니다.
- 피봇 앞에는 피봇보다 값이 작은 모든 원소들이 오고, 피봇 뒤에는 피봇보다 값이 큰 모든 원소들이 오도록 피봇을 기준으로 배열을 둘로 나눕니다. 이렇게 배열을 둘로 나누는 것을 분할이라고 합니다. 분할을 마친 뒤에 피봇은 더이상 움직이지 않습니다.
- 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복합니다.
- 재귀 호출이 한 번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있습니다.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
lesser_arr, equal_arr, greater_arr = list(), list(), list()
for num in arr:
if num < pivot:
lesser_arr.append(num)
elif num > pivot:
greater_arr.append(num)
else:
lesser_arr.append(num)
return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)피봇 값이 최소나 최대값으로 지정되어 파티션이 나누어지지않는 경우 O(n^2)에 대한 시간복잡도를 가집니다. 즉, 정렬하고자 하는 배열이 오름차순으로 정렬되어있거나 내림차순으로 정렬되어있으면 O(n^2)의 시간복잡도를 가집니다. 이때, 배열에서 가장 앞에 있는 값과 중간 값을 교환해준다면 확률적으로나마 시간복잡도 O(nlogn)으로 개선할 수 있습니다.
시간복잡도
최선의 경우(Best cases): T(n) = O(nlogn)
-
순환 호출의 깊이
레코드의 개수 n이 2의 거듭제곱이라 가정했을 때 순환 호출의 깊이는 logn이 됩니다.
-
각 순환 호출 단계의 비교 연산
각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어집니다.
따라서, 최선의 시간복잡도는순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = nlog2이 됩니다.
최악의 경우(Worst cases): T(n) = O(n^2)
최악의 경우는 정렬하고자 하는 배열이 오름차순 정렬되어있거나 내림차순으로 정렬되어 있는 경우입니다.
- 순환 호출이 깊이
레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, 순환 호출의 깊이는 n 임을 알 수 있습니다.
- 각 순환 호출 단계의 비교 연산
각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어집니다.
따라서, 최악의 시간복잡도는 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = n^2
공간복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.
장점
- 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피봇들이 추후 연산에서 제외되는 특성 때문에 시간복잡도가 같은 다른 정렬 알고리즘을 비교했을 때도 가장 빠릅니다.
- 정렬하고자하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않습니다.
