11-12 algoritma divide and coquer.ppt - blognya maz wied · algoritma sorting • mengurutkan data...

7/5/2010

1

Algoritma Divide And Coquer

wijanarto

Definisi

• Divide: membagi masalah menjadi beberapa upa‐masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama)(idealnya berukuran hampir sama),

• Conquer: memecahkan (menyelesaikan) masing‐masing upa‐masalah (secara rekursif), dan

• Combine: mengabungkan solusi masing‐masing upa‐masalah sehingga membentuk solusi masalah semula.

Algoritmaprocedure DIVIDE_and_CONQUER(input n : integer){ Menyelesaikan masalah dengan algoritma D-and-C.Masukan: masukan yang berukuran nKeluaran: solusi dari masalah semula

}Deklarasi

r, k : integerAlgoritmaif n ≤ n0 then {ukuran masalah sudah cukup kecil }

SOLVE upa-masalah yang berukuran n inielse

Bagi menjadi r upa-masalah, masing-masing berukuran n/kfor masing-masing dari r upa-masalah do

DIVIDE_and_CONQUER(n/k)endforCOMBINE solusi dari r upa-masalah menjadi solusi masalah semula

}endif

Versi lain

Procedure DNC(p,q)

Global n,A(1:n);integer m,p,q

If small (p,q) then G(p,q) else

M devide(p,q)

Combine(dnc(p,m),dnc(m+1,q))

Diagram D N C

N input

N input I N input II N input kN input III

Sub prob I Sub prob II Sub prob kSub prob III

Sub solusi I Sub solusi II Sub solusi kSub solusi III

Sub solusi I

Diagram D N C

7/5/2010

2

Jika pembagian secara biner

procedure DIVIDE_and_CONQUER(input n : integer){ Menyelesaikan masalah dengan algoritma D-and-C.Masukan: masukan yang berukuran nKeluaran: solusi dari masalah semula

}Deklarasi

r, k : integerAlgoritmaif n ≤ n0 then {ukuran masalah sudah cukup kecil }

SOLVE upa-masalah yang berukuran n inielse

Bagi menjadi 2 upa-masalah, masing-masing berukuran n/2DIVIDE_and_CONQUER(upa-masalah pertama yang berukuran n/2)DIVIDE_and_CONQUER(upa-masalah kedua yang berukuran n/2)COMBINE solusi dari 2 upa-masalah

endif

Time Complexity

⎩⎨⎧

>+≤

