[06. 정렬 알고리즘] 도수 정렬

#include <iostream>

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;
}

void counting(int arr[], const int N, const int Min, const int Max) {
    int* freq = new int[Max - Min + 1] {0};
    int* sorted = new int[N];

    for (int i = 0; i < N; i++)         freq[arr[i] - Min]++;
    for (int i = 0; i < Max - Min; i++) freq[i + 1] += freq[i];
    for (int i = 0; i < N; i++)         sorted[--freq[arr[i] - Min]] = arr[i];
    memcpy(arr, sorted, sizeof(*arr) * N);

    delete[] freq;
    delete[] sorted;
}

void counting(int arr[], const int N, const int Max) {
    counting(arr, N, 0, Max);
}

#include <random>
#include <chrono>
using namespace std;
using namespace std::chrono;

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

    const int ntimes = 200;
    long long total = 0;
    for (int j = 0; j < ntimes; j++) {
        for (int i = 0; i < N; ++i)
            arr[i] = rand();
        
        auto start = steady_clock::now();
        counting(arr, N, N);				// 427㎲
        auto duration = duration_cast<microseconds>(steady_clock::now() - start);
        total += duration.count();
    }
    cout << total / ntimes << "㎲\n";
    cout << is_sorted(arr, N) << endl;
}