Mata Kuliah: Struktur Data dan Algoritma
Pertemuan: 10
Topik: Algoritma Sorting Lanjut (Merge Sort dan Quick Sort)
Waktu: 150 menit
Sifat: Open Book
Pilih jawaban yang paling tepat untuk setiap soal berikut.
1. Apa kompleksitas waktu worst case dari algoritma Merge Sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
e) O(n² log n)
2. Apa kompleksitas waktu worst case dari algoritma Quick Sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
e) O(2ⁿ)
3. Manakah pernyataan yang BENAR tentang Merge Sort?
a) Merge Sort adalah algoritma in-place
b) Merge Sort memiliki kompleksitas ruang O(1)
c) Merge Sort adalah algoritma stable
d) Merge Sort lebih cepat dari Quick Sort dalam semua kasus
e) Merge Sort menggunakan strategi greedy
4. Paradigma yang digunakan oleh Merge Sort dan Quick Sort adalah:
a) Greedy
b) Dynamic Programming
c) Divide and Conquer
d) Brute Force
e) Backtracking
5. Pada algoritma Quick Sort, apa yang dimaksud dengan “pivot”?
a) Elemen pertama dalam array
b) Elemen yang digunakan sebagai pembanding untuk partisi
c) Elemen terbesar dalam array
d) Elemen tengah hasil sorting
e) Elemen yang selalu dihapus
6. Perhatikan array berikut: [8, 3, 5, 1, 9, 2]. Jika menggunakan Merge Sort, berapa kali proses merge dilakukan hingga array terurut?
a) 3 kali
b) 4 kali
c) 5 kali
d) 6 kali
e) 7 kali
7. Apa kompleksitas ruang (space complexity) dari Merge Sort standar?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
e) O(n²)
8. Manakah strategi pemilihan pivot yang dapat meminimalkan kemungkinan worst case pada Quick Sort?
a) Selalu pilih elemen pertama
b) Selalu pilih elemen terakhir
c) Median-of-three
d) Selalu pilih elemen terbesar
e) Selalu pilih elemen terkecil
9. Apa yang terjadi jika Quick Sort selalu memilih pivot yang merupakan elemen terkecil atau terbesar?
a) Algoritma berjalan optimal O(n log n)
b) Algoritma menjadi O(n²)
c) Algoritma menjadi O(n)
d) Algoritma tidak dapat berjalan
e) Tidak ada pengaruh
10. Dalam proses partisi Lomuto pada Quick Sort dengan array [5, 2, 8, 1, 9] dan pivot = 5 (elemen pertama), posisi akhir pivot setelah partisi adalah:
a) Index 0
b) Index 1
c) Index 2
d) Index 3
e) Index 4
11. Manakah pernyataan yang BENAR tentang lower bound sorting berbasis perbandingan?
a) Lower bound adalah O(n)
b) Lower bound adalah Ω(n log n)
c) Lower bound adalah O(n²)
d) Tidak ada lower bound untuk sorting
e) Lower bound tergantung pada algoritma
12. Mengapa Merge Sort lebih cocok untuk sorting linked list dibandingkan Quick Sort?
a) Merge Sort lebih cepat
b) Merge memerlukan akses sekuensial yang cocok dengan linked list
c) Quick Sort tidak bisa digunakan untuk linked list
d) Merge Sort menggunakan lebih sedikit memori
e) Tidak ada perbedaan
13. Perhatikan rekurensi berikut: T(n) = 2T(n/2) + O(n). Solusi dari rekurensi ini adalah:
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
e) O(2ⁿ)
14. Jika array sudah hampir terurut, algoritma mana yang cenderung memiliki performa TERBAIK?
a) Merge Sort
b) Quick Sort dengan pivot elemen pertama
c) Quick Sort dengan random pivot
d) Selection Sort
e) Bubble Sort dengan early termination
15. Apa keuntungan utama Quick Sort dibandingkan Merge Sort?
a) Selalu lebih cepat
b) In-place (tidak memerlukan memori tambahan O(n))
c) Lebih mudah diimplementasikan
d) Selalu stable
e) Worst case lebih baik
16. Dalam algoritma Merge Sort, operasi “conquer” merujuk pada:
a) Membagi array menjadi dua bagian
b) Menggabungkan dua array terurut
c) Melakukan rekursi pada subarray
d) Memilih pivot
e) Menukar elemen
17. Perhatikan array [4, 1, 3, 2, 5]. Setelah satu kali partisi dengan pivot = 3 (elemen tengah) menggunakan skema Hoare, manakah konfigurasi yang MUNGKIN?
a) [1, 2, 3, 4, 5]
b) [2, 1, 3, 4, 5]
c) [4, 1, 3, 2, 5]
d) [5, 4, 3, 2, 1]
e) [1, 2, 3, 5, 4]
18. Algoritma hybrid yang menggabungkan Quick Sort, Heap Sort, dan Insertion Sort adalah:
a) Timsort
b) Introsort
c) Smoothsort
d) Shellsort
e) Radix Sort
19. Berapa jumlah perbandingan minimum yang diperlukan untuk mengurutkan n elemen menggunakan comparison-based sorting?
a) n
b) n log n
c) ⌈log₂(n!)⌉
d) n²
e) 2ⁿ
20. Manakah yang BUKAN merupakan langkah dalam paradigma Divide and Conquer?
a) Divide: membagi masalah menjadi submasalah
b) Conquer: menyelesaikan submasalah secara rekursif
c) Combine: menggabungkan solusi submasalah
d) Optimize: mengoptimalkan solusi dengan dynamic programming
e) Base case: menyelesaikan masalah trivial secara langsung
Jelaskan tiga langkah utama dalam paradigma Divide and Conquer! Berikan contoh penerapannya pada Merge Sort!
Perhatikan array berikut: [38, 27, 43, 3, 9, 82, 10]
Tunjukkan proses Merge Sort langkah demi langkah hingga array terurut! Gambarkan pohon rekursi yang terbentuk!
Jelaskan mengapa Merge Sort disebut sebagai algoritma “stable”! Berikan contoh kasus di mana sifat stable ini penting!
Tuliskan pseudocode untuk fungsi merge(arr, left, mid, right) yang menggabungkan dua subarray terurut!
Perhatikan array berikut: [5, 2, 8, 1, 9, 3]
Lakukan partisi menggunakan skema Lomuto dengan pivot = elemen terakhir (3). Tunjukkan langkah-langkahnya!
Bandingkan tiga strategi pemilihan pivot pada Quick Sort: (1) elemen pertama, (2) elemen terakhir, (3) median-of-three. Jelaskan kelebihan dan kekurangan masing-masing!
Selesaikan rekurensi berikut menggunakan metode substitusi atau Master Theorem:
Tunjukkan langkah-langkah penyelesaiannya!
Jelaskan mengapa lower bound untuk comparison-based sorting adalah Ω(n log n)! Gunakan konsep decision tree dalam penjelasan Anda!
Implementasikan fungsi Quick Sort dalam C++ dengan strategi pivot median-of-three!
Perhatikan array berikut: [10, 80, 30, 90, 40, 50, 70]
Lakukan Quick Sort lengkap dengan pivot = elemen terakhir. Tunjukkan kondisi array setelah setiap partisi!
Jelaskan konsep “introsort” dan mengapa algoritma ini digunakan sebagai implementasi std::sort di C++!
Analisis kompleksitas waktu Quick Sort untuk kasus:
a) Best case
b) Average case
c) Worst case
Jelaskan kondisi input yang menyebabkan masing-masing kasus!
Implementasikan Merge Sort untuk linked list dalam C++! Jelaskan mengapa pendekatan ini berbeda dari Merge Sort untuk array!
Diberikan array dengan 1.000.000 elemen. Bandingkan perkiraan jumlah operasi yang diperlukan oleh: a) Bubble Sort (O(n²)) b) Merge Sort (O(n log n)) c) Quick Sort average case (O(n log n))
Hitung rasio perbandingannya!
Desain algoritma hybrid yang menggunakan Merge Sort untuk data besar dan Insertion Sort untuk subarray kecil (threshold = 16). Jelaskan mengapa pendekatan ini lebih efisien!
Latar Belakang: Sistem radar pertahanan udara mendeteksi multiple objek yang perlu diurutkan berdasarkan tingkat ancaman. Setiap objek memiliki atribut: ID, jarak (km), kecepatan (km/jam), altitude (m), dan threat score (0-100).
Kriteria pengurutan multi-level:
Data Target:
ID | Jarak | Kecepatan | Altitude | Threat Score
------|-------|-----------|----------|-------------
T-101 | 45 | 800 | 5000 | 85
T-102 | 30 | 600 | 3000 | 90
T-103 | 45 | 750 | 4500 | 85
T-104 | 25 | 900 | 6000 | 90
T-105 | 50 | 500 | 2000 | 75
T-106 | 30 | 850 | 5500 | 90
Pertanyaan:
a) (2 poin) Algoritma sorting mana yang paling tepat untuk sistem ini? Jelaskan alasannya dengan mempertimbangkan:
b) (2 poin) Tunjukkan urutan target setelah sorting berdasarkan kriteria multi-level di atas!
c) (3 poin) Implementasikan fungsi comparator dalam C++ untuk kriteria pengurutan ini!
Latar Belakang: Pusat komando menyimpan log komunikasi yang perlu dianalisis. Setiap log memiliki timestamp, unit pengirim, prioritas (1-5, dengan 1 tertinggi), dan ukuran pesan. Sistem harus mampu mengurutkan jutaan log untuk analisis forensik.
Spesifikasi Sistem:
Pertanyaan:
a) (2 poin) Hitung estimasi memori yang dibutuhkan untuk menyimpan semua log! Apakah muat di RAM?
b) (2 poin) Jika data muat di RAM, algoritma apa yang Anda rekomendasikan? Berikan justifikasi berdasarkan:
c) (2 poin) Estimasikan waktu eksekusi sorting jika satu operasi perbandingan memakan 1 mikrodetik! Bandingkan jika menggunakan:
d) (2 poin) Jelaskan bagaimana Anda akan memodifikasi algoritma jika data TIDAK muat di RAM (external sorting)!
| No | Jawaban | Pembahasan Singkat |
|---|---|---|
| 1 | B | Merge Sort selalu O(n log n) di semua kasus |
| 2 | C | Quick Sort worst case O(n²) saat pivot selalu min/max |
| 3 | C | Merge Sort adalah stable, mempertahankan urutan relatif |
| 4 | C | Divide and Conquer: bagi, selesaikan, gabungkan |
| 5 | B | Pivot adalah elemen pembanding untuk partisi |
| 6 | C | 6 elemen → 5 kali merge (pohon rekursi level 3) |
| 7 | C | Merge Sort memerlukan O(n) memori tambahan |
| 8 | C | Median-of-three meminimalkan kemungkinan worst case |
| 9 | B | Partisi tidak seimbang → O(n²) |
| 10 | C | Setelah partisi: [2,1,5,8,9], pivot 5 di index 2 |
| 11 | B | Lower bound Ω(n log n) untuk comparison-based sorting |
| 12 | B | Merge hanya perlu akses sekuensial |
| 13 | B | Master Theorem case 2: O(n log n) |
| 14 | E | Bubble Sort dengan early termination O(n) untuk data hampir terurut |
| 15 | B | Quick Sort adalah in-place (O(log n) stack space) |
| 16 | C | Conquer = rekursi pada subproblem |
| 17 | B | Setelah partisi dengan pivot 3: elemen ≤3 di kiri |
| 18 | B | Introsort = Quick Sort + Heap Sort + Insertion Sort |
| 19 | C | ⌈log₂(n!)⌉ adalah information-theoretic lower bound |
| 20 | D | Optimize dengan DP bukan bagian dari D&C |
Tiga langkah Divide and Conquer:
Array: [38, 27, 43, 3, 9, 82, 10]
Pohon Rekursi:
[38,27,43,3,9,82,10]
/ \
[38,27,43,3] [9,82,10]
/ \ / \
[38,27] [43,3] [9,82] [10]
/ \ / \ / \
[38] [27] [43] [3] [9] [82]
Proses Merge (bottom-up):
Stable sorting berarti jika dua elemen memiliki kunci yang sama, urutan relatif mereka dalam input dipertahankan dalam output.
Mengapa Merge Sort stable:
Contoh pentingnya stabilitas: Sorting data mahasiswa berdasarkan nilai, kemudian berdasarkan nama:
FUNCTION merge(arr, left, mid, right):
n1 ← mid - left + 1
n2 ← right - mid
CREATE L[n1], R[n2]
// Copy data ke array sementara
FOR i ← 0 TO n1-1:
L[i] ← arr[left + i]
FOR j ← 0 TO n2-1:
R[j] ← arr[mid + 1 + j]
// Merge kembali ke arr
i ← 0, j ← 0, k ← left
WHILE i < n1 AND j < n2:
IF L[i] <= R[j]: // <= untuk stabilitas
arr[k] ← L[i]
i ← i + 1
ELSE:
arr[k] ← R[j]
j ← j + 1
k ← k + 1
// Copy sisa elemen
WHILE i < n1:
arr[k] ← L[i]
i ← i + 1
k ← k + 1
WHILE j < n2:
arr[k] ← R[j]
j ← j + 1
k ← k + 1
Array: [5, 2, 8, 1, 9, 3], Pivot = 3 (elemen terakhir)
Lomuto Partition:
| j | arr[j] | arr[j] ≤ 3? | Aksi | Array | i |
|---|---|---|---|---|---|
| - | - | - | initial | [5,2,8,1,9,3] | -1 |
| 0 | 5 | No | - | [5,2,8,1,9,3] | -1 |
| 1 | 2 | Yes | i++, swap(1,1) | [5,2,8,1,9,3] | 0 |
| 2 | 8 | No | - | [5,2,8,1,9,3] | 0 |
| 3 | 1 | Yes | i++, swap(1,3) | [5,1,8,2,9,3] | 1 |
Koreksi: Mari ulang dengan benar:
Pivot 3 berada di index 2 (posisi akhir yang benar).
| Strategi | Kelebihan | Kekurangan |
|---|---|---|
| Elemen Pertama | Sederhana, O(1) | Worst case pada data terurut/terurut terbalik |
| Elemen Terakhir | Sederhana, O(1) | Sama dengan elemen pertama, rawan worst case |
| Median-of-three | Menghindari worst case untuk data terurut, mendekati median sebenarnya | Sedikit lebih kompleks, O(1) tetapi ada overhead |
Rekomendasi: Median-of-three karena memberikan keseimbangan antara kesederhanaan dan robustness terhadap data yang sudah terurut.
Rekurensi: T(n) = 2T(n/2) + n, T(1) = 1
Menggunakan Master Theorem:
Verifikasi dengan substitusi:
Untuk c = 1: T(n) = n log n ✓
Lower bound Ω(n log n) untuk comparison-based sorting:
Konsep Decision Tree:
Argument:
Kesimpulan: Setiap comparison-based sorting algorithm memerlukan minimal Ω(n log n) perbandingan dalam worst case.
#include <iostream>
using namespace std;
// Fungsi untuk mendapatkan median-of-three
int medianOfThree(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
// Sort three elements
if (arr[low] > arr[mid])
swap(arr[low], arr[mid]);
if (arr[low] > arr[high])
swap(arr[low], arr[high]);
if (arr[mid] > arr[high])
swap(arr[mid], arr[high]);
// Place median at high-1 position
swap(arr[mid], arr[high - 1]);
return arr[high - 1];
}
int partition(int arr[], int low, int high) {
int pivot = medianOfThree(arr, low, high);
int i = low;
int j = high - 1;
while (true) {
while (arr[++i] < pivot);
while (arr[--j] > pivot);
if (i < j)
swap(arr[i], arr[j]);
else
break;
}
swap(arr[i], arr[high - 1]); // Restore pivot
return i;
}
void quickSort(int arr[], int low, int high) {
if (low + 2 <= high) { // Minimal 3 elemen untuk median-of-three
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
} else if (low < high) {
// 2 elemen: simple comparison
if (arr[low] > arr[high])
swap(arr[low], arr[high]);
}
}
int main() {
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
Array: [10, 80, 30, 90, 40, 50, 70], Pivot = elemen terakhir
Partisi 1: Pivot = 70
[10, 30, 40, 50, 70, 90, 80]Partisi 2 (kiri): Array [10, 30, 40, 50], Pivot = 50
[10, 30, 40, 50]Partisi 3 (kiri kiri): Array [10, 30, 40], Pivot = 40
[10, 30, 40]Partisi 4 (kiri kiri kiri): Array [10, 30], Pivot = 30
[10, 30]Partisi 5 (kanan): Array [90, 80], Pivot = 80
[80, 90]Hasil akhir: [10, 30, 40, 50, 70, 80, 90]
Introsort (Introspective Sort):
Introsort adalah algoritma hybrid yang menggabungkan:
Cara kerja:
Mengapa digunakan di std::sort:
Analisis Kompleksitas Quick Sort:
a) Best Case: O(n log n)
b) Average Case: O(n log n)
c) Worst Case: O(n²)
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Mendapatkan node tengah
Node* getMiddle(Node* head) {
if (!head) return head;
Node* slow = head;
Node* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// Merge dua linked list terurut
Node* merge(Node* left, Node* right) {
if (!left) return right;
if (!right) return left;
Node* result = nullptr;
if (left->data <= right->data) {
result = left;
result->next = merge(left->next, right);
} else {
result = right;
result->next = merge(left, right->next);
}
return result;
}
// Merge Sort untuk Linked List
Node* mergeSort(Node* head) {
// Base case
if (!head || !head->next)
return head;
// Dapatkan node tengah
Node* middle = getMiddle(head);
Node* nextOfMiddle = middle->next;
// Putus linked list menjadi dua
middle->next = nullptr;
// Rekursif sort kedua bagian
Node* left = mergeSort(head);
Node* right = mergeSort(nextOfMiddle);
// Merge hasil
return merge(left, right);
}
Perbedaan dengan array:
n = 1,000,000 elemen
a) Bubble Sort O(n²):
b) Merge Sort O(n log n):
c) Quick Sort average O(n log n):
Rasio Perbandingan: | Algoritma | Operasi | Rasio vs Merge Sort | |———–|———|———————| | Bubble Sort | 10¹² | 50,000× lebih lambat | | Merge Sort | 2×10⁷ | 1× (baseline) | | Quick Sort | 2×10⁷ | ~1× (sedikit lebih cepat) |
Waktu estimasi (1 μs per operasi):
const int THRESHOLD = 16;
void insertionSort(int arr[], int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void merge(int arr[], int left, int mid, int right) {
// Implementasi merge standar
// ... (sama seperti sebelumnya)
}
void hybridMergeSort(int arr[], int left, int right) {
if (right - left + 1 <= THRESHOLD) {
// Gunakan Insertion Sort untuk subarray kecil
insertionSort(arr, left, right);
return;
}
if (left < right) {
int mid = left + (right - left) / 2;
hybridMergeSort(arr, left, mid);
hybridMergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
Mengapa lebih efisien:
a) Algoritma yang tepat: Merge Sort
Alasan:
b) Urutan setelah sorting:
Kriteria: Threat Score (desc) → Jarak (asc) → Kecepatan (desc)
| Urutan | ID | Threat | Jarak | Kecepatan |
|---|---|---|---|---|
| 1 | T-104 | 90 | 25 | 900 |
| 2 | T-106 | 90 | 30 | 850 |
| 3 | T-102 | 90 | 30 | 600 |
| 4 | T-103 | 85 | 45 | 750 |
| 5 | T-101 | 85 | 45 | 800 |
Koreksi urutan T-101 dan T-103:
| Urutan | ID | Threat | Jarak | Kecepatan |
|---|---|---|---|---|
| 1 | T-104 | 90 | 25 | 900 |
| 2 | T-106 | 90 | 30 | 850 |
| 3 | T-102 | 90 | 30 | 600 |
| 4 | T-101 | 85 | 45 | 800 |
| 5 | T-103 | 85 | 45 | 750 |
| 6 | T-105 | 75 | 50 | 500 |
c) Fungsi comparator:
struct Target {
string id;
int jarak;
int kecepatan;
int altitude;
int threatScore;
};
bool compareTarget(const Target& a, const Target& b) {
// Prioritas 1: Threat score (descending)
if (a.threatScore != b.threatScore)
return a.threatScore > b.threatScore;
// Prioritas 2: Jarak (ascending)
if (a.jarak != b.jarak)
return a.jarak < b.jarak;
// Prioritas 3: Kecepatan (descending)
return a.kecepatan > b.kecepatan;
}
// Penggunaan:
// stable_sort(targets.begin(), targets.end(), compareTarget);
a) Estimasi memori:
Kesimpulan: Ya, muat di RAM 4 GB dengan sisa ~3 GB untuk working memory.
b) Rekomendasi: Merge Sort (atau Timsort)
Justifikasi:
c) Estimasi waktu (1 μs per perbandingan):
n = 5,000,000
| Algoritma | Operasi | Waktu |
|---|---|---|
| Merge Sort | n × log₂(n) = 5×10⁶ × 22.3 ≈ 1.1×10⁸ | 110 detik |
| Quick Sort | ~1.4 × n × log₂(n) ≈ 1.5×10⁸ | 150 detik |
| Bubble Sort | n² = 2.5×10¹³ | 289 hari |
d) External Sorting (jika tidak muat di RAM):
Pendekatan: External Merge Sort
Kompleksitas I/O: O((n/B) × log(n/M))
Ilustrasi External Merge Sort:
[5GB data on disk]
↓ read 500MB chunks
[chunk1] [chunk2] ... [chunk10]
↓ sort in memory
[sorted1] [sorted2] ... [sorted10]
↓ write to temp files
↓ k-way merge with min-heap
[final sorted output]
| Bagian | Jumlah Soal | Poin per Soal | Total |
|---|---|---|---|
| Pilihan Ganda | 20 | 2 | 40 |
| Uraian | 15 | 3 | 45 |
| Studi Kasus 1 | 3 sub | 2+2+3 | 7 |
| Studi Kasus 2 | 4 sub | 2+2+2+2 | 8 |
| Total | 100 |
This repository is licensed under the Creative Commons Attribution 4.0 International (CC BY 4.0). Commercial use is permitted, provided attribution is given to the author.
© 2026 Anindito