Tugas algoritma: Merge Sort Revisited

Tugas Algoritma dan Struktur Data

Merge Sort Revisited

OLEH :

RASMIATI ASWA (H12111287)

PRODI STATISTIKA JURUSAN MATEMATIKA

FAKULRAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS HASANUDDIN  MAKASSAR 2012

Merge sort 

Merge sort merupakan algoritma pengurutan yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar.

Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort :

1.       Divide

  Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2.         Conquer

Conquer setiap bagian dengan memanggil prosedur merge sort secara      rekursif.

  3.   Kombinasi

Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan    rangkaian data berurutan.

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Contoh:

Inputan datanya adalah sebagai berikut:

7

2

6

5

Membagi rangkaian menjadi dua bagian:

7

2

6

5

Kedua bagian tersebut bisa dinamai LeftArr dan RightArr

Membagi LeftArr menjadi dua bagian:

7

2

Membandingkannya kemudian dikombinasikan:

2

7

7 dan 2 kemudian tukar posisi karena 2 < 7

Membagi RightArr menjadi dua bagian:

6

5

Membandingkannya kemudian dikombinasikan:

5

6

6 dan 5 kemudian tukar posisi karena  5 < 6

Membandingkan LeftArr dan RightArr.

2

7

5

6

Kemudian dilakukan proses membandingkan lagi antara angka di LeftArr dengan RightArr.

Pembandingan biasanya dimulai dari angka terdepan di masing-masing bagian.

Mengkombinasikan LeftArr dengan RightArr.

2

5

6

7

Sehingga menjadi: 2<5<6<7

Berikut ini contoh program dalam pascal

program MergeSort;
uses crt;
type arr = array [1..100] of integer;

var
ArrMain,ArrUrut : arr;
n,m : integer;
function merge(Left:arr; pjgL:integer; Right : arr; pjgR:integer) :arr;
var
i,j,k,m,panjang: integer;
hasil : arr;
begin
i:=1;
j:=1;
k:=1;
panjang:=pjgL+pjgR;
while ((pjgL>0) and (pjgR>0)) do
begin
if(Left[i]<= Right[j]) then
begin
hasil[k]:=Left[i];
i:=i+1;
k:=k+1;
pjgL:=pjgL-1;
end
else
begin
hasil[k]:=Right[j];
j:=j+1;
k:=k+1;
pjgR:=pjgR-1;
end;
end;
while (pjgL>0) do
begin
hasil[k]:=Left[i];
i:=i+1;
k:=k+1;
pjgL:=pjgL-1;
end;
while (pjgR>0) do
begin
hasil[k]:=Right[j];
j:=j+1;
k:=k+1;
pjgR:=pjgR-1;
end;
merge:=hasil;
for m:= 1 to panjang do
writeln('Array Hasil ke-',m,' : ',hasil[m]);
end;

function mergesort(pjg:integer;A : arr):arr;
var
middle,i,pjgLeft,pjgRight : integer;
ArrLeft,ArrRight,ArrHasil : arr;
begin
if pjg <= 1 then
mergesort := A
else
begin
middle := pjg div 2;
for i:=1 to middle do
ArrLeft[i]:=A[i];

for i:=(middle+1) to pjg do
ArrRight[i-middle]:=A[i];
pjgLeft := pjg div 2;
pjgRight := (pjg+1) div 2;
for m:= 1 to pjgLeft do
writeln('ArrayLeft ke-',m,' : ',ArrLeft[m]);
for m:= 1 to pjgRight do
writeln('ArrayRight ke-',m,' : ',ArrRight[m]);
ArrLeft:=mergesort(pjgLeft,ArrLeft);
ArrRight:=mergesort(pjgRight,ArrRight);
mergesort:=merge(ArrLeft,pjgLeft,ArrRight,pjgRight);
end;
end;

begin
clrscr;
write('Jumlah array : ');readln(n);
for m := 1 to n do
begin
write('Array ke-',m,' : ');
readln(ArrMain[m]);
end;
writeln;
ArrUrut := mergesort(n,ArrMain);

