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]
Data Sumber : [4, 8, 7, 3, 1, 2, 6, 5]Index : 1 2 3 4 5 6 7 8
• Ambil data index 4 (3), bandingkan dengan data index sebelumnya (4,7,8) dan susunanya menjadi [3, 4, 7, 8]
Data Sumber : [4, 7, 8, 3, 1, 2, 6, 5]Index : 1 2 3 4 5 6 7 8
• Ambil data index 5 (1), bandingkan dengan data index sebelumnya (3,4,7,8) dan susun menjadi [1, 3, 4, 7, 8]
Data Sumber : [3, 4, 7, 8, 1, 2, 6, 5]Index : 1 2 3 4 5 6 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]
Data Sumber : [1, 3, 4, 7, 8, 2, 6, 5]Index : 1 2 3 4 5 6 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]
Data Sumber : [1, 2, 3, 4, 7, 8, 6, 5]Index : 1 2 3 4 5 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
Data Sumber : [1, 2, 3, 4, 6, 7, 8, 5]Index : 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].
• Untuk i=3 (7), cari dan bandingkan dengan data lainnya yang terkecil disebelah kanannya, ditemukan pada i=4 (3), lalu tukar nilai datanya pada posisi index‐nya data i[3] ditukar
Data : [1, 2, 7, 3, 8, 4, 6, 5] index 1 2 3 4 5 6 7 8
datanya pada posisi index nya data i[3] ditukar ke i[4], sehingga menjadi [1, 2, 3, 7, 8, 4, 6, 5].
7/5/2010
7
• Untuk i=4 (7), cari dan bandingkan dengan data lainnya yang terkecil disebelah kanannya, ditemukan pada i=6 (4), lalu tukar nilai datanya pada posisi index‐nya data i[4] ditukar
Data : [1, 2, 3, 7, 8, 4, 6, 5] index 1 2 3 4 5 6 7 8
datanya pada posisi index nya data i[4] ditukar ke i[6], sehingga menjadi [1, 2, 3, 4, 8, 7, 6, 5].
• Untuk i=5 (8), cari dan bandingkan dengan data lainnya yang terkecil disebelah kanannya, ditemukan pada i=8 (5), lalu tukar nilai datanya pada posisi index‐nya data i[5] ditukar
Data : [1, 2, 3, 4, 8, 7, 6, 5] index 1 2 3 4 5 6 7 8
datanya pada posisi index nya data i[5] ditukar ke i[8], sehingga menjadi [1, 2, 3, 4, 5, 7, 6, 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 data i[6] ditukar
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].
• 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 data i[6] ditukar
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;
Analisa Selection Sort
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
Analisa Selection Sort
• 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[3] <L[4], false, jadi urutan tetap 8, 7, 4, 3, 1, 2, 6, 5
L[4] <L[5], false, jadi urutan tetap 8, 7, 4, 3, 1, 2, 6, 5
L[5] <L[6], true, jadi urutan berubah 8, 7, 4, 3, 2, 1, 6, 5
L[6] <L[7], true, jadi urutan berubah 8, 7, 4, 3, 2, 6, 1, 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[4]<L[5], false,jadi urutan tetap 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[6]<L[7], true,jadi urutan berubah 8, 7, 4, 3, 6, 5, 2, 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
L[2]<L[3], false,jadi urutan tetap 8, 7, 4, 3, 6, 5, 2, 1
L[3]<L[4], false,jadi urutan tetap 8, 7, 4, 3, 6, 5, 2, 1
L[4]<L[5], true,jadi urutan berubah 8, 7, 4, 6, 3, 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
L[7]<L[8], 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
L[5]<L[6],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
L[6]<L[7], false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
L[7]<L[8],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
8, 7, 6, 5, 4, 3, 2, 1
i=5
L[1]<L[2],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
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
L[4]<L[5] 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
L[4]<L[5],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
L[5]<L[6], false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
L[6]<L[7],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
L[7]<L[8],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
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
L[4]<L[5] 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
L[4]<L[5], false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
L[5]<L[6],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
L[6]<L[7],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
L[7]<L[8],false,jadi urutan tetap 8, 7, 6, 5, 4, 3, 2, 1
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
j=6‐> tidak berubah
i:1
j=2‐> tidak berubahj=3‐> tidak berubah
j=4‐> tidak berubah
j=5‐> tidak berubahj=6‐> tidak berubah
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;
}}
Algoritma mergesort 2dalam 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 mergesort 2dalam 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++;}}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
Algoritma Merge sort untuk2 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 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
Algoritma Merge sort untuk2 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; }
}
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 =
Data>M(addr) maka L=t+1 dan U tetap
Data<M(addr) maka L tetap dan U=t-1
Interpolasi Search
51020280
0123
Data step L U M(t) Data:M(t)
100 1 0 10 1 10 >
2 2 10 3 28 >
)(*)()(
)( LULMUMLMdataLt −
−−
+←
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
Data>M(addr) maka L=t+1 dan U tetap
Data<M(addr) maka L tetap dan U=t-1
=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
)(*)()(
)( LULMUMLMdataLt −
−−
+←
40425060801001000
456789
10
13 1 0 10 1 10 >
2 2 10 3 28 >
3 4 10 4 40 =
Data>M(addr) maka L=t+1 dan U tetap
Data<M(addr) maka L tetap dan U=t-1
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