Algoritma gabung
PseudocodeSuatu 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 MATLABM-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
AnalisisPada 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. PenggunaanPenggabungan dapat juga digunakan untuk berbagai hal:
Referensi
|
