Merge Sort
Merge sort, seperti namanya, merupakan algoritma yang dirancang untuk
melakukan pengurutan terhadap sekumpulan bilangan. Ide utama dari merge
sort sama dengan algoritma perhitungan total yang telah kita lakukan
sebelumnya, yaitu membagi-bagikan keseluruhan list menjadi komponen
kecil, dan kemudian mengurutkan komponen tersebut dan menggabungkannya
kembali menjadi sebuah list besar.
Berikut adalah merge sort yang diimplementasikan dalam bahasa
python:def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)
def merge(left, right):
result = []
while len(left) > 0 or len(right) > 0:
if len(left) > 0 and len(right) > 0:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
elif len(left) > 0:
result.append(left.pop(0))
elif len(right) > 0:
result.append(right.pop(0))
return result
Dari kode di atas terlihat bahwa merge sort memiliki dua bagian, yang dituliskan dalam dua buah fungsi:
merge dan merge_sort. Fungsi merge_sort
memiliki logika dan cara kerja yang sama dengan fungsi penjumlahan
total yang kita bangun sebelumnya, dengan perbedaan pada bagian yang
melakukan penggabungan list (return merge(left, right)).
Penggabungan list sendiri dilakukan dengan cukup sederhana dan
gamblang, yaitu hanya membandingkan elemen-elemen dari dua buah list
yang dikirimkan satu per satu, untuk kemudian disimpan ke dalam variabel
result secara terurut. Untuk lebih jelasnya, mari kita coba bedah algoritma pada fungsi merge, langkah demi langkah.
Misalkan kita memanggil fungsi merge seperti berikut:
left = [3, 5]
right = [1, 4]
merge(left, right)
Note
Ingat bahwa list pada variabel > 1 hanya dipanggil dari hasil
left maupun right harus sudah terurut jika ukuran list lebih dari 1. Fungsi merge dengan argumen list berukuran merge dua buah list berukuran satu dalam kasus merge_sort.
Jika kita mengikuti langkah demi langkah pada kode, maka pada setiap iterasi
while kita akan mendapatkan nilai masing-masing variabel sebagai berikut:# Awal fungsi
left = [3, 5]
right = [1, 4]
result = []
# Iterasi 1
left = [3, 5]
right = [4]
result = [1]
# Iterasi 2
left = [5]
right = [4]
result = [1, 3]
# Iterasi 3
left = [5]
right = []
result = [1, 3, 4]
# Iterasi 4
left = []
right = []
result = [1, 3, 4, 5]
Penggabungan seperti di atas dilakukan pada setiap submasalah yang telah dipecah oleh
merge_sort,
sampai kita mendapatkan sebuah list dengan ukuran yang sama pada list
awal. Untuk mempermudah pengertian, gambar di bawah menunjukkan proses
pemecahan dan penggabungan kembali dari merge sort:
Langkah Kerja Merge Sort
Proses divide terjadi ketika kotak dan panah berwarna merah,
sementara conquer dan combine terjadi ketika kotak dan panah diberi
warna biru. Proses conquer merupakan proses di mana kita mengurutkan
elemen dalam list, dan combine adalah ketika kita menggabungkan hasil
urutan dari list tersebut.
Binary Search
Binary search merupakan salah satu algoritma pencarian yang paling efisien, dengan kompleksitasLangsung saja, implementasi binary search menggunakan
python:def binary_search(data, search_val, min_idx, max_idx):
if max_idx < min_idx:
print("%d not found in list"%search_val)
return -1
mid_idx = (min_idx + max_idx) // 2
if data[mid_idx] > search_val:
return binary_search(data, search_val, min_idx, mid_idx - 1)
elif data[mid_idx] < search_val:
return binary_search(data, search_val, mid_idx + 1, max_idx)
else:
print("%d found in index %d"%(search_val, mid_idx))
return mid_idx
[1, 2, 4, 6, 7, 8, 9, 10]
2
pada list tersebut. Sebelum mulai menjalankan algoritma, pastinya kita
harus mengetahui nilai-nilai awal terelbih dahulu. Adapun nilai awal
yang dibutuhkan untuk fungsi binary_search adalah sebagai berikut:data = [1, 2, 4, 6, 7, 8, 9, 10]
search_val = 2
min_idx = 0
max_idx = len(data) - 1 # 7
0,
dengan nilai maksimal (batas akhir pencarian) adalah ukuran dari list
itu sendiri. Di langkah awal binary search, dilakukan perhitungan
terhadap nilai tengah dari min_idx dan max_idx terlebih dahulu, untuk mendapatkan titik awal pencarian. Perhitungan nilai tengah dilakukan pada kode berikut:mid_idx = (min_idx + max_idx) // 2
data pada indeks tersebut lebih besar atau lebih kecil dibandingkan nilai yang akan kita cari (2). Langkah pengecekan ini dilakukan pada perintah if berikut:if data[mid_idx] > search_val:
# nilai lebih besar daripada 2
elif data[mid_idx] < search_val:
# nilai lebih kecil daripada 2
else:
# nilai adalah 2 (ditemukan)
mid_idx adalah 3, dan karena data[3] berisi 6, maka kita akan melakukan pemotongan terhadap seluruh nilai pada data setelah 6,
karena nilai tersebut sudah pasti tidak diperlukan lagi (ingat, data
harus terurut pada binary search). Kita lalu memanggil fungsi binary_search lagi, kali ini dengan mencari hanya pada submasalah (list) berikut (perhatikan bagaimana pada pemanggilan binary_search yang kedua nilai max_idx kita ubah menjadi mid_idx - 1):[1, 2, 4]
1. Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Misalkan tabel A berisi elemen-elemen sebagai berikut :
Ide dasar algoritma secara Divide and Conquer :
Algoritma MinMaks :
1. Untuk kasus n = 1 atau n = 2,
SOLVE : Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks.
2. Untuk kasus n > 2,
- DIVIDE : Bagi dua table A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.
- CONQUER : Terapkan algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan maks dari table bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari table bagian kanan dinyatakan dalam peubah min2 dan maks2.
- COMBINE : Bandingkan min1 dan min2 untuk menentukan min table A, serta bandingkan maks1 dan maks2 untuk menentukan maks table A.
