My first Magazine pemrograman-kompetitif-dasar | Page 58

5 Divide and Conquer
. Masukkan subarray yang masih bersisa ke temp
. Hanya salah satu dari kedua while ini yang akan dieksekusi
while (aIndex ≤ aRight) do
temp[tIndex] ← arr[aIndex]
aIndex ← aIndex + 1
tIndex ← tIndex + 1
end while
while (bIndex ≤ bRight) do
temp[tIndex] ← arr[bIndex]
bIndex ← bIndex + 1
tIndex ← tIndex + 1
end while
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
. Salin isi array temp ke arr
for i ← 0, size − 1 do
32:
arr[aLe f t + i] ← temp[i]
33:
end for
34: end procedure
30:
31:
. Selesai, kini arr[aLe f t..bRight] telah terurut
Analisis Algoritma Merge Sort
Misalkan N adalah ukuran dari array . Dengan proses membagi array menjadi dua array
sama besar secara terus-menerus, banyak kedalaman rekursif dari merge sort adalah O(log N).
Untuk setiap kedalaman, dilakukan divide dan combine.
Proses divide dan conquer bekerja dalam O(1). Sedangkan proses combine melakukan
operasi sebanyak elemen hasil penggabungan. Total elemen yang diproses di tiap kedalaman
adalah O(N).
1
2
3
4
Gambar 5.18: Visualisasi hasil pembagian di masing-masing kedalaman.
•
•
•
•
Pada kedalaman 1, proses combine bekerja dalam O(2 × N/2). Total N elemen diproses.
Pada kedalaman 2, proses combine bekerja dalam O(4 × N/4). Total N elemen diproses.
Pada kedalaman 3, proses combine bekerja dalam O(8 × N/8). Total N elemen diproses.
... dan seterusnya
Dengan O(log N) menyatakan banyaknya kedalaman dan dibutuhkan operasi sebanyak O(N)
pada tiap kedalaman, total kompleksitas dari merge sort adalah O(N log N).
Bisa dibandingkan bahwa algoritma pengurutan menggunakan merge sort jauh lebih cepat da-
ri algoritma pengurutan O(N 2 ) seperti bubble sort . Karena itu, merge sort mampu mengurutkan
array dengan ratusan ribu elemen dalam waktu singkat.
Merge sort memiliki sifat stable . Artinya jika ada dua elemen a 1 dan a 2 yang bernilai sama
(a 1 = a 2 ) dan pada awalnya a 1 terletak sebelum a 2 , maka setelah diurutkan dijamin a 1 akan tetap
48