Implementasi Algoritma Divide and Conquer pada Sorting dan Searching
Nama : Berliana
NPM : 20312133
Kelas : IF 20E
Alamat Web Universitas : https://teknokrat.ac.id/
Alamat Web Fakultas : http://ftik.teknokrat.ac.id/
Pengertian Algoritma Divide
- Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.
- Algoritma Divide and Conquer adalah strategi pemecahan masalah yang besar dengan cara melakukan pembagian masalah yang besar tersebut menjadi beberapa bagian yang lebih kecil secara rekursif hingga masalah tersebut dapat dipecahkan secara langsung. Solusi yang didapat dari setiap bagian kemudian digabungkan untuk membentuk sebuah solusi yang utuh.
Definisi
• Divide: membagi persoalan menjadi beberapa upa-masalah yang memiliki kemiripan dengan persoalan semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
• Conquer (solve): menyelesaikan masing-masing upa-masalah (secara langsung atau secara rekursif).
• Combine: mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi persoalan semula.
Obyek persoalan yang dibagi : masukan (input) atau instances persoalan yang berukuran n seperti:
- tabel (larik),
- matriks,
- eksponen, dll
• Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal sehingga metode Divide and Conquer lebih natural diungkapkan dengan skema rekursif.
Langkah-langkah umum Algoritma Divide and Conquer :
- Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
- Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
- Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.
Algoritma Divide And Conquer ditemukan oleh seorang ilmuwan Rusiabernama Anatolii Alexeevich Karatsuba pada tahun 1960. Pada mulanya, Anatoliimenemukan algoritma yang lebih cepat untuk mengalikan dua buah bilangan bulatyang besar dengan kompleksitas O(nlog 3).
Algoritma Divide and Conquer memiliki kelebihan yang membuatnya banyak diterapkan dan digunakan dalam aplikasi-aplikasi dunia nyata, diantaranya :
- Mampu menyelesaikan masalah yang sulit, algoritma ini mampu menyelesaikan masalah rumit yang hingga kini masih cukup sulit dipecahkan oleh komputer biasa, seperti Tower of Hanoi Problem.
- Algoritma lebih efisien untuk beberapa kasus tertentu, misalnya kasus Fast Fourier Transform maupun Sorting dapat dilakukan dengan kompleksitas algoritma O(n log n) dari algoritma lainnya yang hanya mampu mencapai kompleksitas O (n2).
- Algoritma ini dapat bekerja secara paralel dan dapat memaksimalkan penggunaan dari cache memory.
Contoh algoritma devide and conquer adalah pada 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.
- Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer : Permasalahan convex hull adalah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition), dan penelitian operasi.
- Persoalan Minimum dan Maksimum ( MinMaks ), dan
- Optimasi Konversi Bilangan Desimal Ke Biner
- Mencari Pasangan titik yang jaraknya dekat (close pair)
untuk
menghitung total jumlah dari bilangan-bilangan yang ada di dalam sebuah list, dapat menggunakan perulangan sederhana:
nums = [1,
2, 3, 5, 6, 7, 19, 28, 58, 18, 28, 67, 13]
total = 0
for i in
range(0, len(nums)):
total = total + nums[i]
print(total)
# 255
Algoritma perulangan yang digunakan pada kode di atas memang sederhana dan memberikan hasil yang benar, tetapi terdapat beberapa masalah pada kode tersebut, yaitu perhitungan dilakukan secara linear, yang menghasilkan kompleksitas \(O(n)\). Hal ini tentunya cukup ideal untuk ukuran list kecil, tetapi jika ukuran list menjadi besar (beberapa Milyar elemen) maka perhitungan akan menjadi sangat lambat. nilai dari total tergantung kepada kalkulasi nilai total sebelumnya. tidak dapat melakukan perhitungan total dari depan dan belakang list sekaligus, sehingga kita dapat mempercepat perhitungan dua kali lipat.
Langkah pertama yang dapat kita lakukan adalah
menerapkan teknik rekursif untuk membagi-bagikan masalah menjadi masalah yang
lebih kecil. Jika awalnya kita harus menghitung total keseluruhan list satu per
satu, sekarang kita dapat melakukan perhitungan dengan memecah-mecah list
terlebih dahulu:
def
sums(lst):
if len(lst) >= 1:
return lst[0]
mid = len(lst) // 2
left = sums(lst[:mid])
right = sums(lst[mid:])
return left + right
print(sums(nums))
# 255
Baris if
len(lst) >= 1 memberikan syarat pemberhentian fungsi rekursif, yang akan
mengembalikan isi dari list ketika list berukuran 1 (hanya memiliki satu
elemen).
Baris mid =
len(lst) // 2 mengambil median dari list, sebagai referensi ketika kita membagi
list menjadi dua bagian.
Baris left
= sum(lst[:mid]) dan selanjutnya membagikan list menjadi dua bagian, dengan
nilai mid sebagai tengah dari list.
Singkatnya, setelah membagikan list menjadi dua bagian terus
menerus sampai bagian terkecilnya, kita menjumlahkan kedua nilai list tersebut,
seperti pada gambar berikut:
setiap
bagian rekursif (left = ... dan right = ...) ke satu unit kerja baru, yang
dikenal dengan nama thread. Mekanisme pada sistem operasi atau compiler
kemudian akan membagi-bagikan tugas pembagian dan perhitungan lanjutan agar
dapat dijalankan secara paralel, misalnya dengan membagikan tugas ke dalam
beberapa core prosesor, atau bahkan ke dalam mesin lain (jika terdapat sistem
dengan banyak mesin).
Dengan
membagi-bagikan pekerjaan ke dalam banyak unit, tentunya pekerjaan akan lebih
cepat selesai! Teknik memecah-mecah pekerjaan untuk kemudian dibagikan kepada
banyak pekerja ini dikenal dengan nama divide and conquer.
Contoh 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))
Contoh Binary Search:
Binary search merupakan salah satu algoritma pencarian yang
paling efisien, dengan kompleksitas \(O(\log n)\). Algoritma ini memanfaatkan
teknik divide and conquer dengan memecah lingkup pencarian data menjadi
setengahnya pada setiap kali divide. Kekurangan dari binary search yaitu bahwa
algoritma ini hanya dapat digunakan pada sebuah data atau lsit yang telah
terurut.
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
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)).
Skema Umum Algoritma Divide and Conquer
procedure DIVIDE_and_CONQUER(input n : integer)
{ Menyelesaikan masalah dengan algoritma D-and-C.
Masukan: masukan yang
berukuran n
Keluaran: solusi dari
masalah semula
}
Deklarasi
r, k : integer
Algoritma
if n n0 then
{ukuran masalah sudah cukup kecil }
SOLVE upa-masalah
yang berukuran n ini
else
Bagi menjadi r
upa-masalah, masing-masing berukuran n/r
for masing-masing
dari r upa-masalah do
DIVIDE_and_CONQUER(n/k)
endfor
COMBINE solusi dari r
upa-masalah menjadi solusi masalah semula }
endif
Komentar
Posting Komentar