🔀 Algoritma Sorting Lanjut

Merge Sort & Quick Sort

Pertemuan 10

Universitas Pertahanan RI

🎯 Tujuan Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

Menjelaskan prinsip divide-and-conquer
Mengimplementasikan merge sort dengan benar
Mengimplementasikan quick sort dengan berbagai strategi pivot
Membandingkan performa kedua algoritma
Memilih algoritma sorting yang tepat berdasarkan karakteristik data

📋 Agenda

Bagian 1

Review Sorting Dasar
Paradigma Divide-and-Conquer
Merge Sort

Bagian 2

Quick Sort
Perbandingan & Lower Bound
Pemilihan Algoritma

📖 1. Keterbatasan Sorting Dasar

Algoritma sorting dari Pertemuan 9:

Algoritma	Best	Average	Worst
Bubble Sort	O(n)	O(n²)	O(n²)
Selection Sort	O(n²)	O(n²)	O(n²)
Insertion Sort	O(n)	O(n²)	O(n²)

O(n²) tidak praktis untuk dataset besar!

⚠️ Masalah dengan O(n²)

Jumlah Elemen	O(n²) Operasi	O(n log n) Operasi	Rasio
1,000	1,000,000	~10,000	100×
10,000	100,000,000	~133,000	750×
1,000,000	10¹²	~20,000,000	50,000×

🎖️ Konteks Pertahanan: Sistem radar yang mendeteksi ribuan objek butuh O(n log n)!

📖 2. Paradigma Divide-and-Conquer

Divide-and-Conquer adalah strategi memecah masalah besar menjadi sub-masalah lebih kecil, menyelesaikan secara rekursif, lalu menggabungkan solusinya.

Tiga Langkah D&C

1️⃣ DIVIDE

Pecah masalah menjadi sub-masalah lebih kecil

2️⃣ CONQUER

Selesaikan sub-masalah secara rekursif

3️⃣ COMBINE

Gabungkan solusi menjadi solusi akhir

Visualisasi Divide-and-Conquer

Gambar 10.1: Paradigma divide-and-conquer

Algoritma Sorting O(n log n)

Algoritma	Waktu	Ruang	Stable	In-place
Merge Sort	O(n log n)	O(n)	✅ Ya	❌ Tidak
Quick Sort	O(n log n)*	O(log n)	❌ Tidak	✅ Ya

* rata-rata, worst case O(n²)

📖 3. Merge Sort

Merge Sort membagi array menjadi dua bagian, mengurutkan masing-masing secara rekursif, kemudian menggabungkan (merge) kedua bagian yang sudah terurut.

Langkah Merge Sort

Divide: Bagi array menjadi 2 bagian sama besar
Conquer: Urutkan kedua bagian secara rekursif
Combine: Gabungkan (merge) kedua bagian terurut

Base case: Array dengan 0 atau 1 elemen sudah terurut

Visualisasi Merge Sort

Gambar 10.2: Proses merge sort pada [38, 27, 43, 3, 9, 82, 10]

💻 Fungsi Merge


void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int* L = new int[n1];
    int* R = new int[n2];
    
    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];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    
    delete[] L; delete[] R;
}

💻 Implementasi Merge Sort


void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // Cari titik tengah
        int mid = left + (right - left) / 2;
        
        // Rekursi kiri dan kanan
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Gabungkan
        merge(arr, left, mid, right);
    }
}

Analisis Kompleksitas Merge Sort

Recurrence Relation:

T(n) = 2T(n/2) + O(n)

Kasus	Kompleksitas Waktu
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

Ruang: O(n) untuk array temporary

🧠 Quiz: Merge Sort

Berapa jumlah operasi merge untuk mengurutkan array 8 elemen?

Jawaban: 7 operasi merge

Formula: n - 1 = 8 - 1 = 7

Level 2→1: 4 merge, Level 1→0: 2 merge, Level 0: 1 merge

📖 4. Quick Sort

Quick Sort memilih elemen sebagai pivot, mempartisi array sehingga elemen lebih kecil di kiri dan lebih besar di kanan, lalu rekursi.

Langkah Quick Sort

Pilih Pivot: Pilih satu elemen sebagai pivot
Partition: Susun ulang array:
- Elemen < pivot → kiri
- Elemen > pivot → kanan
Rekursi: Terapkan quick sort pada subarray kiri dan kanan

Visualisasi Quick Sort

Gambar 10.3: Proses quick sort dengan pivot terakhir

💻 Fungsi Partition (Lomuto)


