My first Magazine pemrograman-kompetitif-dasar | Page 60

5 Divide and Conquer
Partisi Hoare
Ada beberapa algoritma untuk melakukan partisi secara in place atau tanpa array sementara.
Kita akan membahas salah satu algoritma partisi yaitu algoritma partisi Hoare. Cara kerja
algoritma Hoare adalah sebagai berikut:
1. Pilih sebuah pivot .
2. Siapkan dua variabel penunjuk, kiri dan kanan dengan masing-masing variabel menunjuk
ujung kiri dan ujung kanan dari array .
3. Gerakkan variabel kiri ke arah kanan, sampai elemen yang ditunjuk > pivot.
4. Gerakkan variabel kanan ke arah kiri, sampai elemen yang ditunjuk ≤ pivot.
5. Jika kiri ≤ kanan, tukar elemen yang ditunjuk kiri dan kanan, kemudian gerakkan kiri ke
kanan satu langkah dan kanan ke kiri satu langkah.
6. Jika kiri ≤ kanan, maka kembali ke tahap 3. Jika tidak, selesai.
Mari kita terapkan algoritma tersebut. Asumsikan kita akan melakukan partisi pada suatu
array [2, 5, 7, 4, 6, 1, 3, 8, 9]. Misalkan kita memilih pivot = 5. Simak Gambar 5.21 hingga Gambar
5.30 yang mengilustrasikan algoritma Hoare dari awal hingga akhir.
2 5 7 4 6 1 3 8 9
^
^
kiri
kanan
Gambar 5.21: Langkah 1: Kita mulai dengan membuat dua variabel penunjuk, yaitu kiri dan kanan
dengan masing-masing variabel menunjuk ujung kiri dan ujung kanan dari array .
2 5 7 4 6 1 3 8 9
^
^
kiri
kanan
Gambar 5.22: Gerakkan variabel kiri ke arah kanan, sampai elemen yang ditunjuk > pivot.
2 5 7 4 6 1 3 8 9
^
^
kiri
kanan
Gambar 5.23: Gerakkan variabel kanan ke arah kiri, sampai elemen yang ditunjuk ≤ pivot.
2 5 7 4 6 1 3 8 9
^ kanan
^
kiri
Gambar 5.24: Karena kiri ≤ kanan, tukar elemen yang ditunjuk kiri dan kanan, lalu gerakkan kiri
ke kanan satu langkah serta kanan ke kiri satu langkah.
50