JavaScript_Heap Sort

힙정렬 구현한 코드(오름차순)

function mySort_heap() {
  let heap = [6, 8, 9, 4, 3, 5, 7]
  for (let i = 1; i < heap.length; i++) {
    let child = i
    do {
      let parent = Math.floor((child - 1) / 2) //부모 인덱스 추출
      if (heap[parent] < heap[child]) {
        ;[heap[parent], heap[child]] = [heap[child], heap[parent]]
      }
      child = parent
    } while (child != 0)
  }

  // 크기를 줄여가며 반복하여 힙을 만든다.

  for (let i = heap.length - 1; i >= 0; i--) {
    ;[heap[0], heap[i]] = [heap[i], heap[0]] // 가장 큰 값을 오른쪽으로 보내고 기존 배열의 마지막 부분을 앞으로 가져옴

    let parent = 0 // parent 초기화

    do {
      child = 2 * parent + 1 // child의 인덱스 구함
      if (child < i - 1 && heap[child] < heap[child + 1]) {
        // 인덱스값이 i-1 보다 작고 해당 child 값이 child + 1 보다 작으면 인덱스값 늘려주기
        child++
      }
      if (child < i && heap[parent] < heap[child]) {
        // child가 i 인덱스값보다 작고 child가 parent 보다 크면 자리 바꾸기
        ;[heap[parent], heap[child]] = [heap[child], heap[parent]]
      }
      parent = child // 이미 정렬된 힙 아래로 내려갈 필요 없게
      console.log(child)
    } while (child < i)
  }
  console.log(heap)
}

mySort_heap()

힙정렬이란?

힙정렬은 최대 힙(Max Heap) 자료구조를 사용하여 정렬하는 알고리즘으로, 주어진 배열을 힙으로 만들고 루트 노드(최대값)를 추출하여 정렬된 배열을 생성한다. 이를 반복하여 모든 요소가 정렬될 때까지 진행함.

동작순서

초기 배열을 힙으로 변환(Build Heap): 주어진 배열을 최대 힙(Max Heap)으로 만든다. 이를 위해 배열의 요소들을 차례대로 힙에 삽입하면서 부모 노드와 비교하여 교환하는 과정을 거친다. (=heapify)

루트 노드(최대값 또는 최소값)를 배열의 마지막 요소와 교환: 최대 힙에서는 루트 노드가 최대값이므로 이 값을 배열의 마지막 요소와 교환. 최대값이 배열의 마지막에 위치하게 됨.

힙 크기를 줄이고 다시 힙을 구성: 힙에서 루트 노드를 제거했으므로 힙의 크기를 줄이고, 남은 요소들을 다시 최대 힙으로 만든다.

위의 단계를 반복: 남은 요소가 1개가 될 때까지 위의 두 단계를 반복, 배열의 모든 요소가 정렬될 때까지 이 과정을 계속 진행한다.

장점

1. 고정적인 시간 복잡도: 힙정렬은 항상 O(n log n)의 시간 복잡도를 가짐.

2. 제자리 정렬 (In-Place Sorting): 힙정렬은 제자리 정렬 알고리즘으로, 추가적인 메모리를 필요로 하지 않아 메모리 사용에 효율적

단점

1. 비교적 느린 성능: 일부 간단한 정렬 알고리즘들보다 힙정렬은 상대적으로 느릴 수 있음. 특히 데이터가 이미 정렬되어 있는 경우에도 배열을 힙으로 변환하는 데 시간이 소요되므로.

2. 데이터 이동 연산이 많음: 힙정렬은 데이터의 이동 연산(요소의 교환)이 많이 필요할 수 있다. 다른 정렬 알고리즘들처럼 데이터의 비교만으로 정렬을 수행하는 것이 아니라, 데이터 이동도 수행해야 함.

3. 고정된 시간 복잡도: 비록 힙정렬의 시간 복잡도는 항상 O(n log n)이지만, 실제로는 퀵소트와 같은 다른 정렬 알고리즘보다 상수항이 큰 편.
   즉, 퀵소트보다는 일반적으로 느릴 수 있음.

불안정 정렬이다

불안정 정렬(Unstable Sort): 힙정렬은 값이 같은 원소의 순서를 보존하지 않는 불안정 정렬 알고리즘. 만약 정렬하려는 데이터에 동일한 값이 여러 개 있고 그 순서가 중요하지 않다면 불안정성은 오히려 장점으로 작용할 수 있다.

-> 힙정렬은 일정한 시간 복잡도와 제자리 정렬의 특성 때문에 특정 상황에서 유용할 수 있지만, 퀵소트와 같은 다른 정렬 알고리즘들과 비교하여 성능이나 구현의 용이성 면에서는 제한적일 수 있다.