힙 정렬: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
편집 요약 없음 태그: m 모바일 웹 고급 모바일 편집 |
발명자 및 일부 출처 추가 |
||
9번째 줄:
|공간복잡도 = <math>O(1)</math>
}}
'''힙 정렬'''(Heap sort)이란 최대 [[힙 (자료 구조)|힙]] 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다
힙 정렬은 1964년 [[J. W. J. 윌리엄스]]에 의해 발명되었다.<ref>{{harvnb|Williams|1964}}</ref> 이 발명 연도는 윌리엄스가 유용한 자료 구조로서 이미 제시한 힙의 탄생일이기도 하다.<ref name="brass">{{cite book |first=Peter |last=Brass |title=Advanced Data Structures |publisher=Cambridge University Press |year=2008 |isbn=978-0-521-88037-4 |page=209}}</ref> 같은 해, [[로버트 플로이드|R. W. 플로이드]]는 제자리 정렬을 할 수 있는 개선판을 출판하였으며 이는 윌리엄스의 초기 연구를 [[트리정렬]] 알고리즘으로 이어나가게 한 것이다.<ref name="brass"/>
최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.
== 알고리즘 ==
줄 147 ⟶ 151:
}
</syntaxhighlight>
== 각주 ==
{{각주}}
{{정렬 알고리즘}}
{{토막글|컴퓨터 과학}}
| |||