힙 정렬

힙 정렬은 힙을 사용해 배열을 낮은 순서에서 높은 순서로 정렬하는 알고리즘이다.

힙은 부분적으로 정렬된 이진 트리로, 배열 안에 저장된다. 힙 정렬 알고리즘은 힙의 구조를 활용해 빠르게 정렬을 수행한다.

낮은 순서에서 높은 순서로 정렬하기 위해, 힙 정렬은 먼저 정렬되지 않은 배열을 최대 힙으로 변환한다. 이렇게 하면 배열의 첫 번째 요소가 가장 큰 값이 된다.

예를 들어 정렬할 배열이 다음과 같다고 하자:

[ 5, 13, 2, 25, 7, 17, 20, 8, 4 ]

이 배열은 먼저 다음과 같은 최대 힙으로 변환된다:

힙의 내부 배열은 다음과 같다:

[ 25, 13, 20, 8, 7, 17, 2, 5, 4 ]

이 상태는 아직 정렬되었다고 할 수 없다! 하지만 이제 정렬 과정이 시작된다: 첫 번째 요소(인덱스 0)와 마지막 요소(인덱스 n-1)를 교환한다. 그 결과는 다음과 같다:

[ 4, 13, 20, 8, 7, 17, 2, 5, 25 ]
  *                          *

이제 새로운 루트 노드인 4는 자식 노드보다 작으므로, shift down 또는 "heapify" 과정을 통해 n-2 요소까지 최대 힙을 복구한다. 힙을 복구한 후, 새로운 루트는 배열에서 두 번째로 큰 값이 된다:

[20, 13, 17, 8, 7, 4, 2, 5 | 25]

중요: 힙을 복구할 때 인덱스 n-1의 마지막 요소는 무시한다. 이 요소는 이미 배열의 최대값을 포함하고 있으므로, 정렬된 위치에 있다. | 표시는 배열의 정렬된 부분이 시작되는 위치를 나타낸다. 이제부터는 배열의 이 부분을 건드리지 않는다.

다시 첫 번째 요소와 마지막 요소(이번에는 인덱스 n-2)를 교환한다:

[5, 13, 17, 8, 7, 4, 2, 20 | 25]
 *                      *

그리고 힙을 다시 유효한 최대 힙으로 복구한다:

[17, 13, 5, 8, 7, 4, 2 | 20, 25]

보는 바와 같이, 가장 큰 값들이 점점 뒤로 이동한다. 이 과정을 루트 노드에 도달할 때까지 반복하면 전체 배열이 정렬된다.

참고: 이 과정은 선택 정렬과 매우 유사하다. 선택 정렬은 배열의 나머지 부분에서 최소값을 반복적으로 찾는다. 최소값 또는 최대값을 추출하는 것은 힙이 잘하는 작업이다.

힙 정렬의 성능은 최선, 최악, 평균 모두 **O(n log n)**이다. 배열을 직접 수정하기 때문에 힙 정렬은 제자리에서 수행할 수 있다. 하지만 안정적인 정렬은 아니다: 동일한 요소들의 상대적 순서가 보존되지 않는다.

다음은 Swift에서 힙 정렬을 구현한 예제이다:

extension Heap {
  public mutating func sort() -> [T] {
    for i in stride(from: (elements.count - 1), through: 1, by: -1) {
      swap(&elements[0], &elements[i])
      shiftDown(0, heapSize: i)
    }
    return elements
  }
}

이 코드는 힙 구현에 sort() 함수를 추가한다. 이 함수를 사용하려면 다음과 같이 작성한다:

var h1 = Heap(array: [5, 13, 2, 25, 7, 17, 20, 8, 4], sort: >)
let a1 = h1.sort()

낮은 순서에서 높은 순서로 정렬하려면 최대 힙이 필요하므로, Heap에 정렬 함수의 역순을 전달해야 한다. <로 정렬하려면 Heap 객체를 > 정렬 함수로 생성해야 한다. 즉, 낮은 순서에서 높은 순서로 정렬하면 최대 힙이 생성되고, 이를 최소 힙으로 변환한다.

이를 위해 편리한 헬퍼 함수를 작성할 수 있다:

public func heapsort<T>(_ a: [T], _ sort: @escaping (T, T) -> Bool) -> [T] {
  let reverseOrder = { i1, i2 in sort(i2, i1) }
  var h = Heap(array: a, sort: reverseOrder)
  return h.sort()
}

Swift Algorithm Club의 Matthijs Hollemans가 작성함