2010

7/5/2010

Definisi

wijanarto

• 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.

Algoritma

Versi lain

Algoritma Divide And Coquer

procedure DIVIDE_and_CONQUER(input n : integer) { Menyelesaikan masalah dengan algoritma D-and-C. Masukan: masukan yang berukuran n Keluaran: solusi dari masalah semula } Deklarasi r, k : integer Algoritma if n ≤ n0 then {ukuran masalah sudah cukup kecil } SOLVE upa-masalah yang berukuran n ini else Bagi menjadi r upa-masalah, masing-masing berukuran n/k for masing-masing dari r upa-masalah do DIVIDE_and_CONQUER(n/k) endfor COMBINE solusi dari r upa-masalah menjadi solusi masalah semula } endif

Diagram D N C

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 III

N input k

Sub prob I

Sub prob II

Sub prob III

Sub prob k

Sub solusi I

Sub solusi II

Sub solusi III

Sub solusi k

Sub solusi I

1

7/5/2010

Jika pembagian secara biner procedure DIVIDE_and_CONQUER(input n : integer) { Menyelesaikan masalah dengan algoritma D-and-C. Masukan: masukan yang berukuran n Keluaran: solusi dari masalah semula } Deklarasi r, k : integer Algoritma if n ≤ n0 then {ukuran masalah sudah cukup kecil } SOLVE upa-masalah yang berukuran n ini else Bagi menjadi 2 upa-masalah, masing-masing berukuran n/2 DIVIDE_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

g (n) , n ≤ n0 ⎧ T (n) = ⎨ ⎩2T ( n / 2) + f ( n ) , n > n0

Masalah menentukan Max dan Min dari n data : • MaxMin dengan metode biasa → g(n)= 2n‐1 • MaxMin dengan metode devide and conquer → g(n)=

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

•

Algoritma Perkalian 2 Bilangan Besar n Digit

Contoh Mencari g(n) • n adalah power of 2

Rekursif conquer

N 2

g(n) 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

• • • • • • •

Misal n=4 x = 6789 y = 2476 x z = ......... ? Problem Size = n Operasi Dominan = perkalian algoritma biasa g(n) = n2 + cn → O(n2)

2

7/5/2010

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

X

a

b

Y

c

d

• • • •

z = .... zz = x.y x.y = (a.10 (a.10n/2 + b).(c.10 b).(c.10n/2 + d) d) n n/2 z = ac.10 + (ad+bc) 10 + bd g(n) = 4g( ) + cn → O(n2) →berdasarkan teorema • 4 kali rekursif (ac, ad, bc, bd)

TEOREMA MENCARI O(f(n)) untuk METODE DEVIDE AND CONQUER • jika g(n) =

• Maka g(n)=

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 akan dan kelompok kartu sumber yang akan diambil untuk disisipkan secara urut ke dalam kelompok kartu pertama.

O(n2) tidak berubah menjadi lebih efisien, maka conquer perlu diubah pseudo code Begin u ← (a+b).(c+d) v ← ac w← bd ← bd z ← v.10n + (u–v−w) 10n/2 + w End maka g(n)= 3g( ) + cn → O(nlog 3) = O(n1,59)

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 tersebut macam cara penyimpanan data tersebut masing‐masing mempunyai keuntungan dan kerugian baik dalam hal kecepatan, efisiensi dan aspek kapasitas memori.

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

3

7/5/2010

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 dari sebelumnya taruh di kiri dan jika sebelumnya, taruh di kiri dan jika tidak (lebih (lebih besar) taruh di kanan , dr contoh diatas maka susunannya 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]

4

7/5/2010



• 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]


Analisa Insertion Sort

• 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 ?

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]

c6

Analisa Insertion Sort n

n

n

j =2

j =2

j =2

T (n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 ∑ t j +c6 ∑ t j − 1 +c7 ∑ t j − 1 + c8 ( n − 1)

∑

j=

j =2 n

n(n + 1) −1 2

∑ j −1 = j =2

Maka

n(n + 1) 2

T (n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 ( T (n) = (

k

∑t

i←i–1

c7 c8

j

j =2

k

∑t

j

−1

j

−1

j =2 k

A[i + 1] ←key

n

time n n‐1 n‐1 n‐1

∑t j =2

n‐1

Simulasi

Source

Jika

cost c1 c2 0 c4 c5

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.

n(n + 1) n(n + 1) n(n + 1) − 1) + c6 ( ) + c7 ( ) + c8 (n − 1) 2 2 2

c5 c6 c7 2 c c c + + )n + (c1 + c2 + c4 + 5 − 6 − 7 + c8 )n − (c2 + c4 + c5 + c8 ) 2 2 2 2 2 2

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

5

7/5/2010

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; } }

Contoh

