70 lines
2.1 KiB
C++
70 lines
2.1 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
#include <random>
|
|
#include <algorithm>
|
|
#include <chrono>
|
|
using namespace std;
|
|
|
|
// =============================================
|
|
// KONFIGURASI — ubah nilai di sini
|
|
// =============================================
|
|
const int DATA_SIZE = 1000000; // jumlah elemen
|
|
|
|
// Pilih kondisi: "avg", "best", atau "worst"
|
|
const string CASE = "worst";
|
|
// =============================================
|
|
|
|
int qpartition(vector<int>& a, int lo, int hi) {
|
|
int mid = lo + (hi-lo)/2;
|
|
if (a[lo] > a[mid]) swap(a[lo], a[mid]);
|
|
if (a[lo] > a[hi]) swap(a[lo], a[hi]);
|
|
if (a[mid] > a[hi]) swap(a[mid], a[hi]);
|
|
swap(a[mid], a[hi-1]);
|
|
int pivot = a[hi-1], i = lo-1;
|
|
for (int j = lo; j < hi-1; j++) if (a[j] <= pivot) swap(a[++i], a[j]);
|
|
swap(a[i+1], a[hi-1]);
|
|
return i+1;
|
|
}
|
|
|
|
void quickRec(vector<int>& a, int lo, int hi) {
|
|
if (lo < hi) { int p = qpartition(a,lo,hi); quickRec(a,lo,p-1); quickRec(a,p+1,hi); }
|
|
}
|
|
|
|
void quickSort(vector<int>& a) { if (a.size() > 1) quickRec(a, 0, (int)a.size()-1); }
|
|
|
|
vector<int> generateData(int n, const string& caseType) {
|
|
vector<int> data(n);
|
|
|
|
if (caseType == "best") {
|
|
// Best case: sudah terurut ascending
|
|
for (int i = 0; i < n; i++) data[i] = i + 1;
|
|
|
|
} else if (caseType == "worst") {
|
|
// Worst case: urutan terbalik (descending)
|
|
for (int i = 0; i < n; i++) data[i] = n - i;
|
|
|
|
} else {
|
|
// Average case: acak (random shuffle)
|
|
for (int i = 0; i < n; i++) data[i] = i + 1;
|
|
mt19937 rng(42);
|
|
shuffle(data.begin(), data.end(), rng);
|
|
}
|
|
|
|
return data;
|
|
}
|
|
|
|
int main() {
|
|
vector<int> data = generateData(DATA_SIZE, CASE);
|
|
|
|
auto start = chrono::high_resolution_clock::now();
|
|
quickSort(data);
|
|
auto end = chrono::high_resolution_clock::now();
|
|
|
|
double ms = chrono::duration<double, milli>(end - start).count();
|
|
|
|
cout << "Case : " << CASE << endl;
|
|
cout << "Size : " << DATA_SIZE << endl;
|
|
cout << "Waktu : " << ms << " ms" << endl;
|
|
|
|
return 0;
|
|
} |