= ,)()2/(2

n ,)()(

0

0

nnnfnTnng

nT

Masalah menentukan Max dan Min dari n data :

Pseudocode

Procedure MaxMin(x, awal, akhir, Max, Min) Begin

if akhir‐awal ≤ 1 then

if x(awal) ≥ x(akhir) then

Max ← x(awal), Min ← x(akhir)

else Max ← x(akhir), Min ← x(awal)

else Begin

Mid ← (awal + akhir) DIV 2

MaxMin(x, awal, mid, Max1, Min1) devide

MaxMin(x, mid+1, akhir, Max2, Min2)

if Max1 ≥ Max2 then

Max ← Max1

else Max ← Max2

if Min1 ≤ Min2 then conquer

Min ← Min1

else Min ← Min2

end

end

• MaxMin dengan metode biasa → g(n)= 2n‐1

• MaxMin dengan metode devide and conquer → g(n)=

• Rekursif conquer

Contoh Mencari g(n)

• n adalah power of 2N g(n)2 1

4 2g(2)+2 = 4

8 2.4+2 = 10

16 2.10+2 = 22

32 2.22+2 = 46

64 2.46+2 = 94

n n − 2

Algoritma Perkalian 2 Bilangan Besar n Digit

• Misal n=4

• x = 6789

• y = 2476 x

• z = ......... ?

• Problem Size = n

• Operasi Dominan = perkalian

• algoritma biasa g(n) = n2 + cn → O(n2)

7/5/2010

3

Dengan metode devide and conquer

• a=67 b=89 x=67*102 + 89 = a.10n/2 + b

• c=24 d=76 y=24*102 = 76 = c.10n/2 + d

• z = ....

• z = x.y = (a.10n/2 + b).(c.10n/2 + d)

X a b

Y c d

z x.y (a.10 b).(c.10 d)

• z = ac.10n + (ad+bc) 10n/2 + bd

• g(n) = 4g( ) + cn → O(n2) →berdasarkan teorema

• 4 kali rekursif (ac, ad, bc, bd)

O(n2) tidak berubah menjadi lebih efisien, maka conquer perlu diubahpseudo code

Beginu ← (a+b).(c+d)v ← ac← bdw← bd

z ← v.10n + (u–v−w) 10n/2 + wEnd

maka g(n)= 3g( ) + cn → O(nlog 3) = O(n1,59)

TEOREMA MENCARI O(f(n)) untuk METODE DEVIDE AND CONQUER

• jika g(n) =

• Maka g(n)=

Algoritma Sorting

• Mengurutkan data dilihat dari struktur data dapat di bagi menjadi dua bagian yaitu statis (larik/array) dan dinamis (pointer). Dari dua macam cara penyimpanan data tersebutmacam cara penyimpanan data tersebut masing‐masing mempunyai keuntungan dan kerugian baik dalam hal kecepatan, efisiensi dan aspek kapasitas memori.

Insertion Sort O(n2)

• Idenya seperti pemain kartu yang membagi elemen menjadi 2 kelompok, yaitu kelompok kartu yang terurut berada di tangan pemain, dan kelompok kartu sumber yang akandan kelompok kartu sumber yang akan diambil untuk disisipkan secara urut ke dalam kelompok kartu pertama.

Algoritma

INSERTION‐SORT (A)

for j ← 2 to length[A]

do key ← A[j]3

{ Sisipkan A[j] ke dalam urutan terurut A[1 . . j ‐ 1].}

i← j – 1

while i > 0 and A[i] > key

do A[i + 1] ←A[i]

i← i – 1

A[i + 1] ←key

7/5/2010

4

Contoh 1 Contoh 2

Data Sumber : [8, 4, 7, 3, 1, 2, 6, 5]

Index : 1 2 3 4 5 6 7 8

Data Sumber : [8, 4, 7, 3, 1, 2, 6, 5]Index : 1 2 3 4 5 6 7 8

1. Ambil data mulai index 1 (8)

2. Ambil data index 2 (4), lalu bandingkan dengan nilai sebelumnya, jika lebih kecil darisebelumnya taruh di kiri dan jika tidak (lebihsebelumnya, taruh di kiri dan jika tidak (lebih besar) taruh di kanan , dr contoh diatas makasusunannya menjadi [4, 8]

• Ambil data index 3 (7), bandingkan dengan data index sebelumnya (4,8), 7>4 tapi lebih 7<8 sehingga susunannya menjadi [4, 7, 8]


• Ambil data index 4 (3), bandingkan dengan data index sebelumnya (4,7,8) dan susunanya menjadi [3, 4, 7, 8]


• Ambil data index 5 (1), bandingkan dengan data index sebelumnya (3,4,7,8) dan susun menjadi [1, 3, 4, 7, 8]


7/5/2010

5

• Ambil data index 6 (2), bandingkan dengan data index sebelumnya (1,3,4,7,8) dan susun menjadi [1, 2, 3, 4, 7, 8]


4. Ambil data index 7 (6), bandingkan dengan data index sebelumnya (1, 2, 3, 4, 7, 8) dan susun menjadi [1, 2, 3, 4, 6, 7, 8]


• Ambil data index 8 (5), bandingkan dengan data index sebelumnya (1, 2, 3, 4, 7, 6, 8) dan susun menjadi [1, 2, 3, 4, 5, 6, 7, 8]

• Hasil Akhir 1 2 3 4 5 6 7 8


• Hasil Akhir 1, 2, 3, 4, 5, 6, 7, 8

Bagaimana jika urutannya kita balik dari besar ke kecil ???Apakah Order fungsinya tetap atau lain, jika lain masuk dalam Apa ?

SimulasiSource

Analisa Insertion Sort

INSERTION‐SORT (A) cost time

for j ← 2 to length[A] c1 n

do key ← A[j]3 c2 n‐1{ Sisipkan A[j] ke dalam urutan terurut A[1 . . j ‐ 1].} 0 n‐1

i← j – 1 c4 n‐1while i > 0 and A[i] > key c5

do A[i + 1] ←A[i] c6

i← i – 1 c7

A[i + 1] ←key c8 n‐1

∑=

k

jjt

2

12

−∑=

k

jjt

12

−∑=

k

jjt

Analisa Insertion Sort

∑∑∑===

−+−+−++−+−+=n

jj

n

jj

n

jj nctctctcncncncnT

287

26

25421 )1(11)1()1()(

∑=

−+

=n

j

nnj2

12

)1(Jika

∑=

+=−

n

j

nnj2 2

)1(1

Maka )1()2

)1(()2

)1(()12

)1(()1()1()( 8765421 −++

++

+−+

+−+−+= ncnncnncnncncncncnT

)()222

()222

()( 85428765

4212765 ccccncccccccncccnT +++−+−−++++++=

T(n) di atas Ini berbentuk quadratik an2 + bn+ c, sehingga order fungsinya O(n2)

Selection Sort

• Idenya adalah mencari membandingkan data dengan data lain yang terkecil kemudian menukar posisinya (index‐nya), hal tersebut p y ( y ),dilakukan urut mulai dari index terkecil hingga habis.

7/5/2010

6

Algoritma versi 1

selectionsort(int A[], int besararray){int i, j;int min, temp;for (i = 0; i < besararray -1; i++){

min = i;for (j = i+1; j < besararray; j++){

if (A[j] < A[min]) min = j;}temp = A[i]; /*pertukaran data*/A[i] = A[min];A[min] = temp;

}}

Algoritma versi 2var lowkey: keytype;

{ kunci terkecil yg ada dari larik A[i], . . . , A[n] }lowindex : integer; { posisi lowkey (kunci terkecil)}

begin1. for i := 1 to n-1 do begin

{ pilih data terendah dr A[i], . . . , A[n] dan pertukarkan dg A[i] }

2. lowindex := i; 3. lowkey := A[i].key;

4. for j := i + 1 to n do { bandingkan key dg lowkey saat ini} 5. if A[j].key < lowkey then begin6. lowkey := A[j].key;

7. lowindex := j end; 8. swap(A[i], A[lowindex])

endend;

Contoh

Data : [8, 4, 7, 3, 1, 2, 6, 5] (Data Sumber)

index 1 2 3 4 5 6 7 8

Data : [8, 4, 7, 3, 1, 2, 6, 5] index 1 2 3 4 5 6 7 8

• untuk i=1 (8), cari dan bandingkan dengan data lainnya yang terkecil di sebelah kanannya, ditemukan pada i=5 (1), lalu tukar nilai datanya pada posisi index‐nya data i[1]nilai datanya pada posisi index nya data i[1] ditukar ke i[5], sehingga menjadi [1, 4, 7, 3, 8, 2, 6, 5].

• Untuk i=2 (4), cari dan bandingkan dengan data lainnya yang terkecil disebelah kanannya, ditemukan pada i=6 (2), lalu tukar nilai datanya pada posisi index‐nya data i[2] ditukar

Data : [1, 4, 7, 3, 8, 2, 6, 5] index 1 2 3 4 5 6 7 8

datanya pada posisi index nya data i[2] ditukar ke i[6], sehingga menjadi [1, 2, 7, 3, 8, 4, 6, 5].


Data : [1, 2, 7, 3, 8, 4, 6, 5] index 1 2 3 4 5 6 7 8


7/5/2010

7


Data : [1, 2, 3, 7, 8, 4, 6, 5] index 1 2 3 4 5 6 7 8



Data : [1, 2, 3, 4, 8, 7, 6, 5] index 1 2 3 4 5 6 7 8



Data : [1, 2, 3, 4, 5, 7, 6, 8] index 1 2 3 4 5 6 7 8

datanya pada posisi index nya data i[6] ditukar ke i[7], sehingga menjadi :

[1, 2, 3, 4, 5, 6, 7, 8].


Data : [1, 2, 3, 4, 5, 7, 6, 8] index 1 2 3 4 5 6 7 8

datanya pada posisi index nya data i[6] ditukar ke i[7], sehingga menjadi :

[1, 2, 3, 4, 5, 6, 7, 8].

Analisa Selection Sort

for i := 1 to n-1 do begin (akhir – awal + 2) + (akhir – awal + 1) .1 +

lowindex := i; lowkey := A[i].key; for j := i + 1 to n do (akhir awal + 2) + (akhir awal + 1) (p + 1))

( )∑=

n

i

iP1

for j := i + 1 to n do (akhir – awal + 2) + (akhir – awal + 1) (p + 1))