Algoritma versi 2 var lowkey: keytype; { kunci terkecil yg ada dari larik A[i], . . . , A[n] } lowindex : integer; { posisi lowkey (kunci terkecil)} begin 1. 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 begin 6. lowkey := A[j].key; 7. lowindex := j end; 8. swap(A[i], A[lowindex]) end end;

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

Data : [8, 4, 7, 3, 1, 2, 6, 5] (Data Sumber) 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 nilai datanya pada posisi index nya data i[1] data i[1] ditukar ke i[5], sehingga menjadi [1, 4, 7, 3, 8, 2, 6, 5].

Data : [1, 4, 7, 3, 8, 2, 6, 5] index 1 2 3 4 5 6 7 8 • 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 datanya pada posisi index nya data i[2] ditukar data i[2] ditukar ke i[6], sehingga menjadi [1, 2, 7, 3, 8, 4, 6, 5].


6

7/5/2010



Data : [1, 2, 3, 4, 5, 7, 6, 8] index 1 2 3 4 5 6 7 8 • Untuk i=6 (7), cari dan bandingkan dengan data lainnya yang terkecil disebelah kanannya, ditemukan pada i=7 (6), lalu tukar nilai datanya pada posisi index‐nya datanya pada posisi index nya data i[6] ditukar 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 • Untuk i=6 (7), cari dan bandingkan dengan data lainnya yang terkecil disebelah kanannya, ditemukan pada i=7 (6), lalu tukar nilai datanya pada posisi index‐nya datanya pada posisi index nya data i[6] ditukar data i[6] ditukar ke i[7], sehingga menjadi : [1, 2, 3, 4, 5, 6, 7, 8].

Analisa Selection Sort

Analisa Selection Sort n

for i := 1 to n-1 do begin (akhir – awal + 2) + (akhir – awal + 1) .1 + ∑ P(i ) lowindex := i; lowkey := A[i].key; for j := i + 1 to n do (akhir awal + 2) + (akhir – (akhir – awal + 2) + (akhir awal + 1) (p + 1)) awal + 1) (p + 1)) if A[j].key < lowkey then c begin lowkey := A[j].key; 1 lowindex := j 1 end; swap(A[i], A[lowindex]) 1 end; i =1

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 +9 (P(i)) = Banyak Langkah dalam S = 1 + banyak langkah inner loop = 1 + 4n – 4i +9 = 4n – 4i +10

7

7/5/2010

Analisa Selection Sort • Outer Loop

n

• Banyak langkah= (akhir – awal + 2) + (akhir – awal + 1) .1 + ∑ P(i ) i =1

•= (((n – 1)‐1) + 2) + (((n – 1)‐1) + 1) .1 + ∑ (4n – 4i + 10) • 2n + 3 + ∑ 4n ‐ ∑ 4i + ∑10 n i = ⎛⎜ 12 n(n + 1)⎞⎟ ( ) •= 2n + 3 + 4n.n – 4. + 10.n ∑ ⎝ ⎠ i =1 4 4 •= 2n + 3 + 4n2 ‐ 2 n − 2 n +10n •= 2n + 3 + 6n2 – 2n2 ‐ 2n + 10n •= 4n2 + 10 n + 3 4n2 + 10n + 3 ∈ O (n2) n

i =1

n

n

n

i =1

i =1

i =1

⎞ ⎛1 ⎜ n n +1 ⎟ ⎠ ⎝2

2

Source

Buble Sort • Metode pengurutan gelembung atau penukaran dapat dilakukan dengan meletakkan elemen terbesar pada sebelah paling kanan urutan (N) dan kemudian elemen paling 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.

Simulasi

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; begin temp := x; x := y; y := temp end; { swap } source

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]); }

simulasi

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

Contoh descending

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

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

7/5/2010

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

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

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

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

i=5 L[1]
i:6 j=0 tidak berubah

Data : [8, 7, 6, 5, 4, 3, 2, 1] index 1 2 3 4 5 6 7 8 i=7 i=8 tetap tidak berubah.

i=6 L[1]
8, 7, 6, 5, 4, 3, 2, 1 Sampai disini algoritma berhenti, karena n‐1=7 sehingga i
Analisis Bubble Sort • PR saja Tulis Tangan, Buktikan bahwa Algoritma Buble Sort berada pada order O(n2)

Kalau ,misalnya di teruskan juga tidak merubah urutan

9

7/5/2010

Sequential Sort • Mengurutkan Data secara sekuen, baik dari kecil ke besar ataupun besar ke kecil • Membanding current dengan next • Jika current > next, maka tukarkan Jik k k k • 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

Algoritma Sekuensial Sort 2 void Seq(int *x, int n){ int i,j,temp; for (i=0 ;ix[j]) { temp=x[i]; x[i]=x[j]; x[j]=temp; } }

