quick sort (1) 썸네일형 리스트형 32. Quick Sort 병합 정렬은 $\Theta(n\text{ lg }n)$의 시간복잡도를 갖지만 메모리 사용량이 너무 많다는 문제가 있다. 이러한 문제가 발생하지 않으면서 병합 정렬과 같은 평균 시간복잡도를 갖는 정렬 방법으로 퀵 정렬(Quick Sort)이 있다. 퀵 정렬은 한 원소의 위치를 고정하고 앞뒤 원소들을 같은 방법으로 정렬하는 분할 정복 기법의 일종이며, 평균적인 상황에서 최고의 성능을 보이지만 최악의 시간복잡도는 $\text{O}(n^2)$라는 문제점이 존재하며, 동일한 값이 여러 개 존재하는 경우 정렬 과정에서 상대적인 순서가 바뀔 수 있다. 퀵 정렬의 과정을 요약하면 다음과 같다. 1. 피벗을 고른다. 2. 피벗보다 뒤에 나와야 하는 첫 번째 원소 $a_i$를 찾는다. 3. 피벗보다 앞에 나와야 하는 마지.. 이전 1 다음
