Langsung ke konten utama

Implementasi Algoritma Merge Sort dengan Java

Algoritma  Merge Sort

Metode pengurutan merge sort adalah metode pengurutan lanjut, sama
dengan metode Quick Sort. Metode ini juga menggunakan konsep devide
and conquer yang membagi data S dalam dua kelompok yaitu S1 dan S2
yang tidak beririsan (disjoint). Proses pembagian data dilakukan secara
rekursif sampai data tidak dapat dibagi lagi atau dengan kata lain data
dalam sub bagian menjadi tunggal.

Setelah data tidak dapat dibagi lagi, proses penggabungan (merging)
dilakukan antara sub-sub bagian dengan memperhatikan urutan data yang
diinginkan (ascending/kecil ke besar atau descending/besar ke kecil).
Proses penggabungan ini dilakukan sampai semua data tergabung dan
terurut sesuai urutan yang diiginkan. Kompleksitas algoritma merge sort
adalah O(n log n).

Secara umum, algoritma merge sort dapat diimplementasikan secara
rekursif. Fungsi rekursif adalah sebuah fungsi yang didalam
implementasinya memanggil dirinya sendiri. Pemanggilan diri sendiri ini
berakhir jika kondisi tertentu terpenuhi (terminated condition is true).
Pada contoh berikut ini, terminated condition dari proses rekursif
mergesort akan berakhir jika data tidak dapat dibagi lagi (data tunggal
telah diperoleh). Dengan kata lain, proses pembagian data dilakukan terus
selama S.size > 1 (belum tunggal).

Ilustrasi dari algoritma merge sort adalah sebagai berikut:

Algoritma mergesort(S,C)
Input: n elemen dari data S dan comparator C
Output: data S terurut berdasarkan C

if S.size()>1
(S1,S2) ← partisi(S,n/2)
mergesort(S1,C)
mergesort(S2,C)
S ← merge(S1,S2)

Fungsi merge berfungsi untuk menggabungkan hasil pengurutan dari sub
bagian S1 dan S2 berdasarkan urutan tertentu (ascending atau descending
order). Kompleksitas proses penggabungan ini (merging) adalah O(n).
Algoritma dari proses penggabungan adalah:

Algoritma merge(S1,S2)
Input: data S1 dan S2 dengan n/2 elemen per data
Output: data terurut dari penggabungan S1 ∪ S2

S ← data kosong
while not S1.empty() and not S2.empty()
if S1.first().elemen() < S2.first().elemen()
S.insert(S1.remove(S1.first())
else
S.insert(S2.remove(S2.first())
while not S1.empty()
S.insert(S1.remove(S1.first())
while not S2.empty()
S.insert(S2.remove(S2.first())
return S

Flow cart beserta Aplikasi Merge sort berbasis Java Bisa di Unduh Disini

Label:

Komentar

Posting Komentar

Postingan populer dari blog ini

Contoh Perhitungan Algoritma Perceptron

      Melanjutkan tulisan saya sebelumnya tentang algoritma perceptron,kali ini saya akan menulis tentang conto perhitungan manual algoritma perceptron. Untuk contoh kasusnya saya menggunakan data logika AND. Cekidot.... Algoritma      Data yang kita gunakan sebagai contoh adalah data logika AND sebagai berikut: x1 x2 target 0 0 0 0 1 0 1 0 0 1 1 1       tentukan bobot awal secara acak, saya pakai contoh w1 = 0,w2 =0, learning rate = 1, bias = 0,maksimal epoh = 10. Disini saya memakai fungsi aktivasi undak biner. Epoh ke 1 Data ke satu x = {0,0}, bobot w = {0,0},b=0,target = 0 y_in = (x1*w1)+(x2*w2)+b = (0*0)+(0*0)+0 = 0 y = sign(0) = 1 karena y != target maka hitung error dan update bobot  error = target - y = 0 - 1 = -1 w1_baru = w1_lama +(learning_rate*error*x1)                = 0 ...
12 komentar
Baca selengkapnya

Contoh Perhitungan Algoritma Learning Vector Quantization

Melanjutkan tulisan saya tentang algoritma Learning Vector Quantization yang lalu, kali ini saya akan melanjutkan dengan contoh perhitungan manual. Berikut ini contoh data yang akan kita hitung. No X1 X2 X3 X4 target 1 0 1 1 0 0 2 0 0 1 1 1 3 1 1 1 1 0 4 1 0 0 1 1 pada contoh di atas, saya menggunakan 4 data sebagai data training beserta target yang bertujuan untuk mendapatkan bobot yang akan digunakan pada proses klasifikasi. Bobot awal adalah { 1, 1, 1, 0} dan { 1, 0, 1, 1} dengan learning rate 0,05 dengan fungsi pembelajaran = 0,1. Pelatihan Iterasi ke 1 1. Data ke 1 { 0, 1, 1, 0} dengan target 0, bobot = {{ 1, 1, 1, 0},{ 1, 0, 1, 1}}      - menghitung bobot untuk masing masing output :          kelas 0 = sqrt(((0-1)^2)+((1-1)^2)+((1-1)^2)+((0-...
39 komentar
Baca selengkapnya

Part 7 : Normalisasi Histogram

Menyambung tulisan saya yang sebelumnya tentang pengolahan citra khususnya histogram,kali ini saya lanjutkan tentang Normalisasi histogram.Sebelumnya saya harap agan sudah mengerti tentang histogram.Jika belum bisa di baca dulu di tulisan saya sebelumnya di sini . Normalisasi Histogram adalah menskalakan nilai piksel secara linear untuk menggunakan secara penuh jangkauan yang tersedia. Rumus :  Keterangan : n k= nilai grayscale dari piksel ke k(k = 0,1,2,3....) min = nilai grayscale terkecil yang diperoleh dari histogram max = nilai grayscale terbesar L = range nilai grayscale citra Contoh perhitungan : dari tabel di atas,nilai min adalah 2 yaitu nilai grayscale terkecil dari citra dan max adalah 5 s = 0 - 2 /5 - 2 =0 (untuk n = 0)  hasil = 0 x 7(nilai maksimal grayscale) = 0 sk = 3 - 2 /5 - 2 = 0.333  (untuk n = 3) hasil = 0.333 x 7 = 2 keterangan : 7 adalah range grayscale dari citra,dan untuk banyak kasus biasanya memakai 255. Tujuan Normalisasi...
1 komentar
Baca selengkapnya