반응형
C. Hoare가 고안, 가장 인기 있는 Sorting으로 일반적으로 속도가 매우 빠르다. 어떤 키 값을 중심으로 (a[i]) 왼쪽으로 부터는 키 값보다 큰 값을, 오른쪽으로 부터는 키 값보다 작은 값을 찾아서 교환하는 방법이다.
1. 기준값(Pivot)을 하나 선택하여
2. 그 기준값보다 작은 항목들은 모두 배열의 왼쪽으로
3. 그 기준값보다 큰 항목들은 모두 배열의 오른쪽으로
4. 왼쪽 부분 배열에 퀵정렬을 재귀적으로 적용
5. 오른쪽의 부분 배열에 퀵 정렬을 재귀적으로 이용
다음 그림은 1,2,3에 대해서 수행하는 그림이다
문제는 Pivot에 따라서 이 알고리즘으 수행 속도가 영향을 받는다, Pivot이 정 중앙 값일 수록 빨라지며, 최악의 경우 O(N^2)까지도 속도가 나올수 있다. Pivot을 구하는 가장 유명한 방법으로는 3중앙(median-of-three) 알고리즘으로 첫번쨰, 중간, 마지막 색인의 값중 가운데 값을 기준값으로 사용하는 것이다.
평균적으로 O(NlogN)의 알고리즘이다.
반응형
