Selection sort mengurutkan array dengan cara memilih: cari angka terkecil, taruh di depan. Lalu cari yang terkecil dari sisanya, taruh di posisi kedua, dan seterusnya. Kayak menyusun kartu di meja: ambil yang paling kecil dulu, lalu yang paling kecil berikutnya.
🧪 Tebakan cepat: array-nya sudah urut. Apa selection sort jadi lebih cepat? Tebak dulu, jawabannya ada di bagian "Seberapa lambat".
Cara kerjanya
Urutkan [64, 25, 12, 22, 11]. Satu pass mengisi satu posisi, mulai dari kiri: cari yang terkecil dari bagian yang belum urut, lalu tukar sekali ke depan bagian itu.
| Pass | Yang terjadi | Array sesudahnya |
|---|---|---|
| 1 | terkecil dari semua: 11, tukar dengan 64 | [11, 25, 12, 22, 64] |
| 2 | terkecil dari sisa: 12, tukar dengan 25 | [11, 12, 25, 22, 64] |
| 3 | terkecil dari sisa: 22, tukar dengan 25 | [11, 12, 22, 25, 64] |
| 4 | terkecil dari sisa: 25, sudah di tempatnya | [11, 12, 22, 25, 64] |
Angka terakhir yang tersisa pasti yang terbesar, jadi 5 angka cukup 4 pass.
function selectionSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
let minIdx = i; // cari yang terkecil dari sisa array
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx !== i) {
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]]; // paling banyak satu tukar per pass
}
}
return arr;
}
console.log(selectionSort([64, 25, 12, 22, 11]).join(",")); // 11,12,22,25,64
iadalah posisi yang sedang diisi. Semua index sebelumisudah urut.minIdxmenyimpan index angka terkecil yang ketemu sejauh ini. Mulainya dariisendiri.- Loop dalam mulai dari
i + 1dan mengecek sisanya. Ketemu yang lebih kecil dariarr[minIdx]? Simpan index-nya. - Sesudah loop dalam selesai, baru tukar
arr[i]denganarr[minIdx]. Kalau yang terkecil sudah di posisii, gak perlu tukar. return arrsesudah loop luar, lalu.join(",")menggabungkannya jadi teks11,12,22,25,64.
Seberapa lambat
Banyaknya data disebut n. Selection sort selalu mengecek semua sisa, apa pun datanya: 5 angka butuh 4 + 3 + 2 + 1 = 10 perbandingan, bahkan kalau sudah urut. Jadi jawaban tebakannya: gak lebih cepat. Perbandingannya O(n²) di semua kasus: datanya dua kali lipat, waktunya kira-kira empat kali lipat.
Kelebihannya ada di jumlah tukar: paling banyak satu tukar per pass, jadi paling banyak n - 1 tukar. Itu O(n) tukar: datanya dua kali lipat, tukarnya paling banyak dua kali lipat. Bubble sort bisa menukar sampai O(n²) kali. Karena itu selection sort cocok kalau menulis atau memindahkan data itu mahal.
⚠️ Jebakan yang sering ketemu
- Menukar di dalam loop dalam. Kalau kamu menukar setiap ketemu yang lebih kecil, hasilnya mungkin urut, tapi tukarnya jadi banyak dan itu bukan selection sort lagi. Simpan index-nya dulu, tukar sekali sesudah loop dalam.
- Menyimpan nilainya, bukan index-nya. Kalau yang disimpan cuma angka terkecilnya, kamu gak tahu posisinya, jadi gak bisa menukar.
minIdxmulai dari 0.let minIdx = 0di setiap pass selalu menunjuk ke angka yang sudah urut di depan. Mulai dariminIdx = i.- Lupa
return arr. Tanpa itu function mengembalikanundefined, dan.join(",")bikin error.
🎯 Bubble, selection, atau insertion?
| Bubble sort | Selection sort | Insertion sort | |
|---|---|---|---|
| Tiap pass | tukar tetangga yang salah urut | cari yang terkecil, tukar sekali | sisipkan satu angka ke bagian kiri yang sudah urut |
| Data sudah urut | O(n) dengan swapped |
tetap O(n²) | O(n) |
| Banyak tukar | bisa O(n²) | paling banyak n - 1 | geser bisa O(n²) |
| Stabil | ya | tidak | ya |
Stabil artinya dua nilai yang sama tetap di urutan aslinya, misalnya dua siswa dengan nilai yang sama tetap di urutan daftar awal. Insertion sort ada di materi berikutnya.
TL;DR: Selection sort mengisi posisi dari kiri: di tiap pass, cari index terkecil (minIdx) dari sisa array, lalu tukar sekali ke posisi i. Simpan index-nya, tukar sesudah loop dalam, dan return arr. Perbandingannya selalu O(n²), bahkan untuk data yang sudah urut, tapi tukarnya paling banyak n - 1, jadi O(n). Selection sort gak stabil.
