힙정렬
-
[56회 변리사 2차-3번] Heap Sort알고리즘 2020. 6. 2. 16:52
2019년 제 56회 변리사 2차 데이터 구조론 2교시 3번 문제 해설 Heap Sort (힙 정렬) 힙정렬을 하기 위해서는 데이터가 힙구조 상태여야한다. 따라서 힙정렬 전에 데이터를 먼저 Heapify Algorithm으로 힙구조를 만든다. (힙구조는 여러개 나올 수 있다.) 오름차순 정렬을 위해 Max Heap을 구성하여 Max Heap의 가장 끝에 해당하는 리프노드와 root를 Swap하면 가장 큰 값이 가장 끝에 위치하게 된다. 가장 끝에 가장 큰 값이 위치 했으므로 가장 끝의 위치를 N이라고 하면 N-1의 위치에 그 다음으로 가장 큰 값을 위치시키면 된다. 이후 부터 다시 Max Heap 만들고 리프와 루트의 Swap (N-1)번 작업하며 정렬하는 알고리즘이다. 참고 ↓ https://www..