🔢 Algoritma Sorting Dasar

Struktur Data dan Algoritma

Pertemuan 09

Universitas Pertahanan RI

🎯 Tujuan Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

Mengimplementasikan Bubble Sort dengan optimasi early termination
Mengimplementasikan Selection Sort dan memahami karakteristiknya
Mengimplementasikan Insertion Sort dan keunggulannya
Menganalisis kompleksitas waktu dan ruang ketiga algoritma
Menjelaskan perbedaan stable dan unstable sort
Memilih algoritma sorting yang tepat untuk kasus tertentu

📋 Agenda

Bagian 1

Pengantar Sorting
Bubble Sort
Selection Sort

Bagian 2

Insertion Sort
Stable vs Unstable Sort
Perbandingan Algoritma

📖 1. Pengantar Sorting

Sorting (Pengurutan) adalah proses menyusun elemen-elemen dalam urutan tertentu berdasarkan kunci perbandingan.

Contoh: [64, 34, 25, 12, 22, 11, 90]

Hasil: [11, 12, 22, 25, 34, 64, 90]

Mengapa Sorting Penting?

🔍 Pencarian

Binary search memerlukan data terurut: O(log n)

📊 Analisis

Statistik, median, percentile lebih mudah

🔗 Merge

Penggabungan data terurut efisien: O(n)

🎖️ Aplikasi di Bidang Pertahanan

Sistem Radar: Mengurutkan target berdasarkan jarak/ancaman
Komunikasi Militer: Prioritas pesan berdasarkan urgensi
Logistik: Urutan pengiriman berdasarkan waktu/prioritas
Intelijen: Ranking data berdasarkan relevansi

Klasifikasi Algoritma Sorting

Kriteria	Kategori	Contoh
Berbasis	Comparison / Non-comparison	Quick Sort / Counting Sort
Memory	In-place / Out-of-place	Bubble Sort / Merge Sort
Stabilitas	Stable / Unstable	Insertion Sort / Selection Sort
Adaptivitas	Adaptive / Non-adaptive	Insertion Sort / Selection Sort

📖 2. Bubble Sort

Bubble Sort bekerja dengan membandingkan dan menukar elemen berdekatan secara berulang hingga seluruh array terurut.

Elemen terbesar akan "menggelembung" (bubble) ke posisi akhir di setiap iterasi.

💻 Algoritma Bubble Sort


void bubbleSort(int arr[], int n) {
    // Lakukan n-1 pass
    for (int i = 0; i < n - 1; i++) {
        // Bandingkan elemen berdekatan
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

Perhatikan: n - 1 - i karena elemen terakhir sudah terurut!

🔄 Visualisasi Bubble Sort

Gambar: Proses Bubble Sort pass demi pass

⚡ Optimasi: Early Termination


void bubbleSortOptimized(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Flag untuk deteksi swap
        bool swapped = false;
        
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        
        // Jika tidak ada swap, array sudah terurut!
        if (!swapped) break;
    }
}

📊 Kompleksitas Bubble Sort

Kasus	Kompleksitas	Kondisi
Best Case	O(n)	Array sudah terurut (dengan optimasi)
Average Case	O(n²)	Array acak
Worst Case	O(n²)	Array terurut terbalik

Space Complexity: O(1) — In-place algorithm

🧠 Quiz: Bubble Sort

Berapa kali swap dilakukan untuk mengurutkan [5, 3, 1] dengan Bubble Sort?


Array awal: [5, 3, 1]
Pass 1: ?
Pass 2: ?

Jawaban: 3 swap

Pass 1: [5,3,1] → [3,5,1] → [3,1,5] (2 swap)
Pass 2: [3,1,5] → [1,3,5] (1 swap)

📖 3. Selection Sort

Selection Sort bekerja dengan mencari elemen minimum dari bagian yang belum terurut, lalu menukarnya dengan elemen pertama bagian tersebut.

"Pilih (select) yang terkecil, taruh di depan."

💻 Algoritma Selection Sort


void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;  // Asumsi elemen i adalah minimum
        
        // Cari minimum di sisa array
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        
        // Tukar jika minimum bukan di posisi i
        if (minIdx != i) {
            swap(arr[i], arr[minIdx]);
        }
    }
}

