문제
다음 중 힙 정렬(Heap Sort)에 대한 설명으로 가장 옳은 것은?
① 최악의 경우에도 O(n log n)의 시간 복잡도를 보장한다 ② 추가적인 메모리 공간이 필요한 외부 정렬이다 ③ 입력 데이터의 초기 순서에 따라 성능이 크게 좌우된다 ④ 동일한 키 값을 가진 요소들의 상대적 순서가 보장된다
정답
1번
해설
힙 정렬은 최악의 경우에도 O(n log n)의 시간 복잡도를 보장하는 정렬 알고리즘이다. ② 힙 정렬은 제자리 정렬(in-place sort)로 추가 메모리가 거의 필요하지 않다. ③ 퀵 정렬과 달리 초기 데이터 순서에 관계없이 일정한 성능을 보인다. ④ 힙 정렬은 불안정 정렬(unstable sort)로 동일한 키 값의 상대적 순서가 보장되지 않는다.