우선 이 분야의 책을 여러 권 읽어보시기를 추천합니다.
또한 Wikipedia를 비롯 web surfing을 해보세요.
보통 대학교
내에서는 논문을 자유롭게 얻을 수 있기 때문에 재학중이시라면 논문을 참고하는 것도 매우 좋습니다.
제가 'Algorithm' 수업을 들을
때 교수님께서 Hoare의 Quicksort 논문을 찾아보라는 보너스 숙제를 내셔서
찾아보고는 생각보다 훨씬 심도있는 이야기로 놀랬던
기억이 있습니다.
저는 그냥 정렬함수 하나 제작했다라로 끝날 줄 알았는데 그렇지가 않더라고요.
원전을 찾아보는 것은 항상 좋은 것
같습니다. 그리고 관련 변형 algorithm에 대한 논문도 많이 있습니다.
Heap은 완전 정렬은 아니며, 적당히 정렬된 상태를 만드는 방식입니다. 완전이항트리(Complete Binary Tree)이기
때문에
C array 처럼 일차원으로 펼쳐놓고, index 만으로 부모 자식 관계를 찾을 수 있어서 동적할당을 통해 노드를
할당하는
트리구현보다 훨씬 성능이 좋습니다. Heap은 최대원소를 찾기 편하고 (O(1)입니다), 최대원소를 제거한 후 깨진 Heap
구조를 재조정하는데
O(log n) 연산으로 가능합니다. 또한 최초에 Heap을 만드는데 걸리는 연산은 O(n)이면
가능합니다.
그리고 이런 모든 연산에 추가적으로 요구되는 공간복잡도는 O(1)이므로 공간제약요소도 받지 않습니다.
이런 특성으로
Heap을 통해 매우 효율적인 정렬 algorithm 제작이 가능합니다.
하지만 정렬에 사용되는 기본연산인 비교와 대입이 원소 수에 따라
거의 일정하기 때문에 초기 원소들의 배치상황에 따라 더 짧은 시간 내에
정렬이 끝나는 특성은 얻지 못합니다. 또한 최대원소 제거 후
Heap 구조를 재조정하는 연산이 배열을 전체적으로 다 훑고 지나가므로
참조지역성의 특성을 활용한 cache의 성능가속을 얻기가
어렵습니다.
이런 이유로 Heapsort는 Quicksort에게 정렬의 대명사를 내주었으며, 대신 Heap은 우선순위큐를 만드는데 많이
활용됩니다.
우선순위큐는 최대원소를 빼내면서 원소를 중간마다 추가할 수 있어야 한다는 요구사항을 반영한 자료구조이므로 Heap이 아주
적당하죠.
Quicksort와 Heapsort를 중심으로 만들어진 혼합정렬인 Introsort를 만든 저자들의 노트가 있습니다.
참고하시기
바랍니다.
http://www.osl.iu.edu/~kyross/pub/introsort-print.pdf
http://www.cs.rpi.edu/~musser/gp/algorithm-concepts/introsort-screen.pdf
또한 다음 자료는 위 노트보다 좀더 자세한 자료가 있습니다.
http://ralphunden.net/?q=a-guide-to-introsort
제 생각에는 Quicksort에도 단점이 있습니다만 결국 제품코드로 들어가는 것이 Quicksort 변형이라는 것과
재귀를 사용한다는
점이 학생들에게 재귀를 가르치는 좋은 예라는 것, 마지막으로 Heap이라는 다소 특이한 자료구조와
그 연산들을 이해하는 어려움이
Heapsort가 Quicksort에게 밀린 요인이 아닐까라는 그런 생각이 듭니다.