Creator Media

Algoritma quick sort diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960, dan dimuat sebagai artikel di “Computer Journal 5” pada April 1962. Quick sort adalah algoritma sorting yang berdasarkan pembandingan dengan metoda divide-and-conqueror. Disebut Quick Sort, karena Algoritma quick sort mengurutkan dengan sangat cepat. Dalam algoritma quick sort , pemilihan pivot adalah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :

Cara Memilih Pivot dalam Algoritma Quick Sort

1. 1. Pivot = elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel kana.
   2. Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan prosedur acak. Lagi pula, ita tidak mengurangi kompleksitas waktu algoritma.
   3. Pivot = elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang (masingmasing n/2 elemen). Cara ini memberkan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri.

Pembahasan lainnya :

• • Pengertian Algoritma Quick Sort
  • Kompleksitas Algoritma Quick Sort
  • Rangkuman Algoritma Divide and Conquer