if A[j].key < lowkey then cbeginlowkey := A[j].key; 1lowindex := j 1

end; swap(A[i], A[lowindex]) 1end;


Inner Loop(akhir – awal + 2) + (akhir – awal + 1) (p + 1))= ((n – (i+1)) + 2) + ((n – (i+1)) + 1) (2 + 1)= ((n – (i+1)) + 2) + ((n – (i+1)) + 1) . 3= ((n – (i+1)) + 2) + 3(n – (i+1)) + 3= 4 (n – (i+1)) + 5= 4n 4i +4+5= 4n – 4i +4+5= 4n – 4i +9(P(i)) = Banyak Langkah dalam S = 1 + banyak langkah inner loop

= 1 + 4n – 4i +9 = 4n – 4i +10

7/5/2010

8


• Outer Loop• Banyak langkah= (akhir – awal + 2) + (akhir – awal + 1) .1 +

•= (((n – 1)‐1) + 2) + (((n – 1)‐1) + 1) .1 +• 2n + 3 +

( )∑=

n

i

iP1

( )∑=

+n

i 110 4i– 4n

∑=

n

in

14 ∑

=

n

ii

14 ∑

=

n

i 1

10‐ + n

•= 2n + 3 + 4n.n – 4. + 10.n = •= 2n + 3 + 4n2 ‐ +10n•= 2n + 3 + 6n2 – 2n2 ‐ 2n + 10n•= 4n2 + 10 n + 3 4n2 + 10n + 3 ∈ O (n2)

( )⎟⎠⎞

⎜⎝⎛ +1

21 nn ∑

=i

i1

( )⎟⎠⎞

⎜⎝⎛ +1

21 nn

nn24

24 2 −

Source Simulasi

Buble Sort

• Metode pengurutan gelembung atau penukaran dapat dilakukan dengan meletakkan elemen terbesar pada sebelah paling kanan urutan (N) dan kemudian elemenpaling kanan urutan (N) dan kemudian elemen terbesar kedua diletakkan pada posisi N‐1, begitu seterusnya. Atau sebaliknya dengan mencari elemen terkecilnya diletakkan paling kiri (pertama/i), dan terkecil kedua di i+1 dan seterusnya.

Algoritma Bubble Sort 1

for i := 1 to n‐1 do

