Untitled

#include <iostream>
#include <vector>
#include <algorithm>

// Fungsi untuk mencari pivot menggunakan algoritma median-of-three
template<typename T>
T MedianOfThree(T a, T b, T c) {
    if (a < b) {
        if (b < c)
            return b;
        else if (a < c)
            return c;
        else
            return a;
    } else {
        if (a < c)
            return a;
        else if (b < c)
            return c;
        else
            return b;
    }
}

// Fungsi untuk melakukan pengurutan dengan algoritma Quick Sort
template<typename T>
void QuickSort(std::vector<T>& arr, int left, int right) {
    if (left < right) {
        // Mencari pivot menggunakan Median of Three
        T pivot = MedianOfThree(arr[left], arr[(left + right) / 2], arr[right]);

        // Partisi array
        int i = left;
        int j = right;
        while (i <= j) {
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;
            if (i <= j) {
                std::swap(arr[i], arr[j]);
                i++;
                j--;
            }
        }

        // Rekursif melakukan Quick Sort pada dua bagian yang dihasilkan
        if (left < j)
            QuickSort(arr, left, j);
        if (i < right)
            QuickSort(arr, i, right);
    }
}

// Fungsi untuk melakukan pengurutan dengan algoritma Heap Sort
template<typename T>
void HeapSort(std::vector<T>& arr) {
    std::make_heap(arr.begin(), arr.end());
    std::sort_heap(arr.begin(), arr.end());
}

// Fungsi untuk melakukan pengurutan dengan algoritma Insertion Sort
template<typename T>
void InsertionSort(std::vector<T>& arr, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        T key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Fungsi Intro Sort
template<typename T>
void IntroSort(std::vector<T>& arr) {
    int n = arr.size();
    int depthLimit = 2 * log2(n);

    // Fungsi rekursif Intro Sort
    auto IntroSortRecursive = [&](auto&& self, int left, int right, int depth) -> void {
        if (right - left + 1 <= 16) {
            InsertionSort(arr, left, right);
        } else if (depth == 0) {
            HeapSort(arr);
        } else {
            QuickSort(arr, left, right);
            depth--;

            int pivotIndex = right - 1;
            T pivot = arr[pivotIndex];
            int i = left;
            int j = right - 1;
            while (i <= j) {
                while (arr[i] < pivot)
                    i++;
                while (arr[j] > pivot)
                    j--;
                if (i <= j) {
                    std::swap(arr[i], arr[j]);
                    i++;
                    j--;
                }
            }

            std::swap(arr[i], arr[pivotIndex]);
            IntroSortRecursive(self, left, i - 1, depth);
            IntroSortRecursive(self, i + 1, right, depth);
        }
    };

    IntroSortRecursive(IntroSortRecursive, 0, n - 1, depthLimit);
}

int main() {
    std::vector<int> arr = {9, 3, 7, 1, 5, 10, 2, 8, 4, 6};

    std::cout << "Array sebelum diurutkan: ";
    for (int num : arr)
        std::cout << num << " ";
    std::cout << std::endl;

    IntroSort(arr);

    std::cout << "Array setelah diurutkan: ";
    for (int num : arr)
        std::cout << num << " ";
    std::cout << std::endl;

    return 0;
}