Breaking News

Penggabungan Data (Merging) Pada Algoritma Pemrograman


Tujuan :
  1. Agar mahasiswa dapat memahami proses penggabungan dua kumpulan data
  2. Mempraktikan penggabungan data dari dua buah data array integer

Merging
Merging


Teori Singkat :

Merging adalah proses penggabungan dua kumpulan data yang masing- masing dalam keadaan urut menjadi satu kumpulan data yang juga dalam keadaan urut . Akan dipelajari bagaimana melakukan merge pada dua buah larik/array (vektor)
Secara umu proses dapat dijelaskan sebagai berikut (untuk mempermudah pemahaman, digunakan dua buah vektor). Diasumsikan bahwa dua buah larik/array yang akan dimerge sudah dalam keadaan urut naik. Kedua buah vektor tersebut adalah sebagai berikut :

Vektor 1

  11     12      23    33     45      67      68      70      81      92

Vektor 2


  9     12      21    42     56      65      7

Secara singkat proses merging dapat dijelaskan sebagai berikut (untuk) ambil wlwmwnt pertama dari vektor 1 (V 1), dan Vektor 2 (V2) . Bandingkan kedua element ini. Jika V1 > V2, maka V2 dimasikan kevektor ketiga jika tidak, V1 dimasukkan kevektor ke tiga. 
Untuk vektor yang elementnya dimasukkan kevektor ketiga. Element berikutnya yang dibandingkan adalah element yang terletak pad subskrip berikutnya. Dalam contoh diatas (V1 = 11 dan V2 - 9) yang terjadi adalah V1 >V2 sehingga V2 dimasukkan ke vektor ketiga. Untuk perbandingan berikutnya, adalah V1 = 11 dan V2 = 12, Proses ini diulang terus sampai salah satu vektor habis dimasukkan terlebih dahulu kevektor ketiga. Hasil merging kedua vektor diatas adalah sebagai berikut (yang digaris bawah berasal dari vektor 2) 


 9
 11
 12
 12
 21
 23
33
 42
 45
56
 65
 67
 68
 70
 74
 81
 92


Algoritma melakukan merer terhadap dua vektor dijelaskan dibawah ini dengan mengasumsikan bahwa keadaan urut naik.

Algoritma MERGING
Vektor yang akan dimerger sudah dalam Algoritma dibawah ini digunakan untuk merging dua buah vektor. Masukkan adalah dua buah vektor yang akan dimerge (vektor A dan Vektor B) yang sudah dalam keadaan urut naik, keluaran adalah vektor hasil merge, C.

Algoritma untuk masukan data dan pengurutan data dalam kedua vector dapat praktikan tambahkan untuk melengkapi algoritma ini.(diambil dari buku Struktur Data dengan Turbo Pascal 6.0, Andi Offset)
Langkah 0 
Baca kedua vektor yang akan di merge, vektor A dan vektor B, banyaknya elemen pada kedua vektor Ca dan Cb. Lakukan proses pengurutan secara urut naik pada kedua vektor ini.  

Langkah 1
(menentukan subskrip awalan) 
Tentukan, I = 1, j = 1, dan Cc = 0

Langkah 2
(proses merging berlangsung) 
Kerjakan langkah 3 dan 4 sampai (1>Ca) atau (J.Cb)

Langkah 3 
tentukan : Cc = Cc + 1 

Langkah 4
Tes apakah : A(I) <B(J)?
Jika ya, tentukan C(Cc) = A(I) dan I = I + 1
Jika tidak, tentukan C(Cc) = B(J), dan J =J+1;

Langkah 5
Tes apakah : I > Ca?
Jika ya , berarti semua element pada vektor sudah diproses semua, kerjakan langkah 6
Jika Tidak, berarti semua elemen pada vektor kedua sudah diproses semua , kerjakan langkah 7

Langkah 6
Untuk K = J sampai Cb, tentukan, Cc = Cc + 1, dan C (Cc) =
B(K), dan lompat kelangkah 8

Langkah 7

Untuk K = 1 sampai Ca, tentukan Cc = Cc +1 dan C(Cc) - A(K). 

Langkah 8
Selesai.


Soal Praktek :
  1. Susunlah flowchart program untuk merging tersebut
  2. Modifikasi flowchart program, agar vektor hasil merge berupa kumpulan data urut turun (petunjuk, daua vektor masukkan A dan B perlu diurutkan terlebih dahulu secara urut turun)

Soal Tugas :

Buatlah flowchart dan program C++ secara lengkap untuk proses merging mulai dari masukkan dua vektor yang susunan elemen masing- masing vektor masih acak. Kemudian dilakukan pengurutan dengan salah satu metode sorting yang anda kuasai, diteruskan proses merging sendiri dan menampilkan vektor hasil mergingnya. 

Terimakasih ^_^

No comments