My first Magazine pemrograman-kompetitif-dasar | Page 64

5 Divide and Conquer
Kasus Terburuk
Kasus paling buruk: ukuran hasil partisi sangat timpang. Hal ini terjadi ketika partisi membagi
array berukuran N menjadi dua subarray yang masing-masing berukuran N − 1 dan 1. Dalam
kasus ini, kedalaman rekursif menjadi mendekati N yang mengakibatkan kompleksitas total
quicksort menjadi O(N 2 ).
Gambar 5.33: Contoh hasil partisi untuk kasus terburuk.
Namun tidak perlu khawatir karena dalam kondisi normal, peluang terjadinya kasus terburuk
sangat kecil. Artinya, pada sebagian besar kasus, quicksort berjalan dengan sangat cepat.
5.3.3
Pemilihan Pivot
Terdapat beberapa strategi pemilihan pivot untuk mencegah hasil partisi yang terlalu
timpang:
• Pilih salah satu elemen secara acak, ketimbang selalu memilih elemen di tengah.
• Pilih median dari elemen paling depan, tengah, dan paling belakang.
Quicksort memiliki sifat tidak stable. Artinya jika dua elemen a 1 dan a 2 memenuhi:
• memiliki yang nilai sama, dan
• sebelum diurutkan a 1 terletak sebelum a 2 ,
maka setelah diurutkan, tidak dijamin a 1 akan tetap terletak sebelum a 2 .
5.4
Studi Kasus 3: Mencari Nilai Terbesar
Perhatikan contoh soal Nilai Terbesar berikut.
Contoh Soal 5.1: Nilai Terbesar
Diberikan sebuah array A yang memiliki N bilangan, carilah nilai terbesar yang ada pada A!
Masalah ini dapat diselesaikan dengan mudah menggunakan perulangan biasa. Namun,
sekarang mari kita coba selesaikan dengan divide and conquer .
54