Apa yang dimaksud pivot pada quicksort?

Apa Itu Pivot dalam Algoritma Quick Sort?

Quick sort adalah salah satu algoritma pengurutan yang paling populer karena kecepatannya dalam menangani data berukuran besar. Salah satu kunci dari kecepatan quick sort terletak pada pemilihan pivot. Tapi sebenarnya, apa itu pivot?

Secara sederhana, pivot adalah elemen yang dipilih dari daftar data yang akan diurutkan. Setelah dipilih, elemen-elemen lain kemudian dibandingkan dengannya. Data yang lebih kecil dari pivot ditempatkan di sebelah kiri, sementara yang lebih besar ditempatkan di sebelah kanan. Proses ini disebut partisi, dan dilakukan secara berulang pada setiap bagian hingga seluruh data terurut.

Namun, pemilihan pivot bukan hal sepele. Jika kita memilih pivot secara cerdas—misalnya, nilai tengah atau elemen acak—proses pengurutan bisa berjalan sangat cepat, bahkan dalam waktu n log n rata-rata. Sebaliknya, jika pivot selalu merupakan elemen terkecil atau terbesar (misalnya saat data sudah terurut), maka performa quick sort bisa menurun drastis menjadi O(n²), sama buruknya dengan algoritma pengurutan sederhana.

Banyak varian quick sort menggunakan strategi tertentu untuk menghindari kasus terburuk, seperti memilih pivot secara acak atau menggunakan median dari tiga elemen. Dengan begitu, algoritma tetap efisien meski data awalnya tidak ideal.

Jadi, meskipun terdengar sepele, peran pivot sangat menentukan. Ia bukan sekadar titik acuan, tapi jantung dari efisiensi quick sort. Pemilihan yang tepat bisa mengubah proses yang lambat menjadi sangat cepat—membuktikan bahwa dalam dunia algoritma, detail kecil bisa berdampak besar.