전산 기초/알고리즘
[정렬] 큌정렬 (Quick Sort)
은져미
2015. 10. 26. 15:07
* 퀵정렬 (Quick Sort)
"전체 원소에 대해서 정렬을 수행하지 않는다"
- Divide and Conquer (분할 정복) : 재귀적 구현 필요
기준값(pivot) 을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할(divide)
기준값(pivot) 보다 큰 원소는 배열의 오른쪽, 기준값(pivot) 보다 작은 원소는 배열의 왼쪽으로 이동
- 실행 성능은 선택한 기준값(pivot) 에 의해 결정
- 일반적으로 기준값(pivot) 은 전체 원소 중에서 가운데 위치한 원소를 선택
[시간 복잡도]
* 최선의 경우, 평균의 경우 : O(nlogn)
pivot 에 의해서 원소들이 왼쪽 부분집합과 오른쪽 부분집합으로 정확히 n/2개씩 이등분이 되는 경우가 반복
* 최악의 경우 : O(n^2)
pivot 에 의해 원소들을 분할했을 때 1개와 n-1개로 한쪽이 치우쳐 분할되는 경우가 반복
<퀵정렬은 같은 시간복잡도를 가지는 다른 정렬 방법에 비해서 자리 교환 횟수를 줄임으로써 실행 시간 성능 향상>