62 lines
1.7 KiB
C++
62 lines
1.7 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 = "best";
|
|
// =============================================
|
|
|
|
void bubbleSort(vector<int>& a) {
|
|
int n = a.size();
|
|
for (int i = 0; i < n - 1; i++) {
|
|
bool swapped = false;
|
|
for (int j = 0; j < n - i - 1; j++)
|
|
if (a[j] > a[j+1]) { swap(a[j], a[j+1]); swapped = true; }
|
|
if (!swapped) break;
|
|
}
|
|
}
|
|
|
|
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();
|
|
bubbleSort(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;
|
|
} |