for j := n downto i+1 do

if A[j].key < A[j‐1].key then swap(A[j], A[j‐1])

procedure swap ( var x, y: type) { pertukaran nilai x dan y } var temp: type; begintemp := x; x := y; y := temp

end; { swap }

simulasisource

Agoritma Bubble Sort 2

void bsort(int list[], int n){int i,j,k;for(i=0;i<(n-1);i++)

for(j=0;j<(n-(i+1));j++)if(list[j] < list[j+1])

swap(&list[j],&list[j+1]);}

Contoh descending

Data : [8, 4, 7, 3, 1, 2, 6, 5] (Data Sumber)

Index 1 2 3 4 5 6 7 8

i=1

L[1] <L[2], false, jadi urutan tetap 8, 4, 7, 3, 1, 2, 6, 5

L[2] <L[3], true, jadi urutan berubah 8, 7, 4, 3, 1, 2, 6, 5





L[7] <L[8], false, jadi urutan berubah 8, 7, 4, 3, 2, 6, 5, 1

8, 7, 4, 3, 2, 6, 5, 1

Data : [8, 7, 4, 3, 2, 6, 5, 1]index 1 2 3 4 5 6 7 8

i=2

L[1]<L[2], false,jadi urutan tetap 8, 7, 4, 3, 2, 6, 5, 1

L[2]<L[3], false,jadi urutan berubah 8, 7, 4, 3, 2, 6, 5, 1 L[3]<L[4], false,jadi urutan tetap 8, 7, 4, 3, 2, 6, 5, 1

L[4]<L[5] false jadi urutan tetap 8 7 4 3 2 6 5 1

8, 7, 4, 3, 2, 6, 5, 1


L[5]<L[6], true,jadi urutan berubah 8, 7, 4, 3, 6, 2, 5, 1


L[7]<L[8], false,jadi urutan berubah 8, 7, 4, 3, 6, 5, 2, 1

8, 7, 4, 3, 6, 5, 2, 1

Berubah berarti nilai tersebut di tukar posisinya

7/5/2010

9

i=3L[1]<L[2], false,jadi urutan tetap 8, 7, 4, 3, 6, 5, 2, 1




Data : [8, 7, 4, 3, 6, 5, 2, 1]index 1 2 3 4 5 6 7 8

L[5]<L[6], true,jadi urutan berubah 8, 7, 4, 6, 5, 3, 2, 1L[6]<L[7], false,jadi urutan tetap 8, 7, 4, 6, 5, 3, 2, 1


8, 7, 4, 6, 5, 3, 2, 1

i=4

L[1]<L[2],false,jadi urutan tetap 8, 7, 4, 6, 5, 3, 2, 1

L[2]<L[3],false,jadi urutan tetap 8, 7, 4, 6, 5, 3, 2, 1 L[3]<L[4], true,jadi urutan berubah 8, 7, 6, 4, 5, 3, 2, 1

L[4]<L[5] true jadi urutan berubah 8 7 6 5 4 3 2 1

Data : [8, 7, 4, 6, 5, 3, 2, 1]index 1 2 3 4 5 6 7 8

L[4]<L[5],true,jadi urutan berubah 8, 7, 6, 5, 4, 3, 2, 1




8, 7, 6, 5, 4, 3, 2, 1

i=5


L[2]<L[3],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1 L[3]<L[4], false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1


Data : [8, 7, 6, 5, 4, 3, 2, 1]index 1 2 3 4 5 6 7 8

i:6j=0 tidak berubah





8, 7, 6, 5, 4, 3, 2, 1

i=6

L[1]<L[2],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1L[2]<L[3],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1

L[3]<L[4],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1 1


Data : [8, 7, 6, 5, 4, 3, 2, 1]index 1 2 3 4 5 6 7 8





8, 7, 6, 5, 4, 3, 2, 1

Sampai disini algoritma berhenti, karena n‐1=7 sehingga i<n‐1 pada outer loop sudah tidak terpenuhi (lihat algo BS versi 2)

i=7

i=8 tetap tidak berubah.

Data : [8, 7, 6, 5, 4, 3, 2, 1]index 1 2 3 4 5 6 7 8

Kalau ,misalnya di teruskan juga tidak merubahurutan

Analisis Bubble Sort

• PR saja Tulis Tangan, Buktikan bahwa Algoritma Buble Sort berada pada order O(n2)

7/5/2010

10

Sequential Sort

• Mengurutkan Data secara sekuen, baik dari kecil ke besar ataupun besar ke kecil

• Membanding current dengan next

Jik k k k• Jika current > next, maka tukarkan

• Dilakukan hingga habis

Algoritma Sequensial Sort 1

