Untitled
unknown
c_cpp
2 years ago
3.5 kB
3
Indexable
#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; }
Editor is loading...