🔄 Visualisasi Selection Sort

Gambar: Proses Selection Sort — mencari minimum dan menukar

📊 Kompleksitas Selection Sort

Kasus	Kompleksitas	Keterangan
Best Case	O(n²)	Tetap harus mencari minimum
Average Case	O(n²)	Selalu sama
Worst Case	O(n²)	Selalu sama

✅ Keunggulan: Maksimum n-1 swap — cocok saat operasi swap mahal!

🧠 Quiz: Selection Sort

Berapa kali swap (maksimum) yang dilakukan Selection Sort untuk array berukuran n?

A. n² B. n log n C. n-1 D. n

Jawaban: C. n-1

Selection Sort melakukan maksimum n-1 swap (satu per iterasi outer loop).
Ini berbeda dengan Bubble Sort yang bisa melakukan banyak swap per pass.

📖 4. Insertion Sort

Insertion Sort membangun array terurut satu elemen pada satu waktu, dengan menyisipkan setiap elemen ke posisi yang tepat di bagian terurut.

Seperti menyortir kartu di tangan — ambil satu kartu, sisipkan di posisi yang benar.

💻 Algoritma Insertion Sort


void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // Elemen yang akan disisipkan
        int j = i - 1;
        
        // Geser elemen yang lebih besar ke kanan
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;  // Sisipkan key di posisi yang tepat
    }
}

🔄 Visualisasi Insertion Sort

Gambar: Proses Insertion Sort — menyisipkan elemen ke posisi yang tepat

📊 Kompleksitas Insertion Sort

Kasus	Kompleksitas	Kondisi
Best Case	O(n)	Array sudah terurut
Average Case	O(n²)	Array acak
Worst Case	O(n²)	Array terurut terbalik

⭐ Keunggulan Insertion Sort

✅ Kelebihan:

Adaptive — O(n) untuk data hampir terurut
Stable — Menjaga urutan relatif
Online — Bisa sort sambil menerima data
Efisien — Untuk data kecil (n < 50)

⚠️ Kekurangan:

O(n²) untuk data besar
Banyak operasi geser

🧠 Quiz: Insertion Sort

Algoritma sorting mana yang paling efisien untuk array yang "hampir terurut"?

A. Bubble Sort B. Selection Sort C. Insertion Sort D. Semua sama

Jawaban: C. Insertion Sort

Insertion Sort adalah adaptive algorithm — kompleksitasnya mendekati O(n) ketika data hampir terurut, karena inner loop hampir tidak berjalan.

📖 5. Stable vs Unstable Sort

Stable Sort mempertahankan urutan relatif elemen dengan kunci yang sama.

Contoh: Sort berdasarkan nilai, jaga urutan abjad


Input:  [(A,3), (B,1), (C,3), (D,2)]
Stable: [(B,1), (D,2), (A,3), (C,3)]  ← A sebelum C
Unstable: [(B,1), (D,2), (C,3), (A,3)]  ← Urutan bisa berubah

🔄 Visualisasi Stability

Gambar: Perbedaan stable dan unstable sort

📊 Stabilitas Algoritma

Algoritma	Stabilitas	Alasan
Bubble Sort	✅ Stable	Swap hanya jika `>`, bukan `>=`
Selection Sort	❌ Unstable	Swap melewati elemen sama
Insertion Sort	✅ Stable	Geser hanya jika `>`, bukan `>=`

💡 Tips: Stabilitas penting saat sorting dengan multiple keys (multi-level sorting).

🎖️ Contoh: Sorting Personel Militer

Urutkan berdasarkan pangkat, lalu masa kerja:


