힙 정렬

선택 정렬이 이차 시간에 동작하는 이유는 매 단계마다 최솟값을 선형 탐색하기 때문입니다.

알고리즘의 실행 시간을 최적화하기 위해, 정렬되지 않은 원소 집합에서 최솟값을 빠르게 추출하는 연산을 지원하는 특별한 자료구조를 만들어 원본 배열 전체를 그 안에 넣은 다음, 최솟값을 하나씩 추출하여 새로운 정렬된 배열에 넣을 수 있습니다.

이것이 바로 이진 힙이 하는 일이며, 연산당 $O(\log n)$에 수행합니다. 이를 이용하면 $O(n \log n)$에 동작하는 알고리즘을 얻습니다.

void heapsort(int* a, int n) {
    // копируем массив в кучу
    t_n = n;
    copy(a, a + n, t + 1);
    build_heap();
    for (int i = 1; i <= n; i++) {
        // удаляем минимум, он останется в ячейке t[n + 1 - i]
        swap(t[1], t[n + 1 - i]);
        t_n--;
        sift_down(1);
    }
    // получили массив t[1..n], в котором все элементы упорядочены по убыванию
    reverse(t, t + n + 1);
    copy(t, t + n, a);
}

주목할 점은 “거의 정렬된” 배열의 경우 알고리즘을 조금 더 빠르게 만들 수 있다는 것입니다. 각 원소가 정렬된 배열에서의 자기 위치로부터 최대 $k$만큼 떨어져 있다는 것이 보장된다면, 크기가 $O(k)$인 힙을 유지하면서 배열을 $k$개 원소의 “창"으로 읽어 들이고, 다음 원소를 추가할 때마다 최솟값을 꺼내 기록하면 충분합니다. 이러한 알고리즘은 $O(n \log k)$의 시간에 동작합니다.