인트로 정렬
| 분류 | 정렬 알고리즘 |
|---|---|
| 자료 구조 | 배열 |
| 최악 시간복잡도 | O(n log n) |
| 평균 시간복잡도 | O(n log n) |
인트로 정렬(introsort)은 평균적으로 빠른 성능을 내면서 최악의 조건에서도 점진적으로 최적화된 성능을 제공하는 하이브리드 정렬 알고리즘이다. 퀵 정렬로 시작한 다음 재귀 깊이가 정렬 대상 요소의 수의 레벨(로그)을 초과할 때 힙 정렬로 전환하며 요소들의 수가 특정 임계치 미만일 때 삽입 정렬로 전환한다. 3가지 알고리즘의 좋은 부분을 합쳐놓은 것이며 인트로 정렬이 사용하는 이 3가지 알고리즘들은 비교 정렬이기 때문에 인트로 정렬 또한 비교 정렬이다.
Musser(1997)에서 David Musser가 발명하였다. 그는 또, 인트로셀렉트라는 퀵셀렉트 기반 하이브리드형 선택 알고리즘를 선보이기도 했다.
의사코드[편집]
procedure sort(A : array):
let maxdepth = ⌊log2(length(A))⌋ × 2
introsort(A, maxdepth)
procedure introsort(A, maxdepth):
n ← length(A)
if n < 16:
insertionsort(A)
else if maxdepth = 0:
heapsort(A)
else:
p ← partition(A) // assume this function does pivot selection, p is the final position of the pivot
introsort(A[1:p-1], maxdepth - 1)
introsort(A[p+1:n], maxdepth - 1)
참고 자료[편집]
- Musser, David R. (1997). “Introspective Sorting and Selection Algorithms”. 《Software: Practice and Experience》 27 (8): 983–993. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#.
- Niklaus Wirth. Algorithms and Data Structures. Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.