contoh Data SEBELUM diurutkan 2167432 i:0 j=1‐> 1 2 6 7 4 3 2 j=2‐> tidak berubah j=3 > tidak berubah j=3‐> j=4‐> tidak berubah j=5‐> tidak berubah j=6‐> tidak berubah i:1 j=2‐> tidak berubah j=3‐> tidak berubah j=4‐> tidak berubah j=5‐> tidak berubah j=6‐> tidak berubah

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

simulasi

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

Analisa Sequential Sort • PR Lagi sama dengan Bubble Sort

Data SETELAH diurutkan 1223467

10

7/5/2010

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] maka bandingkan 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)

Algoritma mergesort 1 dalam 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; } }

Algoritma mergesort 2 dalam c 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++;} 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++;} } }

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 2 sehingga 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, n = 1 ⎧⎪ n T ( n) ⎨ ⎪⎩2T ( 2 ) + n, n > 1

Algoritma mergesort 2 dalam c 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++; } }

Algoritma Merge sort untuk 2 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); } }

11

7/5/2010

Algoritma Merge sort untuk 2 larik 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 while ((left left_end) && (mid end) && (mid <= right)) { right)) { if (numbers[left] <= numbers[mid]) { temp[tmp_pos] = numbers[left]; tmp_pos = tmp_pos + 1; left = left +1; } else

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 :

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

Algoritma Merge sort untuk 2 larik {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; } }

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

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 pivot sebut 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)}.

12

7/5/2010

Algoritma 1 void quickSort(int numbers[], int array_size) { q_sort(numbers, 0, array_size - 1); }

Algoritma 1 if (left != right){ numbers[left] = numbers[right]; left++; } while ((numbers[left]<=pivot)&&(left
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
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 2 void 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); } }

13

7/5/2010

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 :

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 p p , q g g elemen pada posisi 3, dan call qsort secara rekursif dengan menghasilkan sublist 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. Sublist kiri

source

simulasi

Tugas • Simulasikan Algoritma Radixsort dan Pigeon Hole • Presentasikan

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 larik sudah mencapai akhir larik

Searching • Sekuential • Binary Search • Interpolation Search

Algoritma Insert sekuensial dalam Flowchart Mulai Data disimpan dari Alamat awal ke alamat b ik t berikutnya

AddrÍ0 M(addr)Ídata M(addr) Isi ?

T

Y Selesai

AddrÍAddr+1 T

Addr=p ?

Y

14

7/5/2010

Searching Sekuensial terurut

Analisa

• Data tersimpan dalam keadaan terurut • Pencarian secara ascending atau descending • Alamat terakhir(P1) dari larik (P) adalah

• 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)

– 0<= P1 <= P‐1

Flowchart Searching Sekuensial Mulai AddrÍ0 Data tdk Ada

AddrÍAddr+1 M(addr) Isi ?

Y

Data>M(addr) ?

T

Selesai

Y T

M(addr)= data ?

Y

Data Ada

T

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=?

contoh M

data

0

15

1

20

2

25

3

30

4

50

5

60

6

75

7

100

1 2 3 4 5

• Dicari data=50 1. Addr=0, m(addr) isi data ?Î Y 2 M(addr)=data ? Î 2. M(addr) data ? Î T (15<>50) T (15<>50) 3. M(addr)>data ? ÎY (50>15) 4. Addr=addr+1 (addr=1) 5. Ulangi langkah 1 Jika di jalankan maka akan memerlukan 5 langkah untuk menemukan data 50, yaitu dr 15,20,25,30 dan 50

Binary Search • Syarat : data sudah terurut

15

7/5/2010

Analisa

Algoritma Binary Search

• Dalam binary search, jumlah perbandingan yang di perlukan untuk mencari satu elemen dalam list dalah tidak lebih dari log2n, dimana n adalah ukuran list n adalah ukuran list . • Dengan demikian algoritma binary search mempunyai kompleksitas waktu O(n *( log2n)) • Ukuran efisiens :

int BinSearch(int *arr, int val, int N) { int low = 0; int high = N – 1; int mid; while ( low <= high ) { mid = ( low + high g ))/2;; if (arr[mid]==val) {return 1; } else if (arr[mid] < val) { low = mid + 1; } else { high = mid – 1;} } return 0; }

– max=2log n mis n=16 maka 4 langkah – min=1

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

Flowchart Binary Search Mulai

L=Lower U=Upper P1=ukuran Memori/Larik t=tengah

LÍ0 UÍp1 UÍt-1 L<=U ?

T

Selesai

Y T

Data>M(t) ?

T

M(addr)= data ?

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

Data tdk Ada

Y tÍ(L+U)/2

LÍt+1

contoh

Y

Data Ada

x= 2 7 9 12 14 20 36 76 100 125 i= 1 2 3 4 5 6 7 8 9 10 lower=1 upper=10 t=(lower+upper) div 2 = 5 dengan x[5]=14

a=36

t=5

