Selection Sort mencari elemen terkecil dan menaruhnya di posisi yang benar, satu per satu.

Kompleksitas: O(n²) — selalu, tidak ada best case

Cara kerja:

1. Cari elemen terkecil di seluruh array
2. Tukar dengan elemen di posisi pertama
3. Cari terkecil dari sisa array
4. Tukar dengan posisi kedua... dst

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

selectionSort([64, 25, 12, 22, 11]);
// Step 1: Cari min → 11, tukar dengan 64 → [11, 25, 12, 22, 64]
// Step 2: Cari min dari sisa → 12, tukar dengan 25 → [11, 12, 25, 22, 64]
// Step 3: → [11, 12, 22, 25, 64]
// Step 4: → [11, 12, 22, 25, 64] (sudah benar)

Kelebihan:

• Jumlah swap minimal — O(n) swap
• Memori minimal — in-place

Kekurangan:

• Selalu O(n²) walaupun data sudah terurut
• Tidak stabil (bisa mengubah urutan elemen equal)

🎭 Analogi sehari-hari: Susun kartu remi dari kecil ke besar. Cara selection sort: cari kartu paling kecil di seluruh tangan kamu, taruh di kiri. Cari kartu paling kecil dari sisanya, taruh di sebelahnya. Ulangi sampai habis. Berbeda dengan bubble sort yang nuker pasangan terus.

💡 Selection vs Bubble vs Insertion: Semuanya O(n²), tapi karakter beda:

• Bubble: banyak swap, banyak compare
• Selection: sedikit swap (n), banyak compare
• Insertion: efisien untuk hampir-sorted, sedikit shift

Kalau swap mahal (misal data besar atau di disk), Selection menang karena cuma n swap total.

⚠️ Jebakan umum:

• Tidak adaptive — data sudah sorted? Tetap O(n²). Beda dari Bubble (O(n) best dengan early exit)
• Tidak stable secara default — [3a, 3b, 1] jadi [1, 3b, 3a] (3a dan 3b tertukar). Untuk stable, butuh insert bukan swap
• Jangan dipakai untuk dataset besar — sama lambatnya dengan Bubble

🎯 Karakter Selection Sort:

• In-place: ya
• Stable: tidak (kecuali modifikasi pakai shift)
• Best/Average/Worst: semua O(n²) (no adaptive)
• Swap count: O(n) — paling sedikit di antara O(n²) sorts

🧪 Tebakan cepat: Sort 1jt elemen via Selection. Berapa swap? Max n = 1jt swap. Berapa compare? n²/2 = 500 milyar. Compare dominan → swap saving gak kerasa untuk data biasa.

TL;DR: Selection Sort = pilih min dari sisa, swap ke posisi tepat. Selalu O(n²), tidak adaptive. Cuma menarik kalau swap operation mahal.