# Tugas Pendahuluan - Merge Sort & Quick Sort
### Pembuat Soal: AX
```txt
Nama : [your name here]
NPM : [your NPM here]
```
## Teori
### 1. Jelaskan secara singkat tiga langkah utama dari paradigma **Divide and Conquer**! (Divide, Conquer, Combine) (10 poin)
Divide : Ini adalah langkah pertama untuk memecahkan masalah besar menjadi beberapa sub masalah yang lebih kecil dan independen. sub masalah ini adalah versi yang lebih kecil dari masalah aslinya.
Conquer : Langkah kedua adalah menyelesaikan masing-masing sub-masalah secarara rekursif. Jika sub-masalah sudah sangat kecil (base case) solusinya dapat ditemukan dengan mudah.
Combine : Menggabungkan solusi dasri setiap sub masalah yang telah diselesaikan. Penggabungan ini menghasilkan solusi akhir untuk masalah besar yang awal.
### Referensi
- [1]GeeksforGeeks, “Divide and Conquer Algorithm,” GeeksforGeeks, Jan. 17, 2024 [Online]. Available: https://www.geeksforgeeks.org/dsa/divide-and-conquer/ [Diakses: 22-Sep-2025]
- [2]“Divide and Conquer Algorithm,” Programiz.com, 2020. [Online]. Available: https://www.programiz.com/dsa/divide-and-conquer [Diakses: 22-Sep-2025]
---
### 2. Di dalam algoritma Quick Sort, terdapat sebuah langkah krusial yang disebut **partisi**. Apa tujuan utama dari langkah partisi ini terhadap elemen **pivot**? (10 poin)
Tujuan utama dari langkah partisi adalah untuk rearrange elemen dalam sebuah arrag sehingga semua elemen yagn lebih kecil dari pivot akan berada di sisi kiri dan semua elemen yang lebih besar dari pivot berada di sisi kanan.
### Referensi
- [1]GeeksforGeeks, “Quick Sort,” GeeksforGeeks, Jan. 07, 2014. [Online]. Available: https://www.geeksforgeeks.org/dsa/quick-sort-algorithm/ [Diakses: 22-Sep-2025]
- [2]CodeLucky, “Quick Sort Algorithm: Efficient Partition-Based Sorting Explained with Examples - CodeLucky,” CodeLucky, Sep. 05, 2025. [Online]. Available: https://codelucky.com/quick-sort/ [Diakses: 22-Sep-2025]
---
### 3. Jelaskan perbedaan fundamental antara skema partisi **Lomuto** dan **Hoare** dalam hal: (15 poin)
### a. Gerakan pointer yang digunakan.
### b. Posisi akhir dari pivot setelah partisi selesai.
Lomuto :
- Gerakan pointer yang digunakan : Menggunakan satu pointer utama (biasanya i) yang akan berjalan dari kiri ke kanan dan satu pointer lagi untuk iterasi (biasanya j). Pointer i akan nandain batas elemen yang ≤ pivot. Setiap kali j nemu elemen ≤ pivot, i maju dan tuker posisi. Pivot biasanya ditaruh di ujung kanan terlebih dahulu.
- Posisi akhir dari pivot setelah partisi selesai : Setelah partisi selesai, elemen pivot akan berada di posisi akhirnya yang benar dalam array yang sudah diurutkan
Hoare :
- Gerakan pointer yang digunakan : Menggunakan dua pointer yagn satu mulai dari kiri dan satu dari kanan. Mereka akan saling mendekati dengan left dari elemen yang≥ pivot, lalu right mencari elemen yang ≤ pivot. Jika ketemu makan akan menukar dan terus sampai pointer saling melewati.
- Posisi akhir dari pivot setelah partisi selesai : Elemen pivot tidak dijamin berada di posisi akhirnya yang benar. Skema Hoare hanya memastikan bahwa semua elemen di sebelah kiri titik pertemuan pointer lebih kecil dari pivot dan semua elemen di sebelah kanan lebih besar.
### Referensi
- [1]“4. Lomuto Quick Sort i... | Digilab UI,” Digilabdte.com, 2025. [Online]. Available: https://learn.digilabdte.com/books/algorithm-programming/page/4-lomuto-quick-sort-in-c. [Diakses: 22-Sep-2025]
- [2]“5. Hoare Quick Sort in... | Digilab UI,” Digilabdte.com, 2025. [Online]. Available: https://learn.digilabdte.com/books/algorithm-programming/page/5-hoare-quick-sort-in-c. [Diakses: 22-Sep-2025]
- [3]GeeksforGeeks, “Hoare’s vs Lomuto partition scheme in QuickSort,” GeeksforGeeks, Feb. 06, 2017. [Online]. Available: https://www.geeksforgeeks.org/dsa/hoares-vs-lomuto-partition-scheme-quicksort/. [Diakses: 22-Sep-2025]
---
### 4. Bandingkan **Merge Sort** dan **Quick Sort**. Manakah yang disebut algoritma ***in-place*** dan manakah yang merupakan algoritma ***stable***? Jelaskan alasannya secara singkat! (10 poin)
Quick Sort : Algoritma in-place karena algoritma ini mengurutkan elemen di dalam array yang sama tanpa memerlukan memori tambahan yang siginifikan, hanya memiliki kompleksitas O(log n).
Merge Sort : Algoritma Stable karena selama proses penggubungan jika ada dua elemen dengan nilai yagn sama, elemen dari sub-array pertama akan selalu ditempatkan di depan elemen dari sub-array kedua, relatif stabil.
### Referensi
- [1]“3. Understanding Quick... | Digilab UI,” Digilabdte.com, 2025. [Online]. Available: https://learn.digilabdte.com/books/algorithm-programming/page/3-understanding-quick-sort. [Diakses: 22-Sep-2025]
- [2]GeeksforGeeks, “Quick Sort vs Merge Sort,” GeeksforGeeks, Sep. 28, 2018. [Online]. Available: https://www.geeksforgeeks.org/dsa/quick-sort-vs-merge-sort/. [Diakses: 22-Sep-2025]
---
### 5. Performa Quick Sort bisa menurun drastis menjadi $O(n^2)$. Jelaskan sebuah contoh kondisi data dan strategi pemilihan pivot yang dapat menyebabkan skenario *worst-case* ini (Jelaskan untuk masing - masing Hoare dan Lomuto)! (15 poin)
Performa Quick Sort akan menurun drastis menjadi $O(n^2)$ ketika pemilihan pivot secara konsisten menghasilkan partisi yang sangat tidak seimbang. Paling sering terjadi pada array yang sudah terurut.
Skenario worst case dengan Lomuto Partition :
Misal ada suatu array ([1,2,3,4,5]), lomuto akan memilih elemen terakhir, yaitu 5, sebagai pivot. Setelah partisi, elemen 5 akan tetap di posisinya, tetapi sub-array di kirinya ([1,2,3,4]) memiliki n−1 elemen, sementara sub-array di kanannya kosong. Menyebabkan partisi yang sangat tidak seimbang dan berulang di setiap pemanggilan rekursif.
Skenario worst case dengan Lomuto Partition :
Misal ada array yang sama ([1,2,3,4,5]), jika hoare memilih elemen pertama, yaitu 1 sebagai pivot. Maka pointer kiri dan kanan aakan bergerakn melintasi array, karena semua elemen lain lebih besar dari pivot dan tidak ada pertukaran yang terjadi.
### Referensi
- [1]“4. Lomuto Quick Sort i... | Digilab UI,” Digilabdte.com, 2025. [Online]. Available: https://learn.digilabdte.com/books/algorithm-programming/page/4-lomuto-quick-sort-in-c. [Diakses: 22-Sep-2025]
- [2]“5. Hoare Quick Sort in... | Digilab UI,” Digilabdte.com, 2025. [Online]. Available: https://learn.digilabdte.com/books/algorithm-programming/page/5-hoare-quick-sort-in-c. [Diakses: 22-Sep-2025]
- [3]GeeksforGeeks, “Hoare’s vs Lomuto partition scheme in QuickSort,” GeeksforGeeks, Feb. 06, 2017. [Online]. Available: https://www.geeksforgeeks.org/dsa/hoares-vs-lomuto-partition-scheme-quicksort/. [Diakses: 22-Sep-2025]
## Programming
### 1. Implementasi & Analisis Performa Tiga Algoritma Sorting (40 poin)
Implementasikan **Merge Sort**, **Quick Sort (Lomuto)**, dan **Quick Sort (Hoare)** pada TODO (Praktikan) yang telah ditentukan. Ukur performa ketiganya pada dua skenario data yang berbeda untuk menunjukkan keunggulan dan kelemahan masing-masing. Jawaban teori dan analisis dituliskan secara terpisah dari file `.cpp` ini.
**Ketentuan:**
* **JANGAN SENTUH ATAUPUN MENGUBAH FUNCTION main, readDataFromFile, DAN writeDataToFile. PELAJARI SAJA BAGAIMANA PARAMETER FUNCTION MASING - MASING ALGORITMA SORTING DIKIRIMKAN UNTUK MENGISI FUNCTIONNYA**
* Download kedua file berikut dan taruh pada directory yang sama dengan file .cppnya :
* Sorted Data : https://drive.google.com/file/d/18WBgL2CTX4RQoTmnheUoD4GjPaza0l45/view?usp=sharing
* Random Data : https://drive.google.com/file/d/1dZDkqJ9IA6cCkIqgK4Ipg0qdo7uG_hIj/view?usp=sharing
* **Merge Sort**: Gunakan implementasi konseptual yang membuat salinan `vector` baru.
* **Quick Sort (Lomuto)**: Gunakan pivot elemen **terakhir** (`A[high]`).
* **Quick Sort (Hoare)**: Gunakan pivot elemen **pertama** (`A[low]`).
* Kalo bingung sbnrnya udh ada step by stepnya di comment (TODO Praktikan) codenya tinggal diikutin aja.
* Klo masih bingung lg jangan lupa baca daste di learn.digilabdte.com
* **Analisis**: Setelah menampilkan semua hasil waktu, berikan **analisis singkat** yang menjelaskan hasil performa pada kedua skenario tersebut.
> Lengkapi skeleton code di bawah ini!
---
```cpp
#include <iostream>
#include <vector>
#include <fstream> // Library untuk file input/output
#include <string>
#include <chrono>
#include <algorithm>
#include <cstdlib>
#include <ctime>
// --- FUNGSI HELPER UNTUK FILE HANDLING (Tidak Perlu Diubah) ---
// Fungsi untuk membaca data dari file ke vector.
std::vector<int> readDataFromFile(const std::string& fileName) {
std::vector<int> data;
std::ifstream inFile(fileName);
int number;
if (!inFile.is_open()) {
std::cerr << "Error: Gagal membuka file " << fileName << ". Pastikan file tersebut ada." << std::endl;
return data;
}
while (inFile >> number) {
data.push_back(number);
}
inFile.close();
return data;
}
// Fungsi untuk menulis data vector ke sebuah file.
void writeDataToFile(const std::string& fileName, const std::vector<int>& data) {
std::ofstream outFile(fileName);
if (!outFile.is_open()) {
std::cerr << "Error: Gagal membuat file output " << fileName << std::endl;
return;
}
for (int number : data) {
outFile << number << std::endl;
}
outFile.close();
}
// --- IMPLEMENTASI MERGE SORT ---
void merge(std::vector<int>& arr, int left, int mid, int right) {
// TODO (Praktikan): Implementasikan logika merge di sini.
// 1. Tentukan ukuran dan buat vector sementara L (dari left ke mid) dan R (dari mid+1 ke right).
// 2. Salin data dari arr ke vector sementara L dan R.
// 3. Lakukan proses penggabungan (merge) dari L dan R kembali ke arr.
// 4. Salin sisa elemen dari L atau R jika ada.
}
void mergeSort(std::vector<int>& arr, int left, int right) {
// TODO (Praktikan): Implementasikan logika merge sort di sini.
// 1. Base case: jika left >= right, return (array dengan 0 atau 1 elemen sudah terurut)
// 2. Tentukan titik tengah (mid)
// 3. Panggil mergeSort secara rekursif untuk paruh kiri
// 4. Panggil mergeSort secara rekursif untuk paruh kanan
// 5. Panggil fungsi merge untuk menggabungkan kedua paruh
}
// --- IMPLEMENTASI QUICK SORT (LOMUTO) ---
int partitionLomuto(std::vector<int>& arr, int low, int high) {
// TODO (Praktikan): Implementasikan partisi Lomuto di sini.
// 1. Pilih pivot (elemen terakhir)
// 2. Inisialisasi index i (penanda "wall")
// 3. Lakukan iterasi dari low hingga high-1 (dengan pointer j)
// - Jika arr[j] < pivot, geser wall (i++) dan lakukan swap antara arr[i] dan arr[j]
// 4. Setelah loop, tukar pivot (arr[high]) dengan elemen di posisi i+1
// 5. Return posisi pivot yang baru (i+1)
}
void quickSortLomuto(std::vector<int>& arr, int low, int high) {
// TODO (Praktikan): Implementasikan quickSort menggunakan partisi Lomuto.
// 1. Base case: jika low < high
// 2. Panggil partisi Lomuto untuk mendapatkan pivot index (pi)
// 3. Panggil quickSortLomuto secara rekursif untuk sub-array sebelum dan sesudah pivot
}
// --- IMPLEMENTASI QUICK SORT (HOARE) ---
int partitionHoare(std::vector<int>& arr, int low, int high) {
// TODO (Praktikan): Implementasikan partisi Hoare di sini.
// 1. Pilih pivot (elemen pertama)
// 2. Inisialisasi pointer i (dari kiri) dan j (dari kanan)
// 3. Buat sebuah loop tak terbatas (while true):
// - Geser i ke kanan hingga menemukan elemen >= pivot
// - Geser j ke kiri hingga menemukan elemen <= pivot
// - Jika i >= j, keluar dari loop dan Return j
// - Jika tidak, tukar arr[i] dengan arr[j]
}
void quickSortHoare(std::vector<int>& arr, int low, int high) {
// TODO (Praktikan): Implementasikan quickSort menggunakan partisi Hoare.
// 1. Base case: jika low < high
// 2. Panggil partisi Hoare untuk mendapatkan split point (pi)
// 3. Panggil quickSortHoare secara rekursif. Perhatikan batasnya:
// - Panggilan pertama dari low hingga pi
// - Panggilan kedua dari pi+1 hingga high
}
// MAIN FILE JANGAN DIUBAH, PELAJARI SAJA PARAMETER YANG DIKIRIMKAN
int main() {
// Definisi nama file
const std::string RANDOM_FILE = "random_data.txt";
const std::string SORTED_FILE = "sorted_data.txt";
const std::string TIME_OUTPUT_FILE = "hasil_waktu_sorting.txt";
std::ofstream timeOutputFile(TIME_OUTPUT_FILE);
// ================================================================
// Skenario 1: Average Case (Data Acak dari File)
// ================================================================
timeOutputFile << "========================================" << std::endl;
timeOutputFile << "SKENARIO 1: AVERAGE CASE (DATA ACAK)" << std::endl;
timeOutputFile << "========================================" << std::endl;
std::cout << "Membaca data acak dari " << RANDOM_FILE << "..." << std::endl;
// Membaca data dari file
std::vector<int> randomData = readDataFromFile(RANDOM_FILE);
if (!randomData.empty()) {
std::vector<int> dataForMergeSort_rand = randomData;
std::vector<int> dataForLomuto_rand = randomData;
std::vector<int> dataForHoare_rand = randomData;
//===========================================================
// --- Proses & Ukur Waktu Merge Sort (Random) ---
//===========================================================
auto start_ms_rand = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
mergeSort(dataForMergeSort_rand, 0, dataForMergeSort_rand.size() - 1); // Memanggil mergeSort
auto end_ms_rand = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_ms_rand = end_ms_rand - start_ms_rand; // Menghitung durasi dalam milidetik
timeOutputFile << "Merge Sort (Random): " << elapsed_ms_rand.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_random_mergesort.txt", dataForMergeSort_rand); // Menyimpan hasil array yang sudah terurut ke file
//===========================================================
// --- Proses & Ukur Waktu Quick Sort Lomuto (Random) ---
//===========================================================
auto start_qs_lomuto_rand = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
quickSortLomuto(dataForLomuto_rand, 0, dataForLomuto_rand.size() - 1); // Memanggil quickSortLomuto
auto end_qs_lomuto_rand = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_qs_lomuto_rand = end_qs_lomuto_rand - start_qs_lomuto_rand; // Menghitung durasi dalam milidetik
timeOutputFile << "Quick Sort Lomuto (Random): " << elapsed_qs_lomuto_rand.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_random_lomuto.txt", dataForLomuto_rand); // Menyimpan hasil array yang sudah terurut ke file
//===========================================================
// --- Proses & Ukur Waktu Quick Sort Hoare (Random) ---
//===========================================================
auto start_qs_hoare_rand = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
quickSortHoare(dataForHoare_rand, 0, dataForHoare_rand.size() - 1); // Memanggil quickSortHoare
auto end_qs_hoare_rand = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_qs_hoare_rand = end_qs_hoare_rand - start_qs_hoare_rand; // Menghitung durasi dalam milidetik
timeOutputFile << "Quick Sort Hoare (Random): " << elapsed_qs_hoare_rand.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_random_hoare.txt", dataForHoare_rand); // Menyimpan hasil array yang sudah terurut ke file
}
timeOutputFile << std::endl;
// ================================================================
// Skenario 2: Worst Case (Data Terurut dari File)
// ================================================================
timeOutputFile << "========================================" << std::endl;
timeOutputFile << "SKENARIO 2: WORST CASE (DATA TERURUT)" << std::endl;
timeOutputFile << "========================================" << std::endl;
std::cout << "Membaca data terurut dari " << SORTED_FILE << "..." << std::endl;
// Membaca data dari file
std::vector<int> sortedData = readDataFromFile(SORTED_FILE);
if (!sortedData.empty()) {
std::vector<int> dataForMergeSort_sorted = sortedData;
std::vector<int> dataForLomuto_sorted = sortedData;
std::vector<int> dataForHoare_sorted = sortedData;
//===========================================================
// --- Proses & Ukur Waktu Merge Sort (Sorted) ---
//===========================================================
auto start_ms_sorted = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
mergeSort(dataForMergeSort_sorted, 0, dataForMergeSort_sorted.size() - 1); // Memanggil mergeSort
auto end_ms_sorted = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_ms_sorted = end_ms_sorted - start_ms_sorted; // Menghitung durasi dalam milidetik
timeOutputFile << "Merge Sort (Sorted): " << elapsed_ms_sorted.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_terurut_mergesort.txt", dataForMergeSort_sorted); // Menyimpan hasil array yang sudah terurut ke file
//===========================================================
// --- Proses & Ukur Waktu Quick Sort Lomuto (Sorted) ---
//===========================================================
auto start_qs_lomuto_sorted = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
quickSortLomuto(dataForLomuto_sorted, 0, dataForLomuto_sorted.size() - 1); // Memanggil quickSortLomuto
auto end_qs_lomuto_sorted = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_qs_lomuto_sorted = end_qs_lomuto_sorted - start_qs_lomuto_sorted; // Menghitung durasi dalam milidetik
timeOutputFile << "Quick Sort Lomuto (Sorted): " << elapsed_qs_lomuto_sorted.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_terurut_lomuto.txt", dataForLomuto_sorted); // Menyimpan hasil array yang sudah terurut ke file
//===========================================================
// --- Proses & Ukur Waktu Quick Sort Hoare (Sorted) ---
//===========================================================
auto start_qs_hoare_sorted = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
quickSortHoare(dataForHoare_sorted, 0, dataForHoare_sorted.size() - 1); // Memanggil quickSortHoare
auto end_qs_hoare_sorted = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_qs_hoare_sorted = end_qs_hoare_sorted - start_qs_hoare_sorted; // Menghitung durasi dalam milidetik
timeOutputFile << "Quick Sort Hoare (Sorted): " << elapsed_qs_hoare_sorted.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_terurut_hoare.txt", dataForHoare_sorted); // Menyimpan hasil array yang sudah terurut ke file
}
timeOutputFile.close();
std::cout << "Pengukuran selesai. Hasil waktu disimpan di " << TIME_OUTPUT_FILE << std::endl;
std::cout << "Hasil array yang terurut disimpan di file .txt terpisah." << std::endl;
return 0;
}
```
## Jawaban
### Code :
```cpp
#include <iostream>
#include <vector>
#include <fstream> // Library untuk file input/output
#include <string>
#include <chrono>
#include <algorithm>
#include <cstdlib>
#include <ctime>
// --- FUNGSI HELPER UNTUK FILE HANDLING (Tidak Perlu Diubah) ---
// Fungsi untuk membaca data dari file ke vector.
std::vector<int> readDataFromFile(const std::string& fileName) {
std::vector<int> data;
std::ifstream inFile(fileName);
int number;
if (!inFile.is_open()) {
std::cerr << "Error: Gagal membuka file " << fileName << ". Pastikan file tersebut ada." << std::endl;
return data;
}
while (inFile >> number) {
data.push_back(number);
}
inFile.close();
return data;
}
// Fungsi untuk menulis data vector ke sebuah file.
void writeDataToFile(const std::string& fileName, const std::vector<int>& data) {
std::ofstream outFile(fileName);
if (!outFile.is_open()) {
std::cerr << "Error: Gagal membuat file output " << fileName << std::endl;
return;
}
for (int number : data) {
outFile << number << std::endl;
}
outFile.close();
}
// --- IMPLEMENTASI MERGE SORT ---
void merge(std::vector<int>& arr, int left, int mid, int right) {
// TODO (Praktikan): Implementasikan logika merge di sini.
// 1. Tentukan ukuran dan buat vector sementara L (dari left ke mid) dan R (dari mid+1 ke right).
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> L(n1), R(n2);
// 2. Salin data dari arr ke vector sementara L dan R.
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 3. Lakukan proses penggabungan (merge) dari L dan R kembali ke arr.
int i = 0;
int j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 4. Salin sisa elemen dari L atau R jika ada.
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(std::vector<int>& arr, int left, int right) {
// TODO (Praktikan): Implementasikan logika merge sort di sini.
// 1. Base case: jika left >= right, return (array dengan 0 atau 1 elemen sudah terurut)
if (left >= right) {
return;
}
// 2. Tentukan titik tengah (mid)
int mid = left + (right - left) / 2;
// 3. Panggil mergeSort secara rekursif untuk paruh kiri
mergeSort(arr, left, mid);
// 4. Panggil mergeSort secara rekursif untuk paruh kanan
mergeSort(arr, mid + 1, right);
// 5. Panggil fungsi merge untuk menggabungkan kedua paruh
merge(arr, left, mid, right);
}
// --- IMPLEMENTASI QUICK SORT (LOMUTO) ---
int partitionLomuto(std::vector<int>& arr, int low, int high) {
// TODO (Praktikan): Implementasikan partisi Lomuto di sini.
// 1. Pilih pivot (elemen terakhir)
int pivot = arr[high];
// 2. Inisialisasi index i (penanda "wall")
int i = (low - 1);
// 3. Lakukan iterasi dari low hingga high-1 (dengan pointer j)
for (int j = low; j <= high - 1; j++) {
// - Jika arr[j] < pivot, geser wall (i++) dan lakukan swap antara arr[i] dan arr[j]
if (arr[j] < pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
// 4. Setelah loop, tukar pivot (arr[high]) dengan elemen di posisi i+1
std::swap(arr[i + 1], arr[high]);
// 5. Return posisi pivot yang baru (i+1)
return (i + 1);
}
void quickSortLomuto(std::vector<int>& arr, int low, int high) {
// TODO (Praktikan): Implementasikan quickSort menggunakan partisi Lomuto.
// 1. Base case: jika low < high
if (low < high) {
// 2. Panggil partisi Lomuto untuk mendapatkan pivot index (pi)
int pi = partitionLomuto(arr, low, high);
// 3. Panggil quickSortLomuto secara rekursif untuk sub-array sebelum dan sesudah pivot
quickSortLomuto(arr, low, pi - 1);
quickSortLomuto(arr, pi + 1, high);
}
}
// --- IMPLEMENTASI QUICK SORT (HOARE) ---
int partitionHoare(std::vector<int>& arr, int low, int high) {
// TODO (Praktikan): Implementasikan partisi Hoare di sini.
// 1. Pilih pivot (elemen pertama)
int pivot = arr[low];
// 2. Inisialisasi pointer i (dari kiri) dan j (dari kanan)
int i = low - 1;
int j = high + 1;
// 3. Buat sebuah loop tak terbatas (while true):
while (true) {
// - Geser i ke kanan hingga menemukan elemen >= pivot
do {
i++;
} while (arr[i] < pivot);
// - Geser j ke kiri hingga menemukan elemen <= pivot
do {
j--;
} while (arr[j] > pivot);
// - Jika i >= j, keluar dari loop dan Return j
if (i >= j) {
return j;
}
// - Jika tidak, tukar arr[i] dengan arr[j]
std::swap(arr[i], arr[j]);
}
}
void quickSortHoare(std::vector<int>& arr, int low, int high) {
// TODO (Praktikan): Implementasikan quickSort menggunakan partisi Hoare.
// 1. Base case: jika low < high
if (low < high) {
// 2. Panggil partisi Hoare untuk mendapatkan split point (pi)
int pi = partitionHoare(arr, low, high);
// 3. Panggil quickSortHoare secara rekursif. Perhatikan batasnya:
// - Panggilan pertama dari low hingga pi
quickSortHoare(arr, low, pi);
// - Panggilan kedua dari pi+1 hingga high
quickSortHoare(arr, pi + 1, high);
}
}
// MAIN FILE JANGAN DIUBAH, PELAJARI SAJA PARAMETER YANG DIKIRIMKAN
int main() {
// Definisi nama file
const std::string RANDOM_FILE = "random_data.txt";
const std::string SORTED_FILE = "sorted_data.txt";
const std::string TIME_OUTPUT_FILE = "hasil_waktu_sorting.txt";
std::ofstream timeOutputFile(TIME_OUTPUT_FILE);
// ================================================================
// Skenario 1: Average Case (Data Acak dari File)
// ================================================================
timeOutputFile << "========================================" << std::endl;
timeOutputFile << "SKENARIO 1: AVERAGE CASE (DATA ACAK)" << std::endl;
timeOutputFile << "========================================" << std::endl;
std::cout << "Membaca data acak dari " << RANDOM_FILE << "..." << std::endl;
// Membaca data dari file
std::vector<int> randomData = readDataFromFile(RANDOM_FILE);
if (!randomData.empty()) {
std::vector<int> dataForMergeSort_rand = randomData;
std::vector<int> dataForLomuto_rand = randomData;
std::vector<int> dataForHoare_rand = randomData;
//===========================================================
// --- Proses & Ukur Waktu Merge Sort (Random) ---
//===========================================================
auto start_ms_rand = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
mergeSort(dataForMergeSort_rand, 0, dataForMergeSort_rand.size() - 1); // Memanggil mergeSort
auto end_ms_rand = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_ms_rand = end_ms_rand - start_ms_rand; // Menghitung durasi dalam milidetik
timeOutputFile << "Merge Sort (Random): " << elapsed_ms_rand.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_random_mergesort.txt", dataForMergeSort_rand); // Menyimpan hasil array yang sudah terurut ke file
//===========================================================
// --- Proses & Ukur Waktu Quick Sort Lomuto (Random) ---
//===========================================================
auto start_qs_lomuto_rand = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
quickSortLomuto(dataForLomuto_rand, 0, dataForLomuto_rand.size() - 1); // Memanggil quickSortLomuto
auto end_qs_lomuto_rand = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_qs_lomuto_rand = end_qs_lomuto_rand - start_qs_lomuto_rand; // Menghitung durasi dalam milidetik
timeOutputFile << "Quick Sort Lomuto (Random): " << elapsed_qs_lomuto_rand.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_random_lomuto.txt", dataForLomuto_rand); // Menyimpan hasil array yang sudah terurut ke file
//===========================================================
// --- Proses & Ukur Waktu Quick Sort Hoare (Random) ---
//===========================================================
auto start_qs_hoare_rand = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
quickSortHoare(dataForHoare_rand, 0, dataForHoare_rand.size() - 1); // Memanggil quickSortHoare
auto end_qs_hoare_rand = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_qs_hoare_rand = end_qs_hoare_rand - start_qs_hoare_rand; // Menghitung durasi dalam milidetik
timeOutputFile << "Quick Sort Hoare (Random): " << elapsed_qs_hoare_rand.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_random_hoare.txt", dataForHoare_rand); // Menyimpan hasil array yang sudah terurut ke file
}
timeOutputFile << std::endl;
// ================================================================
// Skenario 2: Worst Case (Data Terurut dari File)
// ================================================================
timeOutputFile << "========================================" << std::endl;
timeOutputFile << "SKENARIO 2: WORST CASE (DATA TERURUT)" << std::endl;
timeOutputFile << "========================================" << std::endl;
std::cout << "Membaca data terurut dari " << SORTED_FILE << "..." << std::endl;
// Membaca data dari file
std::vector<int> sortedData = readDataFromFile(SORTED_FILE);
if (!sortedData.empty()) {
std::vector<int> dataForMergeSort_sorted = sortedData;
std::vector<int> dataForLomuto_sorted = sortedData;
std::vector<int> dataForHoare_sorted = sortedData;
//===========================================================
// --- Proses & Ukur Waktu Merge Sort (Sorted) ---
//===========================================================
auto start_ms_sorted = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
mergeSort(dataForMergeSort_sorted, 0, dataForMergeSort_sorted.size() - 1); // Memanggil mergeSort
auto end_ms_sorted = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_ms_sorted = end_ms_sorted - start_ms_sorted; // Menghitung durasi dalam milidetik
timeOutputFile << "Merge Sort (Sorted): " << elapsed_ms_sorted.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_terurut_mergesort.txt", dataForMergeSort_sorted); // Menyimpan hasil array yang sudah terurut ke file
//===========================================================
// --- Proses & Ukur Waktu Quick Sort Lomuto (Sorted) ---
//===========================================================
auto start_qs_lomuto_sorted = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
quickSortLomuto(dataForLomuto_sorted, 0, dataForLomuto_sorted.size() - 1); // Memanggil quickSortLomuto
auto end_qs_lomuto_sorted = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_qs_lomuto_sorted = end_qs_lomuto_sorted - start_qs_lomuto_sorted; // Menghitung durasi dalam milidetik
timeOutputFile << "Quick Sort Lomuto (Sorted): " << elapsed_qs_lomuto_sorted.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_terurut_lomuto.txt", dataForLomuto_sorted); // Menyimpan hasil array yang sudah terurut ke file
//===========================================================
// --- Proses & Ukur Waktu Quick Sort Hoare (Sorted) ---
//===========================================================
auto start_qs_hoare_sorted = std::chrono::high_resolution_clock::now(); // Memulai pengukuran waktu
quickSortHoare(dataForHoare_sorted, 0, dataForHoare_sorted.size() - 1); // Memanggil quickSortHoare
auto end_qs_hoare_sorted = std::chrono::high_resolution_clock::now(); // Menghentikan pengukuran waktu
std::chrono::duration<double, std::milli> elapsed_qs_hoare_sorted = end_qs_hoare_sorted - start_qs_hoare_sorted; // Menghitung durasi dalam milidetik
timeOutputFile << "Quick Sort Hoare (Sorted): " << elapsed_qs_hoare_sorted.count() << " ms" << std::endl; // Menulis hasil waktu ke file
writeDataToFile("sorted_terurut_hoare.txt", dataForHoare_sorted); // Menyimpan hasil array yang sudah terurut ke file
}
timeOutputFile.close();
std::cout << "Pengukuran selesai. Hasil waktu disimpan di " << TIME_OUTPUT_FILE << std::endl;
std::cout << "Hasil array yang terurut disimpan di file .txt terpisah." << std::endl;
return 0;
}
```
### Screenshot Output masing - masing algoritma pada tabel yang disediakan :
Kriteria screesnhot :
* Setelah code di run seharusnya akan ada 7 file baru :
* sorted_random_hoare : Output random data random QuickSort hoare
* sorted_random_lomuto : Output random data random QuickSort lomuto
* sorted_random_mergesort : Output random data random MergeSort
* sorted_terurut_hoare : Output sorted data random QuickSort hoare
* sorted_terurut_lomuto : Output sorted data random QuickSort lomuto
* sorted_terurut_mergesort : Output sorted data random MergeSort
* hasil_waktu_sorting : perbandingan waktu sorting masing - masing
* Pastikan saat screenshot nama file terlihat !
* Screesnhot semuanya sesuai dengan cara di bawah :
* Screenshot Atas (bagian paling atas output) :
* Screenshot Bawah (bagian paling bawah output) :
* hasil_waktu_sorting di screenshot keseluruhan isinya saja
------------------------------------------------------
* Output Random Data :
|Algoritma| Screenshot Atas | Screenshot Bawah |
|---------|--------|--------|
| `sorted_random_mergesort` |  | |
| `sorted_random_lomuto` |||
| `sorted_random_hoare` ||  |
* Output Sorted Data :
|Algoritma| Screenshot Atas | Screenshot Bawah |
|---------|--------|--------|
| `sorted_terurut_mergesort`|| |
| `sorted_terurut_lomuto` |||
| `sorted_terurut_hoare` | ||
* Hasil Waktu Sorting (Untuk ini screenshot untuk 2x percobaan jadi run codenya 2 kali dan screesnhot outputnya kedua percobaan tersebut):
* Screenshot Percobaan 1 :
* Screenshot Percobaan 2 :
### Analisis :
Tujuan utama program ini adalah untuk mendemostrasikan bagaiaman kompleksitas waktu dari algoritma sorting dapat bervariasi tergantung pada kondisi data dan algoritma yang digunakan. program ini menguji dua skenario data :
- avarage case dengan data acak
- worst case dengan data yang sudah terurut
Kode ini terbagi menjadi beberapa seperti fila handling untuk mewrite dan meread data dari file teks dan menyimpan hasil pengurutan ke fila baru. Implementasi juga menggunakan merge sort, quick sort lomuto, quick sort hoare yang berfungsi untuk mengurutkan data. Lalu ada main function yang menjalankan semua fungsi tersebut.
Pada skenario avarage case :
- merge sort membutuhkan waktu eksekusi sekitar 21-22 ms dengan waktu stabil. Performa Merge Sort tidak terlalu terpengaruh oleh urutan data awal karena selalu membagi masalah menjadi dua bagian yang sama besar.
- quick sort menunjukkan performa yang sangat cepat, sekitar 7-8 ms. Ini sesuai dengan teori bahwa pada kasus rata-rata, Quick Sort memiliki kompleksitas O(nlogn) dan sering lebih cepat dari Merge Sort karena tidak memerlukan memori tambahan dan memiliki overhead yang lebih rendah.
Pada skenario worst case :
- merge sort performanya tetap sangat baik dan stabil, sesuai dengan kompleksitas waktu O(nlogn)-nya yang tidak terpengaruh oleh urutan data.
- quick sort lomuto waktu eksekusinya melonjak tajam dari 8 ms menjadi 67-68 ms. Karena skema Lomuto memilih pivot terakhir, pada array yang sudah terurut, pivot selalu menjadi elemen terbesar. Ini menghasilkan partisi yang tidak seimbang, sehingga kompleksitasnya berubah menjadi O(n 2 ).
- Quick sort hoare waktu eksekusinya juga meningkat menjadi 12-13 ms, tetapi peningkatannya tidak sedrastis Lomuto. Ini menunjukkan bahwa skema Hoare lebih tangguh menghadapi kasus terburuk (array terurut) dibandingkan Lomuto
# Random Question (0 poin)
### 1. Berikan first impression anda ke aslab AX, kritik, dan saran
[your answer here]
# Hint untuk CS (tergantung nanti gua moodnya gmn cm harusnya ini bakal ngebantu)
pelajari cara mengukur waktu running suatu function seperti yang ada di TP ini.
Sign in with Wallet
Connect another wallet