SeqSort(int A[], lo, up) {/*lo=A[0], up=A[n]*/int lo,up; int i, j; int tempa; for (i=up-1;i>=lo;i--) {

tempa= A[i]; for (j=i+1;(j<=up&&tempa>A[j]);j++);

A[j-1]=A[j]; /*tukarkan*/A[j-1] = tempa;

/*isi nilai array baru*/

Source simulasi

Algoritma Sekuensial Sort 2

void Seq(int *x, int n){int i,j,temp;for (i=0 ;i<n-1,i++)for (j=i+1;j<n;j++)for (j i+1;j<n;j++)if (x[i]>x[j]) {

temp=x[i];x[i]=x[j];

x[j]=temp;}

}

Contoh

• x=2, 1, 6, 7, 4, 3, 2i= 1 2 3 4 5 6 7

• j= 2 3 4 5 6 7

contoh

Data SEBELUM diurutkan

2 1 6 7 4 3 2

i:0

j=1‐> 1 2 6 7 4 3 2j=2‐> tidak berubah

j=3 > tidak berubah

i:2j=3‐> tidak berubahj=4‐> 1 2 4 7 6 3 2j=5‐> 1 2 3 7 6 4 2j=6‐> 1 2 2 7 6 4 3i:3

j=3‐> tidak berubah

j=4‐> tidak berubahj=5‐> tidak berubah


i:1




j=4‐> 1 2 2 6 7 4 3j=5‐> 1 2 2 4 7 6 3j=6‐> 1 2 2 3 7 6 4i:4j=5‐> 1 2 2 3 6 7 4j=6‐> 1 2 2 3 4 7 6i:5j=6‐> 1 2 2 3 4 6 7

Data SETELAH diurutkan1 2 2 3 4 6 7

Analisa Sequential Sort

• PR Lagi sama dengan Bubble Sort

7/5/2010

11

Merge Sort

• Ada dua larik L1 dan L2, dan larik L3 sebagai penampung hasil urutan, jumlah L3=L1+L2

• Ambil elemen pertama dari L1 dan L2, lalu bandingkan nilainya Jika L1[1]>L2[1] makabandingkan nilainya. Jika L1[1]>L2[1] maka L2[1] dikopikan ke L3[1], kalau tidak L1[1] dikopikan ke L3[1]. Untuk Larik yang elemennya dikopikan ke L3, elemen berikutnya yang dibandingkan adalah elemen pada subskrib berikutnya.

• Berada dalam order O(n log n)

Analisa Merge Sort

• Mergesort dapat di tulis tanpa cara rekursif

• Sehingga kita dapat menulis kompleksitas algoritma, misal n dalaha power of 2, sehingga kita selalu memisahnya menjadi 2sehingga kita selalu memisahnya menjadi 2

• Untuk n = 1, waktunya konstan yaitu 1.

• Selain itu untuk n/2, di tambah waktu untuk merge di hasilkan :

⎪⎩

⎪⎨⎧

>+

=

1,)2

(2

1,1)( nnnT

nnT

Algoritma mergesort 1dalam c

void msort(int X[], int n ){

int l;int Y[MAX];l =1;while (l < n ){

mpass(X,Y,n,l);l = l*2;mpass(Y,X,n,l);l = l*2;

}}


void mpass( int X[],int Y[],int n,int l){int i;i = 0;while( i <= (n-2*l+1)){

merge(X,i,(i+l-1),(i+2*l-1),Y);i = i + 2*l;

}if((i+l-1) < n) merge(X,i,(i+l-1),n,Y);else

while (i <= n ){Y[i] = X[i];i++;

}}


void merge(int X[],int l,int m,int n,int Z[]){int i,j,k;i=k=l;j=m+1;while( i <= m && j <= n){

if(X[i] <= X[j]) { Z[k] = X[i];i++;}else{Z[k] = X[j]; j++;}}else{Z[k] = X[j]; j++;}

k++;}if (i>m){

/*Zk...Zn <-- Xj...Xn*/while(k<=n && j<=n){Z[k] = X[j]; k++;j++;}

}else { /*Zk...Zn <-- Xi...Xm*/while(k<=n && i<=m){ Z[k] = X[i];k++;i++;}

}}

Algoritma Merge sort untuk2 larik

void mergesort(int numbers[], int temp[], int array_size){m_sort(numbers, temp, 0, array_size ‐ 1);

}

void m_sort(int numbers[], int temp[], int left, int right){

int mid;

if (right > left){

mid = (right + left) / 2;

m_sort(numbers, temp, left, mid);

m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);}

}

7/5/2010

12


