My first Magazine pemrograman-kompetitif-dasar | Page 59

5.3 Studi Kasus 2: Quicksort
terletak sebelum a 2 .
5.3
Studi Kasus 2: Quicksort
Terdapat algoritma pengurutan selain merge sort yang memiliki kompleksitas O(N log N),
salah satunya adalah quicksort . Quicksort menggunakan prinsip divide and conquer dalam
pengurutannya. Tahapan dari quicksort adalah sebagai berikut:
1. Divide : pilih suatu elemen yang kita sebut pivot, kemudian kita bagi array menjadi dua
sehingga salah satunya selalu ≤ pivot dan yang sisanya selalu > pivot . Kemudian, lakukan
quicksort pada masing-masing subarray tersebut.
2. Conquer : ketika array hanya memiliki satu elemen, array tersebut sudah terurut.
3. Combine : gabungkan subarray dengan menempelkan hasil quicksort bagian kiri dan kanan.
Kita ingin mengurutkan array [5, 2, 7, 6, 1, 8, 9, 3] secara menaik. Pilih salah satu elemen,
misalnya 5. Kita sebut elemen ini sebagai pivot (pijakan).
Kemudian pindahkan seluruh elemen yang lebih kecil sama dengan pivot (≤ 5) ke sebelah
kiri dari pivot , dan seluruh elemen yang lebih besar dari pivot (> 5) ke sebelah kanan dari pivot .
Urutan elemen-elemen di satu bagian (sebelah kiri pivot atau kanan pivot ) setelah pemindahan
tidaklah penting (boleh acak). Gambar 5.20 merupakan contoh hasil dari proses ini.
5 2 7 6 1 8 9 3
Gambar 5.19: Awal mula array .
2 1 3 5
7 6 8 9
Gambar 5.20: Hasil array setelah proses divide dengan pivot 5. Semua elemen yang berada di
sisi kiri memiliki nilai ≤ 5, sementara elemen pada sisi kanan memiliki nilai > 5.
Setelah didapatkan kedua array tersebut, lakukan quicksort serupa untuk bagian kiri dan
kanan secara rekursif. Base case dari rekursi ini adalah ketika array yang hendak diurutkan hanya
memiliki satu elemen. Dengan langkah tersebut, suatu ketika seluruh array akan menjadi terurut.
5.3.1
Partisi Quicksort
Bagian utama dari quicksort adalah proses partisi (bagian divide ). Sebelum melakukan
partisi, pilih satu elemen yang akan dijadikan pivot . Kemudian, lakukan partisi supaya seluruh
elemen yang ≤ pivot berada di sebelah kiri dari pivot , dan yang > pivot di sebelah kanannya.
Pemilihan elemen pivot dapat dilakukan secara bebas. Bahkan pemilihan pivot dengan cara
tertentu dapat mempengaruhi performa algoritma quicksort . Pilihan yang cukup sering dipakai
adalah menggunakan elemen di tengah array sebagai pivot .
Setelah elemen pivot ditentukan, bagaimana cara mempartisi array ? Kita bisa saja menggu-
nakan sebuah perulangan sebanyak O(N) dan menampung hasil partisi di suatu array sementara,
kemudian menempatkan kembali hasil partisi ke array sebenarnya. Namun cara ini agak mere-
potkan karena kita perlu membuat array sementara dan memindahkan isi dari array .
49