[바미] Sorting algorithm - Heap sort 구현하기.

Heap sort는 선택 정렬 알고리즘을 발전시킨 것으로, 최대/최소 값을 빠르게 찾을 수 있는 이진 트리(Heap)를 이용하여 정렬하는 알고리즘입니다

 

코드

function heapSort(arr) {
  // 최대 힙 구성
  function heapify(arr, i, n) {
    var parent = i;
    var left = 2 * i + 1;
    var right = 2 * i + 2;
    if (left < n && arr[left] > arr[parent]) {
      parent = left;
    }
    if (right < n && arr[right] > arr[parent]) {
      parent = right;
    }
    if (parent !== i) {
      // 부모 노드와 자식 노드 교환
      [arr[i], arr[parent]] = [arr[parent], arr[i]];
      // 교환 후 하위 트리 재귀적으로 heapify
      heapify(arr, parent, n);
    }
  }

  // 힙 정렬
  var n = arr.length;
  for (var i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, i, n);
  }
  
  for (var i = n - 1; i >= 0; i--) {
    // 최대값과 맨 뒤 값을 교환
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // 맨 뒤 값을 제외한 하위 트리 재귀적으로 heapify
    heapify(arr, 0, i);
  }
  
  return arr;
}

// 예시
var arr = [5, 2, 8, 4, 1];
console.log(heapSort(arr)); // [1, 2, 4, 5, 8]

코드 설명

이진 트리를 이용하여 정렬하는 Heap sort 알고리즘을 구현하기 위해서는 먼저 최대 힙 구성과 힙 정렬 과정을 구현해야 합니다.

그래서 heapify 함수를 사용하여 최대 힙을 구성하고, 이를 heapSort 함수 내에서 이용하여 주어진 배열을 정렬하였습니다.

 

heapify 함수는 주어진 배열에서 부모 노드와 자식 노드를 비교하여, 부모 노드가 자식 노드보다 작을 경우 두 값을 교환합니다.
이 때, 자식 노드 중에서 큰 값을 가진 노드와 교환해야 하므로, 자식 노드 중에서 최대 값을 가진 노드를 찾아야 하죠.

 

heapify 함수 내에서는 먼저 부모 노드와 왼쪽 자식 노드, 오른쪽 자식 노드를 비교하여, 가장 큰 값을 가진 노드를 찾고, 가장 큰 값을 가진 자식 노드와 부모 노드를 교환합니다. 이렇게 부모 노드와 자식 노드를 교환한 후에는, 교환된 자식 노드가 루트가 되는 하위 트리에 대해서도 heapify 함수를 재귀적으로 호출하여 최대 힙을 구성합니다.

 

heapSort 함수는 주어진 배열을 최대 힙으로 구성한 후, 최대값을 차례로 맨 뒤로 이동시키면서 정렬합니다. 먼저, 주어진 배열을 최대 힙으로 구성합니다. 

 

이후에는 배열의 마지막 인덱스부터 앞으로 이동하면서, 맨 앞에 있는 원소와 현재 위치의 원소를 교환하고, 교환한 위치를 제외한 하위 트리에 대해서 heapify 함수를 호출하여, 다시 최대 힙을 구성합니다. 이를 배열의 첫번째 인덱스까지 반복하면, 주어진 배열이 정렬된 상태가 됩니다.

따라서, heapify 함수와 heapSort 함수를 적절히 조합하여, 이진 트리를 이용한 Heap sort 알고리즘을 구현할 수 있습니다.