My first Magazine pemrograman-kompetitif-dasar | Page 57

5.2 Studi Kasus 1: Merge Sort
5.2.3
Implementasi Merge Sort
Algoritma 21 adalah implementasi dari prosedur utama merge sort . Prosedur ini akan
mengurutkan array dari indeks le f t hingga right. Prosedur ini secara rekursif akan melakukan
proses divide. Jika kita memiliki array dengan panjang N, maka awalnya kita akan memanggil
MERGE S ORT (arr, 1, N).
Algoritma 21 Algoritma merge sort .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
procedure MERGE S ORT (arr, le f t, right)
if le f t = right then
return
else
mid ← (le f t + right) div 2
MERGE S ORT (arr, le f t, mid)
MERGE S ORT (arr, mid + 1, right)
MERGE (arr, le f t, mid, mid + 1, right)
end if
end procedure
. Tinggal 1 elemen, sudah pasti terurut
Perhatikan bahwa prosedur MERGE S ORT pada Algoritma 21 memanggil prosedur MERGE .
Prosedur ini akan menggabungkan dua array yang terurut. Namun secara implementasinya, kita
hanya menggunakan satu buah array saja. kedua subarray kita bedakan berdasarkan indeksnya,
yang mana array pertama memiliki indeks arr[aLe f t..aRight] sementara array kedua memiliki
indeks arr[bLe f t..bRight]. Prosedur ini akan membuat array arr[aLe f t..bRight] menjadi terurut.
Prosedur ini dapat dilihat pada Algoritma 22.
Algoritma 22 Algoritma untuk menggabungkan 2 array yang terurut.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
procedure MERGE (arr, aLe f t, aRight, bLe f t, bRight)
size ← bRight − aLe f t + 1
. Hitung banyaknya elemen hasil gabungan
temp ← new integer[size]
. Buat array sementara
tIndex ← 0
aIndex ← aLe f t
bIndex ← bLe f t
. Selama kedua subarray masih ada isinya, ambil yang terkecil dan isi ke temp
while (aIndex ≤ aRight) ∧ (bIndex ≤ bRight) do
if arr[aIndex] ≤ arr[bIndex] then
temp[tIndex] ← arr[aIndex]
aIndex ← aIndex + 1
else
temp[tIndex] ← arr[bIndex]
bIndex ← bIndex + 1
end if
tIndex ← tIndex + 1
end while
47