Quick Sort memilih satu elemen sebagai pivot, lalu mempartisi array: elemen lebih kecil di kiri, lebih besar di kanan.

Kompleksitas: O(n log n) average, O(n²) worst case (pivot selalu min/max)

Cara kerja:

1. Pilih pivot (biasanya elemen terakhir)
2. Partition — pindahkan semua < pivot ke kiri, > pivot ke kanan
3. Rekursif: quick sort kiri dan kanan

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIdx = partition(arr, low, high);
    quickSort(arr, low, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

quickSort([10, 7, 8, 9, 1, 5]);
// Pivot=5: [1, 5, 8, 9, 10, 7] → partition
// Kiri: [1] — sudah terurut
// Kanan: [8, 9, 10, 7] — quick sort lagi
// ... Hasil: [1, 5, 7, 8, 9, 10]

Kelebihan:

• In-place — O(log n) memori tambahan (stack rekursi)
• Secara praktis lebih cepat dari Merge Sort (cache-friendly)
• Algoritma sorting paling populer di production

Kekurangan:

• O(n²) worst case (mitigasi: random pivot)
• Tidak stabil

Tip: Pilih pivot secara random atau gunakan "median of three" untuk menghindari worst case.

🎭 Analogi sehari-hari: Sorting ulang tahun karyawan. Pilih satu karyawan random (pivot, misal "Budi lahir Mei"). Pisahin yang lahir sebelum Mei ke kiri, sesudah Mei ke kanan. Lalu rekursif sort kedua sisi pakai pivot baru. Itu Quick Sort.

💡 Mengapa Quick Sort lebih cepat dari Merge Sort di praktik? Sama-sama O(n log n), tapi:

• Quick: in-place (cuma swap) — gak boros memory allocation
• Quick: cache-friendly — operasi di partition yang berdekatan, CPU cache happy
• Merge: alocate sub-array baru tiap level → cache miss banyak

Untuk data biasa, Quick 2-3x lebih cepat walau Big O sama.

⚠️ Jebakan umum:

• Pivot = elemen pertama/terakhir + data sudah sorted → O(n²). Pakai random pivot atau median-of-three
• Tail recursion call stack untuk data 1jt = stack overflow. Pakai iteratif untuk partition besar
• Tidak stable — [3a, 1, 3b] bisa jadi [1, 3b, 3a]. Untuk stable, pakai Merge
• Partition ribet — Lomuto vs Hoare partition, gampang salah implementasi

🎯 Strategi pivot terbaik:

1. Random pivot — pasti aman dari adversarial input
2. Median-of-three — ambil 3 sample, pakai median sebagai pivot
3. Introspective sort (IntroSort) — Quick + fallback ke Heap kalau recursion terlalu dalam (C++ STL pakai ini)

🧪 Tebakan cepat: Quick Sort di array [1,2,3,4,5,6,7,8,9,10] (sorted) dengan pivot terakhir. Worst case O(n²) karena partition terus skewed. Ironi: data sorted = kasus terburuk untuk Quick naive.

TL;DR: Quick Sort = pilih pivot, partition kiri/kanan, rekursif. O(n log n) average, O(n²) worst. Paling cepat di praktik kalau pivot dipilih cerdas. Default sort di banyak language (dengan variant).