Input (urut abjad):
  [("Andi", Sersan, 5th), ("Budi", Letnan, 3th), 
   ("Citra", Sersan, 8th), ("Doni", Letnan, 5th)]

1️⃣ Sort by masa kerja (stable):
  [("Budi", Letnan, 3th), ("Andi", Sersan, 5th), 
   ("Doni", Letnan, 5th), ("Citra", Sersan, 8th)]

2️⃣ Sort by pangkat (stable):
  [("Andi", Sersan, 5th), ("Citra", Sersan, 8th),  ← Sersan terurut by masa kerja
   ("Budi", Letnan, 3th), ("Doni", Letnan, 5th)]  ← Letnan terurut by masa kerja

📖 6. Perbandingan Algoritma

Kriteria	Bubble Sort	Selection Sort	Insertion Sort
Best Case	O(n)*	O(n²)	O(n)
Average Case	O(n²)	O(n²)	O(n²)
Worst Case	O(n²)	O(n²)	O(n²)
Space	O(1)	O(1)	O(1)
Stable?	Ya	Tidak	Ya
Adaptive?	Ya*	Tidak	Ya

* Dengan optimasi early termination

🤔 Kapan Menggunakan?

Bubble Sort

Pembelajaran
Deteksi sorted
Data sangat kecil

Selection Sort

Swap mahal
Memori terbatas
Jumlah write penting

Insertion Sort

Data hampir terurut
Data kecil (n < 50)
Online sorting
Perlu stable sort

📈 Perbandingan Visual

Gambar: Panduan pemilihan algoritma sorting

🎖️ Studi Kasus: Sistem Radar

Skenario: Sistem radar mendeteksi 20 target yang perlu diurutkan berdasarkan jarak dan tingkat ancaman.

Analisis:

Data kecil (n=20) → Insertion Sort cocok
Data mungkin sudah hampir terurut (update posisi) → Adaptive
Perlu stable sort untuk multi-key → Insertion Sort

💻 Implementasi: Sorting Radar Target


struct Target {
    int id;
    double jarak;      // km
    int levelAncaman;  // 1-5
};

// Insertion Sort by levelAncaman (descending), then jarak (ascending)
void sortTargetByPriority(Target arr[], int n) {
    for (int i = 1; i < n; i++) {
        Target key = arr[i];
        int j = i - 1;
        
        // Compare: higher threat first, closer first
        while (j >= 0 && 
               (arr[j].levelAncaman < key.levelAncaman ||
                (arr[j].levelAncaman == key.levelAncaman && 
                 arr[j].jarak > key.jarak))) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

📝 Ringkasan

Algoritma	Cara Kerja	Best/Worst	Karakteristik
Bubble Sort	Bandingkan & tukar berdekatan	O(n) / O(n²)	Stable, Adaptive*
Selection Sort	Pilih minimum, taruh di depan	O(n²) / O(n²)	Unstable, Min swap
Insertion Sort	Sisipkan ke posisi yang tepat	O(n) / O(n²)	Stable, Adaptive, Online

Key Takeaway: Untuk data kecil atau hampir terurut, Insertion Sort adalah pilihan terbaik!

🔬 Tugas Praktikum

Implementasikan ketiga algoritma sorting dalam C++
Buat fungsi untuk menghitung jumlah perbandingan dan swap
Uji dengan berbagai ukuran data: 10, 100, 1000, 10000
Uji dengan berbagai kondisi: sorted, reverse, random
Buat tabel dan grafik perbandingan performa

💡 Hint: Gunakan chrono untuk mengukur waktu eksekusi!

❓ Pertanyaan?

Silakan bertanya atau diskusi

Referensi: Cormen Ch.2 | Weiss Ch.7.2 | Hubbard Ch.13

Terima Kasih! 🙏

Struktur Data dan Algoritma

Pertemuan 09: Algoritma Sorting Dasar