[06. 정렬 알고리즘] 힙 정렬(Heap Sort)

공통

#include <iostream>
using namespace std;

#define swap2(type, x, y) do { type t = x; x = y; y = t; } while (false)

static void heapify(int arr[], int parent, const int last) {
    int temp = arr[parent];
    while (parent < (last + 1) / 2) {
        int lchild = parent * 2 + 1;
        int rchild = lchild + 1;
        int child = (lchild == last || arr[lchild] > arr[rchild]) ? lchild : rchild;
        if (temp >= arr[child])
            break;
        arr[parent] = arr[child];
        parent = child;
    }
    arr[parent] = temp;
}

void HeapSort1(int arr[], const int N) {
    if (N <= 1) return;
    
    const int last = N - 1;
    for (int parent = (last-1) / 2; parent >= 0; parent--)
        heapify(arr, parent, N - 1);
    swap2(int, arr[0], arr[N - 1]);
    
    for (int last = N - 2; last > 0; last--) {
        heapify(arr, 0, last);
        swap2(int, arr[0], arr[last]);
    }
}

#include <queue>

void HeapSort2(int arr[], const int N) {
    priority_queue q(arr, arr + N);
    for (int i = N - 1; i >= 0; i--) {
        arr[i] = q.top();
        q.pop();
    }
}

#include <random>

bool is_sorted(int arr[], const int N) {
    for (int i = 1; i < N; i++)
        if (arr[i - 1] > arr[i])
            return false;
    return true;
}

int main() {
    const int N = RAND_MAX;
    int arr[N];

    const int ntimes = 50;
    int total = 0;
    for (int j = 0; j < ntimes; j++) {
        for (int i = 0; i < N; ++i)
            arr[i] = rand();

        int start = clock();
        //HeapSort1(arr, N);			// 3~4 ms		(ntimes = 200)
        HeapSort2(arr, N);				// 45 ms		(ntimes = 50)
        total += clock() - start;
    }
    cout << total / ntimes << endl;
    cout << is_sorted(arr, N) << endl;
}