[JS] 힙 정렬

힙 정렬(Heap Sort)은 힙 생성 알고리즘를 이용하여 정렬하는 방법이다. 힙 생성 알고리즘은 특정한 노드의 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 또한 위치를 바꾼 후에도 자식이 존재하는 경우, 비교 연산을 수행하여 더 큰 자식과 자신의 위치를 바꾸어야한다. 따라서 최대 힙의 경우, 루트 노드의 원소는 가장 큰 수가 된다. 힙 생성 알고리즘에 대해서는 이전에 포스팅한 적이 있다. 그래서 이번 포스팅에서는 따로 설명하지는 않겠다. 그런데 힙 생성 알고리즘의 시간 복잡도는 몇 일까? 정답은 $$ O(nlog_{2}N) $$ 이다. 왜냐하면 한 번 자식노드가 증가할 때마다 노드의 개수가 2배씩 증가하기 때문이다. 예를 들어 데이터가 1024개라면 대략 10번 정도만 내려가면 된다...

2020.06.15