76 lines
2.1 KiB
C++
76 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 = 10000; // jumlah elemen
|
|
|
|
// Pilih kondisi: "avg", "best", atau "worst"
|
|
const string CASE = "worst";
|
|
// =============================================
|
|
|
|
void mergeHelp(vector<int>& a, int l, int mid, int r) {
|
|
int n1 = mid - l + 1, n2 = r - mid;
|
|
vector<int> L(n1), R(n2);
|
|
for (int i = 0; i < n1; i++) L[i] = a[l + i];
|
|
for (int j = 0; j < n2; j++) R[j] = a[mid + 1 + j];
|
|
int i = 0, j = 0, k = l;
|
|
while (i < n1 && j < n2) a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
|
|
while (i < n1) a[k++] = L[i++];
|
|
while (j < n2) a[k++] = R[j++];
|
|
}
|
|
|
|
void mergeRec(vector<int>& a, int l, int r) {
|
|
if (l < r) {
|
|
int m = l + (r - l) / 2;
|
|
mergeRec(a, l, m);
|
|
mergeRec(a, m + 1, r);
|
|
mergeHelp(a, l, m, r);
|
|
}
|
|
}
|
|
|
|
void mergeSort(vector<int>& a) {
|
|
mergeRec(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();
|
|
mergeSort(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;
|
|
} |