x= 2 7 9 12 14 20 36 76 100 125 i= 1 2 3 4 5 6 7 8 9 10 a>x[t] maka lower = 6 Lower=t+1 upper=10 t=16/2=8 dengan x[8]=76

a=36

t=16/2=8

Dicari a=36

16

7/5/2010

x= 2 7 9 12 14 20 36 76 100 125 i= 1 2 3 4 5 6 7 8 9 10 karena a<x[8], lower=6 upper=t‐1=7 t=6 dengan x[6]=20

a=36

upper=t-1

t=13/2=6

x= 2 7 9 12 14 20 36 76 100 125 i= 1 2 3 4 5 6 7 8 9 10 karena a>x[6] , lower=t+1=6+1=7 upper=7 t=7 dengan x[7]=36 t=7 dengan x[7]=36

a=36

Upper=t+1

t=7

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

karena a=x[7] , Data Di temukan

Interpolation Search • Dikenal sebagai estimated entry search • Data sudah terurut • Mirip Binary Search tetapi lebih canggih sedikit (lihat flowchart) diki (lih fl h ) • Pada tiap langkah pencarian algoritma membuat suatu tebakan/perkiraan (Interpolasi)

Perbandingan Analisa

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 n. membuat 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.

• Mirip dengan hal sebelumnya, interpolation perlu melakukan langkah kompleks dalam loop , walaupun dia memerlukan lebih sedikit waktu di banding binary search waktu 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

17

7/5/2010

Interpolation Sequential Search

Flowchart Interpolation

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

L=Lower U=Upper P1=ukuran Memori/Larik t=tengah

Mulai LÍ0 UÍp1 UÍt-1

Data tdk Ada

T

L<=U ?

Y

LÍt+1

t ←L+

data − M ( L) * (U − L) M (U ) − M ( L)

Selesai

Y T

T

Data>M(t) ?

Y

M(addr)= data ?

Data Ada

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

Algoritma

Contoh searching SS,BS,IS

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 ***/ }

• Data = 5,10,20,28,40,42,50,60,80,100,1000 • Cari 100,800,13 dan 40 dengan Sekuensial, Binary dan Interpolation Binary dan Interpolation i

0

1

2

3

4

5

6

7

8

9

10

N

5

10

20

28

40

42

50

60

80

100

1000

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

Sekuensial Search 100,800,13,40 5 0 1 10 2 20 3 28 0 4 40 5 42 6 50 7 60 8 80 9 100 10 1000

step 1

addr 0

M(addr)

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

Data:M(Addr) 100

800

13

40

5

>

>

>

>

2

1

10

>

>

>

>

3

2

20

>

>

<

>

4

3

28

>

>

>

5

4

40

>

>

=

6

5

42

>

>

7

6

50

>

>

8

7

60

>

>

Jmlh step

3

5

9

8

80

>

>

10

9

100

=

>

10

11

10

1000

<

11

5 0 1 10 2 20 3 28 0 4 40 5 42 6 50 7 60 8 80 9 100 10 1000

Data

step

L

U

t

M(t)

100

1

0

10

5

42

>

2

5+1=6

10

8

80

>

3

8+1=9

10

9

100

=

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

800

Data:M(t)

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

18

7/5/2010

BS Lanjutan 5 0 1 10 2 20 3 28 0 4 40 5 42 6 50 7 60 8 80 9 100 10 1000

Interpolasi Search

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

40

5 0 1 10 2 20 3 28 0 4 40 5 42 6 50 7 60 8 80 9 100 10 1000

stop

1

0

10

5

42

<

2

0

5‐1=4

2

20

>

3

2+1=3

4

4

40

=

data − M ( L) * (U − L) M (U ) − M ( L)

step

L

U

100

1

0

10

1

10

>

2

2

10

3

28

>

3

4

10

5

42

>

4

6

10

7

60

>

5

8

10

9

100

=

1

0

10

8

80

>

2

9

10

10

1000

3

9

9

10

800

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

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

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

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

Interpolasi Search 5 0 1 10 2 20 3 28 0 4 40 5 42 6 50 7 60 8 80 9 100 10 1000

t ←L+

Data

t ←L+

data − M ( L) * (U − L) M (U ) − M ( L)

Data

step

L

U

40

1

0

10

2

2

10

1

0

10

1

2

2

10

3

4

10

13

Data:M(t)

< stop

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

Perbandingan Metode M(t)

Data:M(t)

10

>

Data Cari 1

M(t)

Langkah SS

BS

IS

stop

100

10

3

5

10

>

800

11

5

3

3

28

>

13

3

3

2

4

40

=

40

5

3

3

Rata‐rata =∑/N

29/4

14/4

13/4

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

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. • Solusi

Jadi metode yang terbaik untuk kasus diatas adalah IS source

simulasi

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

19

2010

Recommend Documents