for m:= 1 to n do
writeln('Array Urut ke-',m,' : ',ArrUrut[m]);
end.

Rekurensi

·        Kompleksitas algoritma sering dinyatakan dalam bentuk persamaan rekurensi yang melibatkan fungsi asimptotis. Bentuk ini sebenarnya mewakili bentuk rekursif dari suatu program.

·        Misalnya suatu progam “merge-sort” dinyatakan sbb:

T(n)  =   Q(1)                           bila n=1

                   =   2 T(n/2) + Q(n)    bila n > 1

Ada 3 cara menyelesaikan rekurensi: subsitusi, iterasi, dan  master

Metoda Subsitusi:

Contoh: buktikan T(n) = 2T(ën/2û + n adalah O(n lg n).

·        Untuk suatu nilai c harus dibuktikan bahwa: T(n) £ c.n lg n,  subsitusi n dengan n/2,

     maka T(n/2) £ c.[n/2] lg [n/2], tentu saja

          T(n) £ 2 (c. [n/2] lg [n/2] ) + n

          T(n) £ c.n lg [n/2] + n

          T(n) = c.n lg n – c.n.lg 2 + n

          T(n) = c.n lg n – c.n + n

          T(n) £ c.n lg n

          atau T(n) adalah O(n lg n)

Metoda Iterasi:

Selesaikan  T(n) = 3 T(ën/4û) + n

·        T(n) = n + 3 T(ën/4û)

·        T(n) = n + 3 (ën/4û + 3 T(ën/16û))

·        T(n) = n + 3 (ën/4û + 3 T(ën/16 û + 3 T(ën/64û)))

·        T(n) = n + 3 ën/4û  + 9 ën/16û + 27 T(ën/64û) dst

·        T(n) £ n+3n/4 + 9n/16 + 27n/64 + ... + 3^{log4 n} Q(1)

          £  n S^¥ (3/4)ⁱ   +  Q(n^{log4 3})

                         =  4n + o(n)  =  O(n)

Note: suku ke-i adalah 3ⁱ ën/4ⁱû, habis ketika ën/4ⁱû=1 atau i > log4 n.

Metoda Master:

·        Bentuk umum :  T(n) = a T(n/b) + f(n)

·        Theorema: Bila a³1 dan b>1 adalah tetapan dan f(n) adalah suatu fungsi, kemudian andaikan T(n) didefinisikan pada bilangan bulat positif melalui rekurensi: T(n) =  a T(n/b) + f(n), dimana n/b bisa dinyatakan sebagai ën/bû atau én/bù maka T(n) dapat dibatasi secara asimptotik, sebagai berikut:

·        Bila f(n) = O(n^{logb a - e}), dimana e>0 tetapan, maka T(n) = Q(n^{logb a})

·        Bila f(n) = Q(n^{logb a}), maka T(n) = Q(n^{logb a} lg n)

·        Bila f(n) = W(n^{logb a + e}), dimana e>0 tetapan, dan bila a.f(n/b) £ c.f(n) dengan konstanta c < 1, dan n cukup besar, maka T(n) = Q(f(n)).

·        Contoh: selesaikan T(n) = 9 T(n/3) + n

·        Pada bentuk ini: a = 9, b=3, dan f(n) = n, sehingga dapat diterapkan kasus 1 sehingga T(n) = Q(n^{logb a}) = Q(n^{log3 9}) = Q(n²). Perlu diperhatikan bahwa f(n)=O(n^{log3 9 - e}) dengan e=1.

·        Selesaikan T(n) =  T(2n/3) + 1.

·        Pada bentuk ini: a=1, b=3/2, dan f(n)=1, sehingga n^{logb a} = n^{log3/2 1} = n⁰ = 1 dengan demikian dapat diterapkan kasus 2, karena f(n)=Q(nlogb a) = Q(1), jadi solusinya adalah: T(n) = Q(lg n)