417 lines
15 KiB
C++
417 lines
15 KiB
C++
/**
|
|
* ============================================================
|
|
* ANALISIS KOMPLEKSITAS WAKTU - ALGORITMA PENGURUTAN
|
|
* ============================================================
|
|
* Algoritma : Bubble Sort, Selection Sort, Merge Sort, Quick Sort
|
|
* Kasus : Best Case, Worst Case, Average Case
|
|
* Kompilasi : g++ -O0 -std=c++11 -o sort_benchmark sort_benchmark.cpp
|
|
* ============================================================
|
|
*/
|
|
|
|
#include <iostream>
|
|
#include <vector>
|
|
#include <algorithm>
|
|
#include <chrono>
|
|
#include <random>
|
|
#include <iomanip>
|
|
#include <string>
|
|
#include <sstream>
|
|
#include <map>
|
|
|
|
using namespace std;
|
|
using namespace std::chrono;
|
|
|
|
// ============================================================
|
|
// KONFIGURASI
|
|
// ============================================================
|
|
|
|
const int SIZES[] = { 10000, 20000, 100000, 200000, 1000000, 2000000 };
|
|
const int SIZES_COUNT = 6;
|
|
|
|
const bool RUN_BUBBLE = true;
|
|
const bool RUN_SELECTION = true;
|
|
const bool RUN_MERGE = true;
|
|
const bool RUN_QUICK = true;
|
|
|
|
const bool RUN_BEST = true; // sudah terurut naik
|
|
const bool RUN_WORST = true; // terurut terbalik
|
|
const bool RUN_AVERAGE = true; // acak
|
|
|
|
// Seed random (0 = acak setiap run)
|
|
const unsigned int RANDOM_SEED = 42;
|
|
|
|
// O(n^2) di-skip jika N melebihi ini
|
|
const int O2_LIMIT = 200000;
|
|
|
|
// Lebar bar chart
|
|
const int BAR_WIDTH = 40;
|
|
|
|
// Batas total waktu program (menit). Set 0 untuk nonaktifkan.
|
|
const double OVERTIME_MINUTES = 30.0;
|
|
|
|
// ============================================================
|
|
// SENTINEL
|
|
// -1 = skipped (N > O2_LIMIT)
|
|
// -2 = overtime
|
|
// ============================================================
|
|
const double VAL_SKIP = -1.0;
|
|
const double VAL_OT = -2.0;
|
|
|
|
// ============================================================
|
|
// GENERATOR
|
|
// ============================================================
|
|
|
|
vector<int> genBest(int n) {
|
|
vector<int> d(n);
|
|
for (int i = 0; i < n; i++) d[i] = i + 1;
|
|
return d;
|
|
}
|
|
|
|
vector<int> genWorst(int n) {
|
|
vector<int> d(n);
|
|
for (int i = 0; i < n; i++) d[i] = n - i;
|
|
return d;
|
|
}
|
|
|
|
vector<int> genAverage(int n) {
|
|
vector<int> d(n);
|
|
for (int i = 0; i < n; i++) d[i] = i + 1;
|
|
mt19937 rng(RANDOM_SEED == 0 ? (unsigned int)random_device{}() : RANDOM_SEED);
|
|
shuffle(d.begin(), d.end(), rng);
|
|
return d;
|
|
}
|
|
|
|
// ============================================================
|
|
// ALGORITMA
|
|
// ============================================================
|
|
|
|
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;
|
|
}
|
|
}
|
|
|
|
void selectionSort(vector<int>& a) {
|
|
int n = a.size();
|
|
for (int i = 0; i < n - 1; i++) {
|
|
int m = i;
|
|
for (int j = i + 1; j < n; j++) if (a[j] < a[m]) m = j;
|
|
if (m != i) swap(a[i], a[m]);
|
|
}
|
|
}
|
|
|
|
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); }
|
|
|
|
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); }
|
|
|
|
// ============================================================
|
|
// TIMER
|
|
// ============================================================
|
|
|
|
typedef time_point<high_resolution_clock> TimePoint;
|
|
|
|
double measure(void (*fn)(vector<int>&), vector<int> data) {
|
|
TimePoint s = high_resolution_clock::now();
|
|
fn(data);
|
|
TimePoint e = high_resolution_clock::now();
|
|
return duration<double, milli>(e - s).count();
|
|
}
|
|
|
|
double elapsed(const TimePoint& start) {
|
|
return duration<double, milli>(high_resolution_clock::now() - start).count();
|
|
}
|
|
|
|
bool overtime(const TimePoint& start) {
|
|
return OVERTIME_MINUTES > 0 && elapsed(start) >= OVERTIME_MINUTES * 60000.0;
|
|
}
|
|
|
|
// ============================================================
|
|
// FORMAT
|
|
// ============================================================
|
|
|
|
string fmtN(int n) {
|
|
if (n >= 1000000) return to_string(n/1000000) + ".000.000";
|
|
if (n >= 1000) return to_string(n/1000) + ".000";
|
|
return to_string(n);
|
|
}
|
|
|
|
string fmtT(double ms) {
|
|
if (ms == VAL_OT) return " OVERTIME";
|
|
if (ms == VAL_SKIP) return " SKIPPED";
|
|
ostringstream o; o << fixed << setprecision(2) << ms << " ms";
|
|
return o.str();
|
|
}
|
|
|
|
string makeBar(double ms, double maxVal) {
|
|
if (ms == VAL_SKIP) {
|
|
return string(BAR_WIDTH, ' ') + " (skipped)";
|
|
}
|
|
if (ms == VAL_OT) {
|
|
string b;
|
|
for (int i = 0; i < BAR_WIDTH; i++) b += "\xe2\x96\x91"; // ░
|
|
return b + " OVERTIME";
|
|
}
|
|
int fill = (maxVal > 0) ? (int)((ms / maxVal) * BAR_WIDTH) : 0;
|
|
if (fill == 0 && ms > 0) fill = 1;
|
|
string b;
|
|
for (int i = 0; i < fill; i++) b += "\xe2\x96\x88"; // █
|
|
for (int i = fill; i < BAR_WIDTH; i++) b += " ";
|
|
return b;
|
|
}
|
|
|
|
void sep2(int w=72) { cout << string(w,'=') << "\n"; }
|
|
void sep1(int w=72) { cout << string(w,'-') << "\n"; }
|
|
|
|
// ============================================================
|
|
// STRUKTUR HASIL
|
|
// ============================================================
|
|
|
|
struct Result {
|
|
double best, worst, avg;
|
|
Result() : best(VAL_SKIP), worst(VAL_SKIP), avg(VAL_SKIP) {}
|
|
};
|
|
|
|
// ============================================================
|
|
// CHART PER KASUS
|
|
// ============================================================
|
|
|
|
struct AlgoEntry {
|
|
string name;
|
|
bool enabled;
|
|
void (*fn)(vector<int>&);
|
|
};
|
|
|
|
void printChart(
|
|
const string& label,
|
|
const vector<AlgoEntry>& algos,
|
|
const map<string, map<int,Result> >& res,
|
|
int caseIdx // 0=best 1=worst 2=avg
|
|
) {
|
|
// Cari max (nilai nyata saja)
|
|
double maxVal = 0;
|
|
for (int a = 0; a < (int)algos.size(); a++) {
|
|
if (!algos[a].enabled) continue;
|
|
for (int i = 0; i < SIZES_COUNT; i++) {
|
|
const Result& r = res.at(algos[a].name).at(SIZES[i]);
|
|
double v = (caseIdx==0)?r.best:(caseIdx==1)?r.worst:r.avg;
|
|
if (v > 0 && v > maxVal) maxVal = v;
|
|
}
|
|
}
|
|
|
|
cout << "\n"; sep2();
|
|
cout << " " << label << "\n"; sep2();
|
|
|
|
for (int a = 0; a < (int)algos.size(); a++) {
|
|
if (!algos[a].enabled) continue;
|
|
cout << "\n " << algos[a].name << "\n"; sep1();
|
|
for (int i = 0; i < SIZES_COUNT; i++) {
|
|
const Result& r = res.at(algos[a].name).at(SIZES[i]);
|
|
double v = (caseIdx==0)?r.best:(caseIdx==1)?r.worst:r.avg;
|
|
cout << " " << setw(10) << left << fmtN(SIZES[i])
|
|
<< " | " << makeBar(v, maxVal) << "\n";
|
|
}
|
|
cout << "\n";
|
|
}
|
|
}
|
|
|
|
// ============================================================
|
|
// TABEL RINGKASAN
|
|
// ============================================================
|
|
|
|
void printTable(
|
|
const vector<AlgoEntry>& algos,
|
|
const map<string, map<int,Result> >& res
|
|
) {
|
|
cout << "\n"; sep2();
|
|
cout << " TABEL RINGKASAN WAKTU (ms)\n"; sep2();
|
|
cout << left
|
|
<< setw(14) << "Algoritma"
|
|
<< setw(12) << "N"
|
|
<< setw(18) << "Best Case"
|
|
<< setw(18) << "Worst Case"
|
|
<< setw(18) << "Avg Case"
|
|
<< "\n";
|
|
sep1();
|
|
for (int a = 0; a < (int)algos.size(); a++) {
|
|
if (!algos[a].enabled) continue;
|
|
bool first = true;
|
|
for (int i = 0; i < SIZES_COUNT; i++) {
|
|
const Result& r = res.at(algos[a].name).at(SIZES[i]);
|
|
cout << left
|
|
<< setw(14) << (first ? algos[a].name : "")
|
|
<< setw(12) << fmtN(SIZES[i])
|
|
<< setw(18) << fmtT(r.best)
|
|
<< setw(18) << fmtT(r.worst)
|
|
<< setw(18) << fmtT(r.avg)
|
|
<< "\n";
|
|
first = false;
|
|
}
|
|
sep1();
|
|
}
|
|
}
|
|
|
|
// ============================================================
|
|
// MAIN
|
|
// ============================================================
|
|
|
|
int main() {
|
|
vector<AlgoEntry> algos;
|
|
AlgoEntry e;
|
|
|
|
e.name="BubbleSort"; e.enabled=RUN_BUBBLE; e.fn=bubbleSort; algos.push_back(e);
|
|
e.name="SelectSort"; e.enabled=RUN_SELECTION; e.fn=selectionSort; algos.push_back(e);
|
|
e.name="MergeSort"; e.enabled=RUN_MERGE; e.fn=mergeSort; algos.push_back(e);
|
|
e.name="QuickSort"; e.enabled=RUN_QUICK; e.fn=quickSort; algos.push_back(e);
|
|
|
|
// Inisialisasi hasil
|
|
map<string, map<int,Result> > results;
|
|
for (int a = 0; a < (int)algos.size(); a++)
|
|
for (int i = 0; i < SIZES_COUNT; i++)
|
|
results[algos[a].name][SIZES[i]] = Result();
|
|
|
|
// ── Phase 1: Benchmark ─────────────────────────────────────
|
|
TimePoint prog_start = high_resolution_clock::now();
|
|
bool ot = false;
|
|
|
|
cout << "\n"; sep2();
|
|
cout << " BENCHMARK SEDANG BERJALAN...\n";
|
|
if (OVERTIME_MINUTES > 0)
|
|
cout << " Batas waktu : " << OVERTIME_MINUTES << " menit\n";
|
|
sep2(); cout << "\n";
|
|
|
|
for (int a = 0; a < (int)algos.size(); a++) {
|
|
if (!algos[a].enabled) continue;
|
|
const string& name = algos[a].name;
|
|
|
|
for (int i = 0; i < SIZES_COUNT; i++) {
|
|
int n = SIZES[i];
|
|
bool sizeSkip = (name=="BubbleSort"||name=="SelectSort") && n > O2_LIMIT;
|
|
Result r;
|
|
|
|
if (sizeSkip) {
|
|
cout << " [--] " << setw(12) << name
|
|
<< " N=" << setw(10) << fmtN(n)
|
|
<< " | skipped (N > " << fmtN(O2_LIMIT) << ")\n";
|
|
cout.flush();
|
|
results[name][n] = r;
|
|
continue;
|
|
}
|
|
|
|
// Best
|
|
if (RUN_BEST) {
|
|
if (ot) {
|
|
r.best = VAL_OT;
|
|
cout << " [!!] " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Best = OVERTIME\n";
|
|
} else {
|
|
r.best = measure(algos[a].fn, genBest(n));
|
|
cout << " [OK] " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Best = " << fmtT(r.best) << "\n";
|
|
if (overtime(prog_start)) {
|
|
ot = true;
|
|
cout << "\n [!!] OVERTIME — " << fixed << setprecision(1)
|
|
<< elapsed(prog_start)/60000.0 << " menit"
|
|
<< " (batas: " << OVERTIME_MINUTES << " menit)\n"
|
|
<< " [!!] Sisa run ditandai OVERTIME.\n\n";
|
|
}
|
|
}
|
|
}
|
|
|
|
// Worst
|
|
if (RUN_WORST) {
|
|
if (ot) {
|
|
r.worst = VAL_OT;
|
|
cout << " [!!] " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Worst = OVERTIME\n";
|
|
} else {
|
|
r.worst = measure(algos[a].fn, genWorst(n));
|
|
cout << " [OK] " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Worst = " << fmtT(r.worst) << "\n";
|
|
if (overtime(prog_start)) {
|
|
ot = true;
|
|
cout << "\n [!!] OVERTIME — " << fixed << setprecision(1)
|
|
<< elapsed(prog_start)/60000.0 << " menit"
|
|
<< " (batas: " << OVERTIME_MINUTES << " menit)\n"
|
|
<< " [!!] Sisa run ditandai OVERTIME.\n\n";
|
|
}
|
|
}
|
|
}
|
|
|
|
// Average
|
|
if (RUN_AVERAGE) {
|
|
if (ot) {
|
|
r.avg = VAL_OT;
|
|
cout << " [!!] " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Average = OVERTIME\n";
|
|
} else {
|
|
r.avg = measure(algos[a].fn, genAverage(n));
|
|
cout << " [OK] " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Average = " << fmtT(r.avg) << "\n";
|
|
if (overtime(prog_start)) {
|
|
ot = true;
|
|
cout << "\n [!!] OVERTIME — " << fixed << setprecision(1)
|
|
<< elapsed(prog_start)/60000.0 << " menit"
|
|
<< " (batas: " << OVERTIME_MINUTES << " menit)\n"
|
|
<< " [!!] Sisa run ditandai OVERTIME.\n\n";
|
|
}
|
|
}
|
|
}
|
|
|
|
results[name][n] = r;
|
|
cout.flush();
|
|
}
|
|
cout << "\n";
|
|
}
|
|
|
|
// ── Phase 2: Chart per kasus ───────────────────────────────
|
|
if (RUN_BEST) printChart("BEST CASE (array sudah terurut naik)", algos, results, 0);
|
|
if (RUN_WORST) printChart("WORST CASE (array terurut terbalik)", algos, results, 1);
|
|
if (RUN_AVERAGE) printChart("AVERAGE CASE (array acak / random)", algos, results, 2);
|
|
|
|
// ── Phase 3: Tabel ─────────────────────────────────────────
|
|
printTable(algos, results);
|
|
|
|
// ── Footer ─────────────────────────────────────────────────
|
|
double total = elapsed(prog_start);
|
|
cout << "\n"; sep2();
|
|
if (ot) cout << " [!!] BENCHMARK DIHENTIKAN KARENA OVERTIME\n";
|
|
cout << " Total waktu : " << fixed << setprecision(2)
|
|
<< total/1000.0 << " detik (" << total/60000.0 << " menit)\n";
|
|
cout << " Bar : \xe2\x96\x88 = normal \xe2\x96\x91 = OVERTIME (skipped) = N > batas\n";
|
|
sep2(); cout << "\n";
|
|
|
|
return 0;
|
|
} |