C++ 삽입 정렬과 퀵 정렬 학습

// quicksort.cpp
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <cassert>

// --------- 유틸리티: insertion sort (작은 구간 최적화) ----------
template<typename T>
void insertion_sort(std::vector<T>& a, int l, int r) {
    for (int i = l + 1; i <= r; ++i) {
        T key = std::move(a[i]);
        int j = i - 1;
        while (j >= l && a[j] > key) {
            a[j + 1] = std::move(a[j]);
            --j;
        }
        a[j + 1] = std::move(key);
    }
}

// --------- 유틸리티: median-of-three pivot index ----------
template<typename T>
int median_of_three(const std::vector<T>& a, int l, int r) {
    int m = l + ((r - l) >> 1);
    // return index of median among a[l], a[m], a[r]
    if (a[l] < a[m]) {
        if (a[m] < a[r]) return m;
        return (a[l] < a[r]) ? r : l;
    }
    else {
        if (a[l] < a[r]) return l;
        return (a[m] < a[r]) ? r : m;
    }
}

// --------- Hoare partition 기반 퀵소트 (중복과 성능 균형) ----------
template<typename T>
void quicksort_hoare_impl(std::vector<T>& a, int l, int r) {
    const int INSERTION_SORT_THRESHOLD = 16;
    // use an explicit loop for tail recursion elimination
    while (l < r) {
        if (r - l + 1 <= INSERTION_SORT_THRESHOLD) {
            insertion_sort(a, l, r);
            return;
        }

        // pivot: median-of-three
        int midIndex = median_of_three(a, l, r);
        T pivot = a[midIndex];

        int i = l - 1;
        int j = r + 1;
        while (true) {
            do { ++i; } while (a[i] < pivot);
            do { --j; } while (a[j] > pivot);
            if (i >= j) break;
            std::swap(a[i], a[j]);
        }
        int p = j; // partition point: [l..p] <= pivot, [p+1..r] >= pivot

        // Recurse on smaller part first to bound recursion depth (stack O(log n))
        if (p - l < r - (p + 1)) {
            quicksort_hoare_impl(a, l, p);
            l = p + 1; // tail recursion elimination for right part
        }
        else {
            quicksort_hoare_impl(a, p + 1, r);
            r = p; // continue loop on left part
        }
    }
}

template<typename T>
void quicksort_hoare(std::vector<T>& a) {
    if (a.empty()) return;
    quicksort_hoare_impl(a, 0, static_cast<int>(a.size()) - 1);
}

// --------- 3-way 퀵소트 (동일키가 많은 경우 강력) ----------
template<typename T>
std::mt19937& rng_instance() {
    static thread_local std::mt19937 gen((unsigned)std::chrono::high_resolution_clock::now().time_since_epoch().count());
    return gen;
}

template<typename T>
void quicksort_3way_impl(std::vector<T>& a, int l, int r) {
    if (l >= r) return;
    const int INSERTION_SORT_THRESHOLD = 16;
    if (r - l + 1 <= INSERTION_SORT_THRESHOLD) {
        insertion_sort(a, l, r);
        return;
    }

    std::uniform_int_distribution<int> dist(l, r);
    int pivIdx = dist(rng_instance<T>());
    T pivot = a[pivIdx];

    int lt = l;      // a[l..lt-1] < pivot
    int i = l;      // a[lt..i-1] == pivot
    int gt = r;      // a[gt+1..r] > pivot

    while (i <= gt) {
        if (a[i] < pivot) {
            std::swap(a[lt++], a[i++]);
        }
        else if (a[i] > pivot) {
            std::swap(a[i], a[gt--]);
        }
        else {
            ++i;
        }
    }

    quicksort_3way_impl(a, l, lt - 1);
    quicksort_3way_impl(a, gt + 1, r);
}

template<typename T>
void quicksort_3way(std::vector<T>& a) {
    if (a.empty()) return;
    quicksort_3way_impl(a, 0, static_cast<int>(a.size()) - 1);
}

// --------- 테스트 헬퍼 ----------
template<typename T>
bool is_sorted_vec(const std::vector<T>& a) {
    for (size_t i = 1; i < a.size(); ++i) if (a[i - 1] > a[i]) return false;
    return true;
}

int main() {
    // 간단한 테스트: 랜덤 정수, 중복 있는 경우, 정렬 확인
    std::mt19937 gen((unsigned)std::chrono::high_resolution_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<int> dist(0, 100); // 중복 많이 있음

    const int N = 20000;
    std::vector<int> a;
    a.reserve(N);
    for (int i = 0; i < N; ++i) a.push_back(dist(gen));

    auto b = a; // 복사본

    // Hoare quicksort <-인덱스 두개 를 양 끝에서 좁혀가면서
    auto t1 = std::chrono::high_resolution_clock::now();
    quicksort_hoare(a);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::cout << "Hoare quicksort sorted: " << std::boolalpha << is_sorted_vec(a)
        << ", time(ms): " << std::chrono::duration<double, std::milli>(t2 - t1).count() << "\n";

    // 3-way quicksort <- 동일 키가 많으면 효율적
    auto t3 = std::chrono::high_resolution_clock::now();
    quicksort_3way(b);
    auto t4 = std::chrono::high_resolution_clock::now();
    std::cout << "3-way quicksort sorted: " << std::boolalpha << is_sorted_vec(b)
        << ", time(ms): " << std::chrono::duration<double, std::milli>(t4 - t3).count() << "\n";

    // 비교: std::sort (introsort)
    auto c = a; // a already sorted; regenerate from original
    c = a; // just to have variable
    // re-generate c from original vector for fair compare:
    c = std::vector<int>(); c.reserve(N);
    gen.seed((unsigned)std::chrono::high_resolution_clock::now().time_since_epoch().count());
    for (int i = 0; i < N; ++i) c.push_back(dist(gen));

    auto t5 = std::chrono::high_resolution_clock::now();
    std::sort(c.begin(), c.end());
    auto t6 = std::chrono::high_resolution_clock::now();
    std::cout << "std::sort sorted: " << std::boolalpha << is_sorted_vec(c)
        << ", time(ms): " << std::chrono::duration<double, std::milli>(t6 - t5).count() << "\n";

    return 0;
}