[Algorithm] 힙 정렬(Heap Sort)

힙 정렬은 먼저 이진 트리에서 시작하게 된다.
배열을 이진 트리라고 생각하고 그것을 힙 구조로 만드는 Build Heap 과정이 이루어진다.
힙 구조라는 것은 예로 최대 힙을 설명하면 부모 노드가 자식 노드보다 큰 힙 구조를 뜻한다.
그렇게 힙 구조가 형성이 되었다면 마지막 노드와 맨 처음 노드를 변경하고 범위를 -1해서 다시 힙구조로 만들어주는 Heapify 과정을 진행한다.
그렇게 반복하다보면 정렬이 이루어진다.
힙 정렬도 병합 정렬과 마찬가지로 최악,평균,최선의 상황에 상관 없이 O(nlogn)에 수행 시간을 갖게 된다.

코드는 힙 정렬 알고리즘을 구현한 것이다.
먼저 heapSort가 호출 되어서 하나 하나의 노드마다 최대 힙구조로 만들어주는 과정을 진행한다.
그 이후에 Heapify함수를 호출해서 가장 큰 수를 맨 뒤로 보내고 다시 범위를 줄여 힙구조로 수정하는 과정을 진행한다

이는 앞선 힙 정렬 코드의 실행 화면이다. 이진 트리를 이용한다는 점에서 다른 정렬과 다른 점에서 효율적일 수 있다는 매력적인 정렬인 것 같다.

이는 5,11,8,7,4 라는 배열을
직접 힙 정렬로 손으로 정렬 해본 것이다.
이처럼 손으로 그 과정을 정렬해보는 것도 좋은 공부가 되는 것 같다.