인트로 정렬

인트로 정렬(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)

 참고 자료 


 Niklaus Wirth. Algorithms and Data Structures. Prentice-Hall, Inc., 1985. .

분류:비교 정렬