5. 퀵 정렬(Quick Sort)
2020.09.29
퀵 정렬은 분할 정복법을 이용한 정렬 알고리즘이다. 기준 원소 $p$(pivot)를 정하여 정렬하고자 하는 리스트를 $LT$ ($p$보다 작은 원소들), $EQ$ ($p$와 같은 원소들), $GT$ ($p$보다 큰 원소들)의 세 부분으로 분할하고, $LT$와 $GT$를 재귀를 통해 각각 정렬 후, 세 부분을 합쳐 정렬을 완료한다. def quickSort(L): if len(L)> 1: i = -1 # pivot, 보통은 마지막 원소를 사용 LT, EQ, GT = partition(L, i) quickSort(LT) quickSort(GT) L = merge(LT, EQ, GT) return L 리스트 분할 리스트의 각 원소를 차례대로 꺼내어 기준 원소 p와 비교하여 분할하기 때문에, 분할 단계는 $O(..