My first Magazine pemrograman-kompetitif-dasar | Page 63

5.3 Studi Kasus 2: Quicksort
15:
16:
17:
18:
19:
20:
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
. Sampai saat ini, dipastikan pRight < pLe f t
QUICKSORT (le f t, pRight)
23:
QUICKSORT (pLe f t, right)
24:
end if
25: end procedure
21:
22:
Analisis Algoritma Quicksort
Pada setiap kedalaman rekursi, array hasil partisi belum tentu memiliki ukuran yang sama.
Hasil partisi bergantung pada nilai pivot yang kita pilih. Karena hal ini, kita dapat menganalisis
kompleksitas quicksort dalam 3 kasus:
Kasus Terbaik
Pembelahan menjadi dua subarray sama besar menjamin kedalaman rekursif sedangkal
mungkin. Sehingga untuk kasus terbaik, jalannya algoritma menjadi seperti merge sort dan
bekerja dalam O(N log N).
1
2
3
4
Gambar 5.31: Contoh hasil partisi untuk kasus terbaik.
Kasus Rata-Rata
Pada kebanyakan kasus, ukuran hasil partisi berbeda-beda. Secara rata-rata kompleksitas-
nya masih dapat dianggap O(N log N). 10
Gambar 5.32: Contoh hasil partisi untuk kasus rata-rata.
53