Quicksort

Quicksort adalah salah satu algoritma pengurutan yang paling banyak dipakai. Algoritma ini memilih pivot, membagi daftar menjadi nilai yang lebih kecil dari pivot dan sisanya, lalu mengurutkan kedua sisi dengan cara yang sama. Quicksort cepat dalam praktik dan tidak butuh daftar tambahan, tetapi seberapa cepat bergantung pada pivotnya.

Batang yang dipartisi di sekitar batang pivot: batang yang lebih kecil di satu sisi, yang lebih besar di sisi lain, dan pivot di antaranya
Batang yang dipartisi di sekitar batang pivot: batang yang lebih kecil di satu sisi, yang lebih besar di sisi lain, dan pivot di antaranya

Idenya

Pilih satu nilai sebagai pivot. Susun ulang daftar sehingga setiap nilai yang lebih kecil dari pivot berada sebelumnya dan nilai lainnya setelahnya. Penyusunan ulang itu disebut partisi, dan partisi menempatkan pivot tepat di posisinya dalam daftar terurut. Kedua sisi kini menjadi masalah yang terpisah: urutkan masing-masing dengan quicksort. Sisi yang berisi satu nilai atau kosong sudah terurut.

Partisi, langkah demi langkah

Aplikasi ini memakai partisi Lomuto. Pivot dipindahkan ke ujung bagian. Sebuah penanda mulai dari awal: semua nilai sebelum penanda lebih kecil dari pivot. Setiap nilai lainnya dibandingkan dengan pivot; jika lebih kecil, nilai itu ditukar ke penanda dan penanda maju satu tempat. Di akhir, pivot ditukar ke penanda. Ambil 5, 1, 4, 2, 8 dengan nilai terakhir sebagai pivot: keempat nilai lebih kecil dari 8, jadi 8 tetap di ujung. Bagian 5, 1, 4, 2 dipartisi di sekitar 2 sehingga menjadi 1, 2, 4, 5, dan 4, 5 di sekitar 5. Totalnya 8 perbandingan, 2 penukaran, dan 3 partisi.

Pivot yang baik dan buruk

Jika setiap pivot jatuh di tengah, setiap partisi akan membagi dua masalahnya, dan pengurutan butuh sekitar n log₂ n perbandingan. Pada daftar acak, pivot jarang sempurna tetapi biasanya cukup baik: untuk 40 nilai acak, aplikasi menghitung sekitar 190 perbandingan. Kasus terburuk terjadi saat pivot selalu nilai terkecil atau terbesar. Dengan nilai terakhir sebagai pivot, daftar yang sudah terurut atau terbalik mengalami persis hal itu: setiap partisi hanya menyingkirkan pivot, dan pengurutan butuh n(n − 1)/2 perbandingan, 780 untuk 40 nilai.

Memilih pivot

Pivot acak membuat kasus terburuk sangat kecil kemungkinannya untuk input apa pun, karena tidak ada urutan tertentu yang bisa mengecohnya. Median dari tiga, yaitu nilai tengah dari elemen pertama, tengah, dan terakhir, murah dihitung dan menangani daftar terurut maupun terbalik dengan baik. Coba keduanya pada daftar terurut di aplikasi, dan jumlah perbandingan turun dari 780 menjadi sekitar 150. Banyak nilai yang sama adalah masalah lain: semuanya jatuh di satu sisi pivot. Partisi tiga arah, yang menyimpan nilai yang sama dengan pivot di bagian tengah, mengatasi hal itu.

Sejarah dan penggunaan

Tony Hoare menemukan quicksort pada 1959 dan menerbitkannya pada 1961. Partisi buatannya memindai dari kedua ujung dan melakukan lebih sedikit penukaran; versi Lomuto yang lebih sederhana yang ditampilkan di sini menjadi populer lewat buku teks. Quicksort mengurutkan di tempat dan loop dalamnya sangat pendek, jadi biasanya lebih cepat dari merge sort dalam praktik, meskipun tidak stabil. Introsort, algoritma pengurutan di balik pustaka standar C++, menjalankan quicksort dan beralih ke heap sort jika partisinya terlalu tidak seimbang, sehingga kasus terburuknya tetap n log n.

Tony Hoare, yang menemukan pengurutan cepat pada 1959 dan menerbitkannya pada 1961.
Tony Hoare, yang menemukan pengurutan cepat pada 1959 dan menerbitkannya pada 1961.

Jelajahi

Buka aplikasi dan tekan Langkah. Bagian yang dipartisi diberi bayangan, pivot punya warna sendiri, dan garis putus-putus menandai akhir bagian kiri, yaitu nilai yang lebih kecil dari pivot. Setiap pivot berubah hijau saat mencapai tempat akhirnya. Pilih daftar terurut dan nilai terakhir sebagai pivot, lalu beralih ke median dari tiga, dan bandingkan penghitungnya.

Pertanyaan yang sering diajukan

Berapa kompleksitas waktu quicksort?

O(n log n) rata-rata dan dengan pivot yang baik, O(n²) pada kasus terburuk. Quicksort mengurutkan di tempat; rekursinya butuh memori tambahan O(log n) jika sisi yang lebih kecil diurutkan lebih dulu.

Apa perbedaan partisi Lomuto dan Hoare?

Lomuto memakai satu penanda dan memindai dari kiri ke kanan, mudah diikuti, dan itulah yang ditampilkan aplikasi ini. Hoare memindai dari kedua ujung saling mendekat dan menukar pasangan yang berada di sisi yang salah, sehingga rata-rata penukarannya sekitar tiga kali lebih sedikit.

Mengapa quicksort lambat jika banyak nilai yang sama?

Nilai yang sama dengan pivot semuanya masuk ke sisi yang sama, sehingga daftar dengan sedikit nilai berbeda terbagi tidak seimbang, dan daftar yang semua nilainya sama seburuk kasus terburuk. Partisi tiga arah yang mengumpulkan nilai yang sama dengan pivot di tengah menghindari hal itu.

Apakah quicksort stabil?

Tidak. Penukaran selama partisi memindahkan nilai dalam jarak jauh, sehingga nilai yang sama bisa berubah urutan.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba quicksort