My first Magazine pemrograman-kompetitif-dasar | Page 62

5 Divide and Conquer
Implementasi Partisi Hoare
Implementasi partisi Hoare terdapat di Algoritma 23.
Algoritma 23 Implementasi partisi Hoare.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
procedure PARTITION (arr, le f t, right, pivot)
pLe f t ← le f t
pRight ← right
while pLe f t ≤ pRight do
while arr[pLe f t] ≤ pivot do
pLe f t ← pLe f t + 1
end while
while arr[pRight] > pivot do
pRight ← pRight − 1
end while
if pLe f t ≤ pRight then
SWAP (arr[pLe f t], arr[pRight])
pLe f t ← pLe f t + 1
pRight ← pRight − 1
end if
end while
end procedure
Analisis Algoritma Partisi Hoare
Terdapat dua variabel penunjuk, yang setiap langkahnya selalu bergerak ke satu arah tanpa
pernah mundur. Algoritma berhenti ketika variabel kiri dan kanan bertemu. Artinya, setiap elemen
array dikunjungi tepat satu kali. Kompleksitasnya adalah O(N).
5.3.2
Implementasi Quicksort
Setelah kita mengimplementasikan algoritma partisi, mengintegrasikannya ke quicksort
cukup mudah. Implementasinya terdapat di Algoritma 24.
Algoritma 24 Implementasi quicksort .
procedure QUICKSORT (arr, le f t, right)
if le f t ≥ right then
3:
return
4:
else
5:
pivot ← arr[(le f t + right) div 2]
1:
2:
6:
7:
8:
9:
10:
11:
12:
13:
14:
52
pLe f t ← le f t
pRight ← right
while pLe f t ≤ pRight do
while arr[pLe f t] ≤ pivot do
pLe f t ← pLe f t + 1
end while
while arr[pRight] > pivot do
pRight ← pRight − 1
end while
. Tidak ada elemen yang perlu diurutkan