Quick sort mengurutkan dengan memilih satu angka sebagai pivot (patokan), lalu memisahkan sisanya: yang lebih kecil dari pivot ke kiri, yang lebih besar ke kanan. Dua sisi itu lalu diurutkan dengan cara yang sama. Mirip menyusun barisan menurut tinggi badan: pilih satu orang, yang lebih pendek berdiri di kirinya, yang lebih tinggi di kanannya, lalu tiap kelompok diatur lagi dengan cara yang sama.
🧪 Tebakan cepat: setelah satu kali pemisahan, berapa angka yang pasti sudah ada di tempat akhirnya: satu, separuh, atau semua? Tebak dulu, jawabannya ada di bagian "Pilih pivot, pisahkan, ulangi".
Pilih pivot, pisahkan, ulangi
Ini yang terjadi pada [10, 7, 3, 9, 1, 5, 8], dengan angka terakhir sebagai pivot:
| Bagian | Pivot | Kiri (lebih kecil) | Kanan (lebih besar) |
|---|---|---|---|
[10, 7, 3, 9, 1, 5, 8] |
8 | [7, 3, 1, 5] |
[10, 9] |
[7, 3, 1, 5] |
5 | [3, 1] |
[7] |
[3, 1] |
1 | [] |
[3] |
[10, 9] |
9 | [] |
[10] |
Bagian berisi 0 atau 1 angka sudah terurut, itu base case-nya. Susun dari bawah: [1, 3], lalu [1, 3, 5, 7], lalu [1, 3, 5, 7, 8, 9, 10]. Jawaban tebakan: setelah satu pemisahan, cuma pivot yang pasti sudah di tempat akhirnya, karena semua yang lebih kecil ada di kirinya dan semua yang lebih besar di kanannya.
function quickSort(arr) {
if (arr.length <= 1) return arr; // base case
const pivot = arr[arr.length - 1]; // pivot: angka terakhir
const sisa = arr.slice(0, -1); // semua angka selain pivot
const left = sisa.filter(x => x < pivot); // lebih kecil
const right = sisa.filter(x => x >= pivot); // lebih besar atau sama
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([10, 7, 3, 9, 1, 5, 8]));
// [1, 3, 5, 7, 8, 9, 10]
arr.slice(0, -1)mengambil semua angka kecuali yang terakhir, yaitu pivotnya. Pivot harus dikeluarkan dulu supaya gak ikut terbagi lagi.filterbikin array baru berisi angka yang lolos syarat:leftdapat yang< pivot,rightdapat yang>= pivot. Angka yang sama dengan pivot harus ikut ke salah satu sisi, kalau gak, angka kembar hilang.[...quickSort(left), pivot, ...quickSort(right)]menyusun hasil: kiri yang sudah urut, pivot, lalu kanan yang sudah urut....menuang isi array ke array baru.- Pivot boleh angka mana saja. Kalau pakai yang pertama, pivotnya
arr[0]dan sisanyaarr.slice(1).
Versi di Lab: partisi di tempat
Kode di Lab gak bikin array baru. Function partition berjalan dari kiri ke kanan, dan tiap angka yang lebih kecil dari pivot ditukar ke deretan depan. Terakhir, pivot ditukar ke posisi tepat setelah deretan itu. [10, 7, 3, 9, 1, 5, 8] dengan pivot 8 jadi [7, 3, 1, 5, 8, 9, 10]: 7, 3, 1, 5 maju ke depan, dan 8 duduk di index 4, tempat akhirnya. Cara ini hemat memori, karena gak ada array tambahan selain catatan rekursinya.
Cepat, tapi ada kasus terburuk
Big-O bilang seberapa cepat kerja algoritma bertambah saat datanya bertambah. O(n) artinya datanya dua kali lipat, waktunya kira-kira dua kali lipat.
- Rata-rata O(n log n). Pivot biasanya membelah data kira-kira jadi dua, jadi cuma ada sekitar log n level, dan tiap level membandingkan n angka. 1.000 angka: sekitar 10.000 langkah.
- Terburuk O(n²). Kalau pivot selalu angka terkecil atau terbesar, misalnya data yang sudah terurut dengan pivot terakhir, tiap pemisahan cuma menyisihkan satu angka. 1.000 angka: sekitar 500.000 perbandingan.
- Obatnya: pilih pivot acak, atau angka di tengah. Di data terurut, pivot tengah membelah data jadi dua lagi.
Quick sort juga gak stabil: data yang nilainya sama bisa tertukar urutan aslinya.
⚠️ Jebakan yang sering ketemu
>di sisi kanan. Kalauleftpakai< pivotdanrightpakai> pivot, angka yang sama dengan pivot gak masuk ke mana pun.[3, 6, 8, 10, 1, 2, 1]jadi kehilangan satu angka 1.- Pivot gak dikeluarkan. Kalau
rightdiambil dariarr, bukan dari sisanya, pivot ikut masukrightlagi. Untuk data seperti[2, 2], rekursinya gak pernah selesai:Maximum call stack size exceeded. - Lupa
return. Tanpareturn, hasilquickSort(left)jadiundefined, dan...undefinedbikin error.
TL;DR: Quick sort memilih pivot, memisahkan angka yang lebih kecil ke kiri dan yang lebih besar atau sama ke kanan, lalu mengurutkan dua sisi itu dengan rekursi: [...quickSort(left), pivot, ...quickSort(right)]. Setelah satu pemisahan, pivot sudah di tempat akhirnya. Rata-rata O(n log n), tapi O(n²) kalau pivot selalu yang terkecil atau terbesar, seperti data terurut dengan pivot di ujung. Pakai pivot acak atau tengah. Quick sort gak stabil.
