Algoritma gabung

Algoritme gabung adalah algoritme yang dijalankan sebagai akibat dari terlalu banyaknya daftar yang diurutkan, dengan menghasilkan lebih banyak daftar yang diurutkan sebagai output. Algoritme gabung ini disesuaikan untuk mesin drive tape. Penggunaannya dalam akses memori acak besar yang terkait telah menurun, karena banyak aplikasi algoritme gabung yang mempunyai alternatif lebih cepat ketika kamu memiliki akses memori acak yang menjaga semua data mu. Hal ini disebabkan algoritme ini membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel.

Algoritme urut gabung membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritme urut gabung memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritme ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan.

Algoritme gabung umumnya memiliki satu set pointer p_0..n yang menunjuk suatu posisi di dalam satu set daftar L_0..n . Pada awalnya mereka menunjuk item yang pertama pada setiap daftar. Algoritmenya sebagai berikut:

Selama p_0..n masih menunjuk data yang di dalam sebagai pengganti pada akhirnya:

Melakukan sesuatu dengan data item yang menunjuk daftar mereka masing-masing.
Menemukan pointers points untuk item dengan kunci yang paling rendah; membantu salah satu pointer untuk item yang berikutnya dalam daftar.

Pseudocode

Suatu implementasi pseudocode sederhana yang tak berulang dari penggabungan dengan dua daftar yang mungkin tertulis sebagai berikut:

 function merge(a, b)
	var list result
	var int i, j := 0
	
	while (i < length(a)) and (j < length(b))
		if a[i] < b[j]
			add a[i] to result
                       i := i + 1
		else
			add b[j] to result
			j := j + 1

	while i < length(a)
		add a[i] to result
		i := i + 1
	while j < length(b)
		add b[j] to result
		j := j + 1
	
	return result

Implementasi algoritme gabung menggunakan MATLAB

M-File

 function p=merge(a,b)
 % MERGE Penggabungan
 % MERGE(A,B) menggabungkan dua list
 if nargin<2 
     error('Kekurangan argumen input');
 end % pengecekan error
    a=a(:); % meyakinkan bahwa input merupakan vektor baris
    b=b(:);
    na=length(a); % menemukan panjang a dan b
    nb=length(b);
    df=a+b; % hasil dari daftar
    ndf=length(df);
    p=[zeros(1,nb-na) a]+[zeros(1,na-nb) b];

Command window

  >> a=[1 2 3]
     a =
          1     2     3
  >> b=[2 3 4]
     b =
          2     3     4
  >> merge(a,b)
     ans =
          3
          5
          7
  >> p=[3 5 7]
     p =
          3     5     7
  >> for i=1:3
         x=a(i)+p(i)
     end
     x =
          4
     x =
          7
     x =
         10
  >> for j=1:3
         y=b(j)+p(j)
     end
     y =
         5
     y =
          8
     y =
         11

Analisis

Pada umumnya algoritme gabung berjalan dalam waktu proposional untuk penjumlahan pada panjangnya daftar; Algoritme gabung beroperasi pada bilangan besar dalam daftar yang akan segera mengalikan penjumlahan panjangnya daftar pada saat itu untuk keluaran gambar pointers points yang mana menunjuk pada item yang paling rendah, yang dapat terpengaruhi dengan suatu heap(tumpukan) yang didasarkan prioritas antrian dalam O(lg n) waktu, untuk O(m lg n) waktu (di mana n adalah bilangan pada daftar yang digabungkan, m adalah penjumlahan panjangnya daftar, dan lg adalah log basis 2). Ketika menggabungkan panjang m dua daftar, terdapat suatu perbandingan lompatan yang lebih rendah 2m-1 yang ada dalam kasus terburuk.

Keluaran data item Merge klasik (satu yang digunakan dalam urut gabung) dengan kunci yang paling rendah pada langkah masing-masing, memberikan beberapa daftar yang diurutkan, hasil daftar yang diurutkan berisi semua unsur-unsur di dalam daftar input manapun, dan hal itu dilakukan agar waktunya proporsioal untuk input penjumlahan panjangnya daftar.

Penggunaan

Penggabungan dapat juga digunakan untuk berbagai hal:

Diberikan satu set saldo-saldo rekening yang beredar dan satu set transaksi, kedua-duanya disortir oleh nomor rekening, menghasilkan satu saldo-saldo rekening baru setelah transaksi diterapkan; ini selalu diperlukan untuk mempercepat ”transaksi baru” penunjuk ketika keduanya mempunyai kunci yang sama, dan menambahkan semua angka-angka pada tape yang manapun dengan nomor rekening yang sama untuk menghasilkan saldo yang baru.
Menghasilkan suatu daftar catatan yang disortir dengan menyajikan kunci disemua daftar ini yang memerlukan outputting kapan saja suatu catatan yang semua kunci p_0..n adalah sama.
Dengan cara yang sama untuk menemukan bilangan besar pada satu tape yang lebih kecil dibandingkan masing-masing nomor pada satu tape yang lainnya (contoh untuk mengeluarkan gambar pengelompokan pajak masing-masing orang di dalamnya).
Dengan cara yang sama untuk menghitung perbedaan set semua arsip dalam satu daftar dengan arsip yang tidak sesuaian dengan yang lainnya.
Operasi penyisipan dalam mesin pencarian untuk menghasilkan suatu indeks balikkan.
Menggabungkan permainan-permainan adalah suatu peranan pusat dalam fungsi pemrograman teknik Dijkstra untuk menghasilkan bilangan-bilangan tetap.

Referensi

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997.ISBN 0-201-89685-0. Pages 158–160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp. 197–207.
Atrinawati, Lovinta Happy. Analisis Kompleksitas Algoritme Untuk Berbagai Macam Metode Pencarian Nilai (Searching) dan Pengurutan Nilai (Sorting) pada Tabel. Program Studi Teknik Informatika, Institut Teknologi Bandung.