Creator Media

Kompleksitas suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk mendapatkan hasil yang diinginkan. Efisiensi algoritma Quick Sort sangat dipengaruhi oleh pemilihan elemen pivot. Pemilihan pivot akan menentukan jumlah dan besar partisi pada setiap tahap rekursif. Kasus terbaik (best case) terjadi bila pivot berada pada elemen tengah dan n adalah 2k dimana k=konstanta, sehingga kedua tabel akan selalu berukuran sama setiap pemartisian.

Kebutuhan waktu dari quicksort bergantung pada pembuatan partisi, seimbang atau tidak, yang bergantung juga pada elemen yang digunakan sebagai poros. Dalam menghitung kompleksitas ini, perlu dilihat pula perhitungan recurrence, karena terdapat fungsi rekursif untuk penyelesaian sub-masalah.

Terdapat 3 kemungkinan kasus dari performa algoritma quick sort ini yaitu terbaik (best case), terburuk (worst case), dan rata-rata (average case).

Kompleksitas Algoritma Quick Sort

1. 1. Kasus Terbaik (Best Case)

      Kasus terbaik terjadi bila pivot adalah elemen median sedemikian sehingga kedua upa-tabel berukuran relatif sama setiap kali pempartisian. Menentukan median tabel adalah persoalan tersendiri, sebab kita harus menentukan median dari tabel yang belum terurut.

   2. Kasus Terburuk (Worst Case)

      Kasus ini terjadi bila pada setiap partisi pivot selalu elemen masksimum (atau elemen minimum) tabel. Hal ini menyebabkan pembagian menghasilkan upatabel kiri (atau kanan) berukuran satu elemen dan upatabel kanan (atau kiri) berukuran n – 1 elemen.

   3. Kasus Rata-Rata

      Kasus ini terjadi jika pivot dipilih secara acak dari elemen tabel, dan peluang setiap elemen dipilih menjadi pivot adalah sama. Kompleksitas waktunya adalah Tavg(n) = O(n 2 log n). Pembuktiannya lebih rumit.

Algoritma Quick Sort dapat kita ketahui sebagai algoritma yang handal dalam melakukan pengurutannya dari besarnya waktu asimptotik yang diperlukan apabila diberikan n buah masukan. Dimana kompleksitas algoritma dari algoritma ini memiliki 3 kasus yaitu O(n 2 log n) untuk kasus terbaik, O(n 2 ) untuk kasus terburuk, dan O(n 2 log n) untuk kasus rata-rata. Kompleksitas tersebut dipengaruhi karena pemilihan pivot. Oleh karena itu proses pemilihan pivot perlu dipertimbangkan. Pivot yang terkadang digunakan yaitu elemen tengah dari tabel yang akan diurut.

Pembahasan lainnya :

• • Pengertian Algoritma Quick Sort
  • Rangkuman Algoritma Divide and Conquer
  • Cara Memilih Pivot dalam Algoritma Quick Sort