void merge(int numbers[], int temp[], int left, int mid, int right){

int i, left_end, num_elements, tmp_pos;

left_end = mid ‐ 1;

tmp_pos = left;num_elements = right ‐ left + 1;

while ((left <= left end) && (mid <= right)) {while ((left left_end) && (mid right)) {

if (numbers[left] <= numbers[mid]) {temp[tmp_pos] = numbers[left];

tmp_pos = tmp_pos + 1;

left = left +1;

}else


{temp[tmp_pos] = numbers[mid];

tmp_pos = tmp_pos + 1;

mid = mid + 1; }

}while (left <= left_end) {

temp[tmp pos] = numbers[left];temp[tmp_pos] = numbers[left];

left = left + 1;tmp_pos = tmp_pos + 1; }

while (mid <= right) {

temp[tmp_pos] = numbers[mid];

mid = mid + 1;tmp_pos = tmp_pos + 1; }

for (i=0; i <= num_elements; i++) {

numbers[right] = temp[right];right = right – 1; }

}

Contoh

L1: 11, 12, 23, 33, 45, 67, 68, 70, 81, 92 =10

L2: 9, 12, 21, 42, 56, 65, 74 =7

L3: x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x =17

• Contoh diatas L1[1]=11, L2[1]=11, 11>9 ?, ya, jadi L3[1]=9. Perbandingan berikutnya L1[1]=11, L2[2]=12, 11>12, tidak, jadi L3[2]=11, begitu seterusnya hingga salah satu larik habis dikopi ke L3, kemudian sisa larik dikopikan ke L3 juga dan hasilnya :

Hasil

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

Contoh Merge sort lagi

• Data : 11 2 45 67 33 22 11 0 34 23

• Hasil: 0 2 11 11 22 23 33 34 45 67

source simulasi

Quick Sort

• Jika jumlah elemen dalam S adalah 0 atau 1, maka urutan sudah terjadi (trivial).

• Ambil sembarang elemen v dalam S. Ini di sebut pivotsebut pivot.

• Partition atau bagi S ‐ {v} (sisa elemen dalam S) ke dalam dua kelompok yang berbeda : S1 = {x ∈S ‐ {v}| x≤ v}, dan S2 = {x∈ S ‐{v}| x≥ v}.

• Kembalikan { quicksort(S1) di ikuti oleh v dan di ikuti lagi oleh quicksort(S2)}.

7/5/2010

13

Algoritma 1

void quickSort(int numbers[], int array_size) {

q_sort(numbers, 0, array_size - 1); }

Algoritma 1

void q_sort(int numbers[], int left, int right) {

int pivot, l_hold, r_hold; l_hold = left; r_hold = right; pivot = numbers[left]; while (left < right){

while((numbers[right]>=pivot)&& left<right))right--;

Algoritma 1

if (left != right){ numbers[left] = numbers[right]; left++;

} while ((numbers[left]<=pivot)&&(left<right))

left++; if (left != right){

numbers[right] = numbers[left]; right--;

} }

Algoritma 1

numbers[left] = pivot; pivot = left; left = l_hold; right = r_hold; if (left < pivot)

q_sort(numbers, left, pivot-1); if (right > pivot)

q_sort(numbers, pivot+1, right); }

Algoritma 2

int posisikunci(int i,int j ){

return((i+j) /2);}

Algoritma 2void quicksort(int list[],int m,int n){

int key,i,j,k;if( m < n){

k = posisikunci(m,n);

tukar(&list[m],&list[k]);key = list[m]; i = m+1; j = n;

while(i <= j){while((i<=n)&&(list[i]<=key))i++;

while((j>=m)&&(list[j]>key)) j--;

if(i<j) tukar(&list[i],&list[j]);}

tukar(&list[m],&list[j]);

quicksort(list,m,j-1);quicksort(list,j+1,n);

}

}

7/5/2010

14

Contoh dengan Algo 2

• Data :10,5,23,67,20,30,60

• Pertama, key = 67, i =1, dan j =6. i di inkremen hingga 7, karena tidak ada elemen > key , maka j tidak di dekremen , karena pada posisi 6,nilainya kurang dari key. Karena i > j, kita tukar elemen key (posisi 0) dengan posisi 6, lalu call qsort secara rekursif, dan menghasilkan sublist kiri dari posisi 0 sampai 5, serta sublist kanan seperti :

Sublist kiri

Contoh dengan algo 2

Pada tahap kedua sublist kiri dengan key = 23, i =1, dan j =5. i di inkremen hingga mencapai 2. Karena elemen pada posisi 2 lebih besar dari kunci, j di dekremen hingga 4 karena nilai pada posisi 4 kurang dari kunci. Karena i < j, elemen pada posisi 2 dan 4 di tukar. Kemudian i di inkremen hingga 4 dan j di dekremen sampai 3. Karena i > j, kita tukar elemen kunci (posisi 0), dengan elemen pada posisi 3, dan call qsort secara rekursif dengan menghasilkan p p , q g gsublist kiri dari posisi elemen 0 sampai 2, dan kanan dari 4 sampai 5 :

Hal ini di lanjutkan hingga selesai atau m>n, atau elemen larik habis.

source simulasi

Tugas

• Simulasikan Algoritma Radixsort dan Pigeon Hole

• Presentasikan

Searching

• Sekuential

• Binary Search

• Interpolation Search

Sequential Search

• Dikenal sebagai linear search

• Mencari key(info yang dicari) pada suatu data tak terurut hingga data di temukan atau data sudah mencapai akhir lariksudah mencapai akhir larik

Algoritma Insert sekuensial dalam Flowchart

Addr 0

Mulai

M(addr) data

Data disimpan dariAlamat awal ke alamatb ik t

M(addr) Isi ?

Addr Addr+1

Addr=p ?

M(addr) data

Selesai

T

T Y

Y

berikutnya

7/5/2010

15

Searching Sekuensial terurut

• Data tersimpan dalam keadaan terurut

• Pencarian secara ascending atau descending

