Gambaran besar dulu
Bayangkan kamu punya 8 lembar kartu nilai ulangan yang berantakan di atas meja: 5, 2, 8, 1, 9, 3, 7, 4. Tugasmu: urutkan dari terkecil ke terbesar.
Cara paling intuitif yang kebanyakan orang lakukan secara alami adalah ini: pindai semua kartu, ambil yang nilainya paling kecil, taruh di paling kiri. Lalu ulangi lagi dari sisa kartu yang belum diurutkan.
Itu persis cara kerja Selection Sort — “pilih yang terkecil, taruh di tempatnya, lanjut.”
Konsep inti: dua zona
Selama proses berlangsung, daftar kamu selalu terbagi jadi dua bagian:
- Zona kiri (zona terurut): sudah beres, tidak disentuh lagi
- Zona kanan (zona belum terurut): masih berantakan, masih perlu diproses
Di awal, zona kiri kosong. Di akhir, zona kanan kosong. Kita pindahkan satu elemen per iterasi dari kanan ke kiri.
Simulasi lengkap: daftar [5, 2, 8, 1, 9, 3, 7, 4]
Iterasi 1
Zona belum terurut: semua 8 angka. Cari yang terkecil.
5, 2, 8, 1, 9, 3, 7, 4 → minimum = 1 (ada di indeks ke-3)
Tukar 1 dengan angka di posisi paling kiri (yaitu 5):
[1] | 2, 8, 5, 9, 3, 7, 4
Zona kiri: [1]. Selesai untuk posisi 0.
Iterasi 2
Zona belum terurut: 2, 8, 5, 9, 3, 7, 4. Cari minimum.
Minimum = 2, sudah ada di posisi pertama zona ini. Tidak perlu tukar.
[1, 2] | 8, 5, 9, 3, 7, 4
Iterasi 3
Zona belum terurut: 8, 5, 9, 3, 7, 4. Cari minimum.
Minimum = 3 (indeks ke-5 dari daftar asli). Tukar dengan 8.
[1, 2, 3] | 5, 9, 8, 7, 4
Iterasi 4
Zona belum terurut: 5, 9, 8, 7, 4. Cari minimum.
Minimum = 4. Tukar dengan 5.
[1, 2, 3, 4] | 9, 8, 7, 5
Iterasi 5
Zona belum terurut: 9, 8, 7, 5. Cari minimum.
Minimum = 5. Tukar dengan 9.
[1, 2, 3, 4, 5] | 8, 7, 9
Iterasi 6
Zona belum terurut: 8, 7, 9. Cari minimum.
Minimum = 7. Tukar dengan 8.
[1, 2, 3, 4, 5, 7] | 8, 9
Iterasi 7
Zona belum terurut: 8, 9. Cari minimum.
Minimum = 8. Sudah di posisi benar, tidak perlu tukar.
[1, 2, 3, 4, 5, 7, 8] | 9
Iterasi 8 (selesai)
Sisa satu elemen, otomatis sudah benar.
Hasil akhir: [1, 2, 3, 4, 5, 7, 8, 9] ✓
Sifat khas Selection Sort yang wajib diingat
Ini yang membuat Selection Sort berbeda dari algoritma lain:
- Selalu melakukan tepat n-1 iterasi (8 angka = 7 iterasi)
- Total perbandingan: n(n-1)/2 — untuk 8 angka berarti 28 perbandingan
- Tidak peduli apakah data sudah hampir terurut atau benar-benar acak, jumlah perbandingannya sama saja
Analogi nyatanya: bayangkan kamu disuruh memilih siswa terpendek dari barisan, lalu kamu harus tetap berjalan dan mengecek setiap orang satu per satu dari ujung ke ujung — meski kamu sudah tahu siapa yang paling pendek sejak menit pertama. Itulah “kelemahan” Selection Sort: dia tidak bisa “skip” meski kondisi data sebenarnya sudah bagus.
Perbandingan Selection Sort vs Insertion Sort
| Aspek | Selection Sort | Insertion Sort |
|---|---|---|
| Cara kerja | Cari minimum, taruh di posisi yang benar | Ambil elemen, sisipkan ke posisi yang tepat di zona terurut |
| Jumlah perbandingan | Selalu tetap: n(n-1)/2 | Bervariasi: bisa sedikit kalau data hampir terurut |
| Jumlah pertukaran (swap) | Maksimal n-1 kali (satu swap per iterasi) | Bisa lebih banyak, tergantung seberapa jauh elemen harus bergeser |
| Performa data acak | Sama saja | Sama saja |
| Performa data hampir terurut | Tetap lambat | Bisa sangat cepat |
Poin diskusi itu: Selection Sort menang soal jumlah pertukaran (swap). Setiap iterasi paling banyak satu kali tukar. Insertion Sort bisa melakukan banyak pergeseran hanya untuk menyisipkan satu elemen ke posisi yang benar.
Kalau data sudah hampir terurut, Insertion Sort jauh lebih efisien. Tapi kalau yang dikhawatirkan adalah operasi swap (misalnya menulis ke memory mahal), Selection Sort lebih hemat.
Jebakan umum yang sering salah
- Lupa bahwa indeks bergeser. Setiap iterasi, zona pencarian mengecil satu. Jangan cari minimum dari seluruh daftar lagi di iterasi kedua dan seterusnya.
- Bingung “tidak perlu tukar” itu valid. Kalau minimum sudah ada di posisi paling kiri zona belum terurut, kita tetap menghitung iterasi tersebut sebagai selesai, tapi tidak melakukan swap.
- Mengira n iterasi, bukan n-1. Elemen terakhir otomatis sudah di posisi benar, jadi iterasi ke-n tidak diperlukan.
Kuis Cepat
-
Pada daftar
[3, 6, 1, 8, 2], setelah iterasi pertama Selection Sort selesai, seperti apa tampilan daftarnya? -
Selection Sort pada daftar 10 angka melakukan berapa total perbandingan?
-
Dalam kondisi data yang hampir terurut, mana yang lebih efisien: Selection Sort atau Insertion Sort? Jelaskan alasanmu dalam satu kalimat.