정렬 알고리즘 - 힙 정렬

힙 정렬(Heap Sort)

• 힙 정렬은 비교 기반 정렬 알고리즘이다.
• 선택 정렬 알고리즘과 비슷하게 정렬 된 영역과 아닌 영역을 나누어 가장 큰 요소를 찾아 정렬된 영역으로 배치시킨다.(오름차순 기준)
• 선택 정렬 보다 개선된 점은 선형 시간이 소요되는 선택 정렬의 탐색과 달리 힙 자료구조를 사용하여 최댓값을 탐색한다.
• 선택 정렬 시간 복잡도 : O(N^2)
• 힙 정렬 시간 복잡도 : O(nlog(n))

시간복잡도

• 최선의 경우 : O(nlog(n))
• 최악의 경우 : O(nlog(n))
  
  

장점

• 최악의 경우에도 O(nlog(n)) 의 빠른 속도가 보장된다.
• 추가적인 메모리를 필요로 하지 않는다.
  
  

단점

• 정렬간의 데이터 안정성을 보장받지 못한다. 즉, 중복의 데이터의 경우 순서가 바뀌는 unstable한 알고리즘
• 데이터의 상태에 따라 다른 정렬법 보다 느릴 수 있다.
  
  

구현

function HeapSort(arr) {
  for (let i = parseInt(arr.length / 2); i >= 0; i--) {
    Heapify(arr, i);
  }

  for (let i = arr.length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    Heapify(arr, 0, i);
  }

  return arr;
}

function Heapify(arr, idx, length = arr.length) {
  let leftIdx = idx * 2 + 1;
  let rightIdx = idx * 2 + 2;
  let max = idx;

  if (leftIdx < length && arr[leftIdx] > arr[max]) {
    max = leftIdx;
  }

  if (rightIdx < length && arr[rightIdx] > arr[max]) {
    max = rightIdx;
  }

  if (max !== idx) {
    [arr[idx], arr[max]] = [arr[max], arr[idx]];
    Heapify(arr, max, length);
  }

  return arr;
}

console.log(HeapSort([6, 5, 3, 1, 8, 7, 2, 4]));