• Alamat terakhir(P1) dari larik (P) adalah– 0<= P1 <= P‐1

Analisa

• Dalam metode pencarian sekuensial, perbandingan yang di lakukan adalah sebanyak n kali dalam kasus worstcase, sehingga algoritma ini berorder O(n)sehingga algoritma ini berorder O(n)

• Jika pada index i data ketemu maka dia berada pada O(i)

• Sehingga rata‐rata pencariannya berada pada O(n/2)

Flowchart Searching Sekuensial

Addr 0

Mulai

Addr Addr+1 Data tdk Ada

M(addr) Isi ?

Addr Addr+1 Data tdk Ada

Selesai

T

T Y

Y

M(addr)=data ?

Data>M(addr) ?

Data Ada

T

Y

contoh

• Dicari data=50

1. Addr=0, m(addr) isi data ? Y

2 M(addr) data ? T (15<>50)

15

20

25

0M data

1

2

1

2

32. M(addr)=data ? T (15<>50)

3. M(addr)>data ? Y (50>15)

4. Addr=addr+1 (addr=1)

5. Ulangi langkah 1Jika di jalankan maka akan memerlukan 5 langkahuntuk menemukan data 50, yaitu dr 15,20,25,30 dan 50

25

30

50

60

75

1007

23

4

56

45

Binary Search

Diketahui :

Larik x=x(1),x(2),x(3),…,x(n)

Data tertentu

Cari a → a ada di x, x[i]=a → i=?

Binary Search

• Syarat : data sudah terurut

7/5/2010

16

Analisa

• Dalam binary search, jumlah perbandingan yang di perlukan untuk mencari satu elemen dalam list dalah tidak lebih dari log2n, dimana n adalah ukuran listn adalah ukuran list .

• Dengan demikian algoritma binary search mempunyai kompleksitas waktu O(n *( log2n))

• Ukuran efisiens :– max=2log n mis n=16 maka 4 langkah

– min=1

– rata2=(1+2+…+log n) log n == ½ 2 log n

Algoritma Binary Search

int BinSearch(int *arr, int val, int N){

int low = 0; int high = N – 1; int mid;while ( low <= high ) {

mid = ( low + high )/2;( g ) ;if (arr[mid]==val) {return 1; }else if (arr[mid] < val) {

low = mid + 1;}else { high = mid – 1;}

}return 0;

}

Flowchart Binary Search

L 0U p1

Mulai L=LowerU=UpperP1=ukuran Memori/Larikt=tengah

L<=U ?

U t-1Data tdk Ada

Selesai

T

T YM(addr)=data ?

Data>M(t) ?

Data AdaT

Y

t (L+U)/2L t+1Y

contoh

x= 2 7 9 12 14 20 36 76 100 125

i= 1 2 3 4 5 6 7 8 9 10

ingin dicari a=36 dalam x

x= 2 7 9 12 14 20 36 76 100 125i= 1 2 3 4 5 6 7 8 9 10

lower=1

upper=10

t=(lower+upper) div 2 = 5 dengan x[5]=14t=5

a=36

Dicari a=36

a>x[t] maka lower = 6

upper=10

t=16/2=8 dengan x[8]=76

x= 2 7 9 12 14 20 36 76 100 125i= 1 2 3 4 5 6 7 8 9 10

a=36

t=16/2=8

Lower=t+1

t=16/2=8

7/5/2010

17

karena a<x[8], lower=6

upper=t‐1=7

t=6 dengan x[6]=20

x= 2 7 9 12 14 20 36 76 100 125i= 1 2 3 4 5 6 7 8 9 10

a=36

t=13/2=6

upper=t-1

t=13/2=6

karena a>x[6] ,

lower=t+1=6+1=7

upper=7

t=7 dengan x[7]=36

x= 2 7 9 12 14 20 36 76 100 125i= 1 2 3 4 5 6 7 8 9 10

a=36Upper=t+1

t=7 dengan x[7]=36t=7

karena a=x[7] ,

Data Di temukan

x= 2 7 9 12 14 20 36 76 100 125i= 1 2 3 4 5 6 7 8 9 10

a=36

Interpolation Search

• Dikenal sebagai estimated entry search

• Data sudah terurut

• Mirip Binary Search tetapi lebih canggih diki (lih fl h )sedikit (lihat flowchart)

• Pada tiap langkah pencarian algoritma membuat suatu tebakan/perkiraan (Interpolasi)

Perbandingan Analisa

• Ketika n besar, binary search membutuhkan waktu lebih sedikit, dalam worst case, di banding linear search. Hal ini karena di membuat perbandingan lg n dari pada nmembuat perbandingan lg n dari pada n.

• Langkah yang di tunjukan dalam binary search lebih kompleks dan membutuhkan waktu yang lebih dari pada langkah dalam linear search.

• Dengan demikian untuk kasus n kecil, linear search lebih cepat.

Perbandingan Analisa

• Mirip dengan hal sebelumnya, interpolation perlu melakukan langkah kompleks dalam loop , walaupun dia memerlukan lebih sedikit waktu di banding binary searchwaktu di banding binary search.

