
Quick sort
·
📚 STUDY/📈 알고리즘
Divide-and-conquer를 기반으로 하는 정렬 알고리즘으로, 방식은 아래와 같다.1. Pivot 선택 : 배열에서 하나의 원소를 pivot으로 선택한다. 2. 분할 : pivot을 기준으로 pivot보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 배열한다.3. 재귀 호출 : 왼/오른쪽 부분 배열에 quick sort를 재귀적으로 수행한다. 💡 이상적인 경우 pivot이 항상 배열을 거의 절반으로 나누는 경우, T(n) = 2T(n/2)+O(n) 재귀식을 따른다.마스터 정리를 이용하면, T(n)=O(nlogn)이 된다. 💡 최악의 경우pivot이 항상 가장 작거나 or 큰 원소를 선택하는 경우이다.(= 배열이 거의 정렬되어 있거나 역순일 때 잘못된 pivot을 선택한다는 말)이때, partit..