int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Pivot = elemen terakhir
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    
    swap(arr[i + 1], arr[high]);
    return i + 1;  // Posisi pivot
}

Proses Partition

Gambar 10.4: Langkah-langkah partition (Lomuto scheme)

💻 Implementasi Quick Sort


void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Partisi dan dapatkan posisi pivot
        int pivotIndex = partition(arr, low, high);
        
        // Rekursi kiri dan kanan (tanpa pivot)
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

Strategi Pemilihan Pivot

Strategi	Kelebihan	Kekurangan
First/Last	Sederhana	O(n²) pada data terurut
Random	Menghindari worst case	Butuh random generator
Median-of-Three	Balance yang baik	Sedikit overhead

✅ Rekomendasi: Gunakan Median-of-Three atau Random

Analisis Kompleksitas Quick Sort

Kasus	Kompleksitas	Kondisi
Best Case	O(n log n)	Pivot selalu di tengah
Average Case	O(n log n)	Pivot cukup seimbang
Worst Case	O(n²)	Pivot selalu min/max

Ruang: O(log n) untuk call stack (rata-rata)

🧠 Quiz: Quick Sort Partition

Untuk array [7, 2, 1, 6, 8, 5, 3, 4] dengan pivot = 4 (terakhir), di posisi mana pivot setelah partition?

Jawaban: Index 3

Elemen < 4: [2, 1, 3] → 3 elemen di kiri

Hasil: [2, 1, 3, 4, 8, 5, 7, 6]

📖 5. Merge Sort vs Quick Sort

Gambar 10.5: Perbandingan karakteristik merge sort dan quick sort

Tabel Perbandingan

Aspek	Merge Sort	Quick Sort
Worst Case	O(n log n)	O(n²)
Space	O(n)	O(log n)
Stable	Ya	Tidak
In-place	Tidak	Ya
Cache	Kurang baik	Baik

Kapan Menggunakan?

Pilih Merge Sort:

Butuh stable sort
Data di linked list
External sorting (disk)
Worst case O(n²) tidak boleh

Pilih Quick Sort:

Memori terbatas
Data di array (cache-friendly)
Internal sorting
Performa rata-rata penting

Lower Bound: Ω(n log n)

Untuk comparison-based sorting, tidak mungkin lebih cepat dari Ω(n log n) pada kasus terburuk.

Penjelasan (Decision Tree):

n! kemungkinan permutasi
Butuh n! daun di decision tree
Tinggi minimum: log₂(n!) = Ω(n log n)

📖 6. Pemilihan Algoritma

Gambar 10.7: Flowchart pemilihan algoritma sorting

Panduan Praktis

Kondisi	Rekomendasi
n < 50	Insertion Sort
Data hampir terurut	Insertion Sort
Butuh stable sort	Merge Sort
Memori terbatas	Quick Sort atau Heap Sort
Worst case tidak boleh buruk	Merge Sort atau Heap Sort
Performa rata-rata optimal	Quick Sort

🎖️ Aplikasi Pertahanan

Sistem Radar Tracking:

Ribuan objek terdeteksi per detik
Harus diurutkan berdasarkan prioritas ancaman
Quick Sort untuk kecepatan rata-rata
Atau Merge Sort jika butuh worst-case guarantee

⚠️ Sistem kritis sebaiknya gunakan Introsort (hybrid quick+heap+insertion)

Introsort: Algoritma Hybrid

Introsort = Quick Sort + Heap Sort + Insertion Sort

Mulai dengan Quick Sort
Jika rekursi terlalu dalam → switch ke Heap Sort
Untuk partisi kecil → gunakan Insertion Sort

Digunakan oleh: std::sort() di C++ STL

📝 Ringkasan

Konsep	Poin Penting
Divide-and-Conquer	Bagi → Taklukkan → Gabungkan
Merge Sort	O(n log n) selalu, O(n) ruang, stable
Quick Sort	O(n log n) rata-rata, O(log n) ruang, in-place
Pivot Selection	Median-of-three atau random untuk menghindari O(n²)
Lower Bound	Comparison-based sorting minimal Ω(n log n)
Introsort	Hybrid: Quick + Heap + Insertion (C++ std::sort)

❓ Pertanyaan?

Silakan bertanya atau diskusi

Referensi: Cormen Ch.7-8 | Weiss Ch.7.4-7.7 | Hubbard Ch.13

Terima Kasih! 🙏

Struktur Data dan Algoritma

Pertemuan 10 — Algoritma Sorting Lanjut