Pengurutan cepat
Memilih satu nilai, yaitu pivot, lalu memindahkan nilai yang lebih kecil ke kirinya dan yang lebih besar ke kanannya. Lalu hal yang sama dilakukan di tiap sisi.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- tidak
- ya
Kasus terbaik: bagaimana waktu tumbuh seiring ukuran daftar n saat input paling mudah bagi algoritma ini.
Rata-rata: pertumbuhan waktu biasa terhadap n. Pada n², jumlah nilai 2 kali lipat butuh sekitar 4 kali waktu; n log n jauh lebih lambat.
Kasus terburuk: pertumbuhan pada input tersulit. Berguna saat kecepatan tidak boleh turun.
Memori: berapa memori tambahan yang dibutuhkan selain daftar. 1 berarti beberapa variabel, n berarti salinan daftar.
Stabil: dua nilai yang sama tetap dalam urutan aslinya. Penting saat mengurutkan data menurut satu kolom.
Tanpa memori tambahan: mengurutkan di dalam daftar itu sendiri, tanpa daftar kedua.
- dibandingkan
- dipindahkan
- pivot
- di posisi akhir
Kedalaman rekursi: 0 · paling kecil yang mungkin: 4 · terburuk: 23 menunggu pivotnya
Tekan putar: garis menunjukkan pertumbuhan biaya selama pengurutan
Tekan putar atau jalankan langkah demi langkah.
Spasi: putar atau jeda. Panah kiri dan kanan: melangkah. Home dan End: lompat.
Coba ini: Pilih daftar terbalik. Pivot selalu nilai terkecil atau terbesar yang tersisa, jadi satu sisi kosong dan biaya naik mendekati n².
Cara kerjanya
Di sini pivot adalah nilai terakhir dalam rentang. Dari kiri ke kanan, setiap nilai yang tidak lebih besar dari pivot ditukar ke sisi kiri. Lalu pivot diletakkan di antara kedua sisi, dan di situ ia tinggal seterusnya. Tiap sisi kemudian diurutkan dengan cara yang sama.
Kapan ini pilihan yang tepat
Salah satu cara mengurutkan tercepat dalam praktik, dan hampir tidak butuh memori tambahan. Tapi jika terus memilih pivot yang buruk, misalnya pada daftar yang sudah terurut, ia jadi lambat. Versi sungguhan memilih pivot dengan lebih hati-hati.