바닐라 자바스크립트로 힙 정렬(Heap Sort) 구현하기

힙 정렬(Heap Sort)은 대표적인 비교 기반 정렬 알고리즘입니다. 개선된 선택 정렬(selection sort)이라고 생각할 수 있는데, 선택 정렬과 마찬가지로 입력 배열을 '정렬된 영역'과 '정렬되지 않은 영역'으로 나누고, 정렬되지 않은 영역에서 목표 값(최댓값 또는 최솟값)을 추출해 정렬된 영역으로 옮기는 작업을 반복하며 정렬되지 않은 영역을 점차 줄여 나가는 방식으로 동작합니다.

힙 정렬의 동작 원리

힙 정렬은 이진 힙(binary heap) 자료구조를 활용합니다. 배열을 완전 이진 트리 형태로 해석한 뒤, 부모 노드가 항상 자식 노드보다 큰 최대 힙(max heap)을 구성하면 루트에는 항상 최댓값이 위치하게 됩니다. 이후 루트 값을 배열의 마지막 요소와 교환하고 힙의 크기를 하나 줄인 다음 다시 힙을 재구성하는 과정을 반복하면 오름차순으로 정렬된 배열을 얻을 수 있습니다. 시간 복잡도는 평균 및 최악의 경우 모두 O(n log n)으로 안정적인 성능을 보입니다.

예제 코드

바닐라 자바스크립트로 구현한 전체 코드는 다음과 같습니다.

const constructHeap = (arr, ind) => {
    let left = 2 * ind + 1;
    let right = 2 * ind + 2;
    let max = ind;
    if (left < len && arr[left] > arr[max]) {
        max = left;
    }
    if (right < len && arr[right] > arr[max]) {
        max = right;
    }
    if (max != ind) {
        swap(arr, ind, max);
        constructHeap(arr, max);
    }
}
function swap(arr, index_A, index_B) {
    let temp = arr[index_A];
    arr[index_A] = arr[index_B];
    arr[index_B] = temp;
}
function heapSort(arr) {
    len = arr.length;
    for (let ind = Math.floor(len / 2); ind >= 0; ind -= 1) {
        constructHeap(arr, ind);
    }
    for (ind = arr.length - 1; ind > 0; ind--) {
        swap(arr, 0, ind);
        len--;
        constructHeap(arr, 0);
    }
}
const arr = [3, 0, 2, 5, -1, 4, 1];
heapSort(arr);
console.log(arr);
var len;

코드 설명

constructHeap 함수는 특정 인덱스를 루트로 하는 서브트리를 최대 힙 조건에 맞게 재구성하는 역할을 합니다. 왼쪽 자식(2*i+1)과 오른쪽 자식(2*i+2) 중 더 큰 값을 찾아 현재 노드와 교환하고, 교환이 발생하면 재귀적으로 아래쪽 힙도 다시 정비합니다. heapSort 함수는 먼저 배열 전체를 최대 힙으로 만든 뒤, 루트(최댓값)를 배열 끝으로 옮기는 과정을 반복하여 정렬을 완성합니다.

실행 결과

위 코드를 실행하면 콘솔에 다음과 같이 오름차순으로 정렬된 배열이 출력됩니다.

[
    -1, 0, 1, 2,
    3, 4, 5
]