• Pada n yang besar maka interpolasi lebih cepat di banding binary, karena pada saat melakukan interpolasi terhadap penentuan median lebih presisi, walupun langkahnya lebih kompleks

7/5/2010

18

Interpolation Sequential Search

• Kombinasi Interpolasi dan sequential

• Algoritma akan melakukan pencarian secara interpolasi, jika tidak ketemu Algoritma akan mencari data secara sequen kedepan ataumencari data secara sequen, kedepan atau belakang , tergantung arah yang di berikan

Flowchart Interpolation

L 0U p1

MulaiL=LowerU=UpperP1=ukuran Memori/Larikt=tengah

L<=U ?

U t-1Data tdk Ada

Selesai

T

T YM(addr)=data ?

Data>M(t) ?

Data AdaT

Y

L t+1Y

)(*)()(

)( LULMUMLMdataLt −

−−

+←

Selama L<=U dan M(L)<=data<=M(U)T merupakan integer yg di round-up atau yang terdekat (ceiling)

Algoritma

int isearch(typekey key, dataarray r[]){ int high, j, low ; low = 1; high = n; while (r[high]>= key) && (key > r[low]) do{ j= trunc((key— r[low])/(r[high]— r{low])*(high—low))+low;

if (key>r[j]) low = j+1;else if (key < r[j]) high := j-1 else low =j; } if (r[low]== key) return(low) /*** ketemu(r[low])

***/else return(—1); /*** tidakketemu ***/ }

Contoh searching SS,BS,IS

• Data = 5,10,20,28,40,42,50,60,80,100,1000

• Cari 100,800,13 dan 40 dengan Sekuensial, Binary dan InterpolationBinary dan Interpolation

• N=11, P>N 0<=p1<=P‐1

i 0 1 2 3 4 5 6 7 8 9 10

N 5 10 20 28 40 42 50 60 80 100 1000

Sekuensial Search100,800,13,40

51020280

0123

step addr M(addr)Data:M(Addr) Jmlh

step100 800 13 40

1 0 5 > > > >

2 1 10 > > > >

40425060801001000

456789

10

3 2 20 > > < > 3

4 3 28 > > >

5 4 40 > > = 5

6 5 42 > >

7 6 50 > >

8 7 60 > >

9 8 80 > >

10 9 100 = > 10

11 10 1000 < 11

Binary Search(1)100,(2)800,(3)13,(4)40

51020280

0123

Data step L U t M(t) Data:M(t)

100 1 0 10 5 42 >

2 5+1=6 10 8 80 >

3 8+1=9 10 9 100 =

40425060801001000

456789

10

800 1 0 10 5 42 >

2 5+1=6 10 8 80 >

3 8+1=9 10 9 100 >

4 9+1=10 10 10 1000 <

5 10 10‐1=9 9 sudah stop

Data>M(addr) maka L=t+1 dan U tetap

Data<M(addr) maka L tetap dan U=t-1

7/5/2010

19

BS Lanjutan

51020280

0123

Data step L U t M(t) Data:M(t)

13 1 0 10 5 42 <

2 0 5‐1=4 2 80 <

3 0 2‐1=1 stop

40425060801001000

456789

10

40 1 0 10 5 42 <

2 0 5‐1=4 2 20 >

3 2+1=3 4 4 40 =



Interpolasi Search

51020280

0123

Data step L U M(t) Data:M(t)

100 1 0 10 1 10 >

2 2 10 3 28 >

)(*)()(


−−

+←

40425060801001000

456789

10

3 4 10 5 42 >

4 6 10 7 60 >

5 8 10 9 100 =

800 1 0 10 8 80 >

2 9 10 10 1000 <

3 9 9 10 stop



=0+((100-5)/(1000-5))*(10-0)=0+((95)/(995))*10=0+0.095*10=0+0.95=0.95 1

Interpolasi Search

51020280

0123

Data step L U M(t) Data:M(t)

40 1 0 10 1 10 >

2 2 10 stop

)(*)()(


−−

+←

40425060801001000

456789

10

13 1 0 10 1 10 >

2 2 10 3 28 >

3 4 10 4 40 =



Perbandingan Metode

Data CariLangkah

SS BS IS

100 10 3 5

800 11 5 3800 11 5 3

13 3 3 2

40 5 3 3

Rata‐rata =∑/N 29/4 14/4 13/4

Jadi metode yang terbaik untuk kasus diatas adalah IS

source simulasi

Soal

• X=1,3,6,10,15,21,28,36,45,55,75,150,750,1500,3000

• Cari data dengan 3 metode seq,binary dan interpolasi untuk data: 25,21,750 dan 1250. Hitung berapa langkah utk masing‐masing data dan cari rata‐rata pencariannya.

• SolusiSolusi

Soal Lagi ?

Data

27,18,29,28,39,13,16,42,17

Ditanya:

Dicari 39,50,42,20

Gunakan SS,BS,IS

Berapa rata‐rata masing‐masing metode

11-12 algoritma divide and coquer.ppt - blognya maz wied · algoritma sorting • mengurutkan data...

Documents