반응형
6. 힙 정렬(heap sort)
By RolandH, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=3330798
힙 정렬이란?
리스트를 이진 트리 구조로 배치한뒤 최대 힙을 구성하면,
근노드가 최댓값을 가지게 되는데
이 최댓값을 리스트의 가장 끝으로 이동시킨 뒤 remove시킴.
e.g.) 오름차순 힙 정렬 이미지
By Swfung8 - 자작, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14957305
[ 장점 ]
- 시간복잡도면에서 효율적인 편
- 추가적인 메모리 사용이 없어, 메모리 제약 상황에서도 사용 가능함
[ 단점 ]
- 불안정한 정렬(unstable)
시간 복잡도 : O(nlogn)
공간 복잡도 : O(1)
반응형
'알고리즘' 카테고리의 다른 글
| 알고리즘 8 [너비 우선 탐색, BFS] (0) | 2025.02.25 |
|---|---|
| 알고리즘 7 [깊이 우선 탐색, DFS] (0) | 2025.02.18 |
| 알고리즘 5 [퀵정렬, quick sort] (0) | 2025.02.10 |
| 알고리즘 4 [병합정렬, merge sort] (0) | 2025.02.06 |
| 알고리즘 3 [삽입정렬, insertion sort] (0) | 2025.02.05 |