METODE DEVIDE AND CONQUER (DANDC) Di dalam metode ini, kita mempunyai suatu fungsi untuk menghitung input. Kemudian n input tersebut dipartisi menjadi k subset input yang berbeda (1< k ≤ n) → k subproblem k subproblem → k subsolusi → solusi Bentuk Umum dari Proses Metode DANDC :
Jika subproblem masih relatif cukup besar, maka metode DANDC dapat digunakan lagi untuk keadaan tersebut. Pemakaian ulang DANDC dinyatakan dengan teknik rekursif. Pemecahan menjadi k subproblem ini menunjukkan bahwa ia mempunyai sifat yang sama dengan problem aslinya (awalnya). Algoritmanya secara umum : PROCEDURE DANDC(p,q) GLOBAL n,A(1:n); INTEGER m.p.q IF SMALL(p,q) THEN G(p,q) ELSE M ← DIVIDE(p,q) COMBINE(DANDC(p,m),DANDC(m+1,q)) ENDIF END DANDC
Metode Devide And Conquer ( DANDC) SMALL(p,q) adalah fungsi yang bernilai boole yang menentukan apakah input q-p+1 berukuran cukup kecil ∋ solusi dapat dihitung tanpa pemecahan. Jika demikian halnya, maka fungsi G(p,q) yang dipanggil. Pada
keadaan
lain
fungsi
DIVIDE(p,q)
yang
dipanggil,
Fungsi
DIVIDE(p,q)
menghasilkan integer yang menguraikan input menjadi 2 bagian. Misal m = DIVIDE(p,q), maka input dipecah ∋ A(p:m) dan A(m+1,q) Metode DANDC biasa dipakai pada searching dan sorting.
SEARCHING Menentukan Bilangan Max dan Min Sebelum kita lihat penggunaan metode DANDC-nya, maka kita lihat terlebih dahulu algoritmanya secara iteratif sebagai berikut : PROCEDURE STRAITMAXMIN INTEGER i,n max ← min ← A(1) For i ← 2 TO n DO IF A(i) > max THEN max ← A(i) ELSE IF A(i) < min THEN min ← A(i)
………bagian perbandingan ………bagian perbandingan
ENDIF ENDIF REPEAT END STRAITMAXMIN
Procedure STRAITMAXMIN tersebut akan menghasilkan 3 keadaan, yakni: 1. Best Case, bila datanya tersusun menaik, dengan banyak perbandingan adalah n-1 2. Worst Case, bila datanya tersusun menurun, dengan banyak perbandingan adalah 2(n-1) 3. Average Case, bila datanya tidak tersusun menaik ataupun menurun, dengan banyak perbandingan adalah 3(n-1)/2
Bila pada procedure STRAITMAXMIN tersebut, bagian perbandingannya diubah menjadi : IF A(i) > max THEN max ← A(i) ENDIF
Logika dan Algoritma – Yuni Dwi Astuti, ST
2
Metode Devide And Conquer ( DANDC) IF A(i) < min THEN min ← A(i) ENDIF Maka Best Case = Worst Case = Average Case = 2(n-1) Algoritmanya secara rekursif (dengan metode DANDC) PROCEDURE MAXMIN(i,j,fmax,fmin) INTEGER i,j; GLOBAL n,A(1:n) CASE : i=j
; fmax ← fmin ← A(i)
: i=j-1 ; IF A(i) < A(j) THEN fmax ← A(j); fmin ← A(i) ELSE fmax ← A(i); fmin ← A(j) ENDIF : ELSE mid ← ⎣ (i+j)/2 ⎦ CALL MAXMIN(i,mid,gmax,gmin) CALL MAXMIN(mid+1,j,hmax,hmin) fmax ← MAX(gmax,hmax) fmin ← MIN(gmin,hmin) ENDCASE END MAXMIN
Contoh : A = { 22, 13, -5, -8, 15, 60, 17, 31, 47 }, Maka simulasi dari procedure MAXMIN tersebut adalah :
Logika dan Algoritma – Yuni Dwi Astuti, ST
3
Metode Devide And Conquer ( DANDC) Jadi outputnya adalah max = 60 dan min = -8 Jumlah perbandingan elemennya, yang direpresentasikan oleh T(n) adalah :
T(n)
T( ⎣ n/2 ⎦ ) +T( ⎡ n/2 ⎤ ) + 2
;n>2
1
;n=2
0
;n=1
untuk n ≈ power value dari 2 = 2k dan k integer positif, maka : T(n)
= 2 T(n/2) + 2 = 2 (2 T(n/4) + 2) + 2 = 4 T(n/4) + 4 + 2 = 22 T(n/22) + 22 + 2 = 23 T(n/23) + 23 + 22 + 2 . . . = 2k-1 T(2) + 2k-1 + 2k-2 + … + 23 + 22 + 2 = 2k-1 +2k - 2 = 3n/2 - 2
Jadi T(n) = Ο(n)
SORTING Untuk mengurutkan barisan n input elemen yang ditempatkan dalam suatu array. Urutan yang diinginkan adalah urutan yang tidak turun (non decreasing). Contoh barisan dengan urutan : 1. Menaik
: 5, 8, 10, 12, 15, 16
2. Menurun
: 20, 17, 15, 14, 12, 10
3. Tidak turun
: 5, 9, 10, 12, 12, 15, 16
4. Tidak naik
: 16, 15, 15, 12, 10, 8
Dari Metode Sorting yang ada, akan dibahas metode merge sort dan quick sort.
Logika dan Algoritma – Yuni Dwi Astuti, ST
4
Metode Devide And Conquer ( DANDC) Merge Sort Algoritma dari Merge Sort terdiri dari dua prosedur, yakni prosedur MERGESORT dan prosedur MERGE. Kedua prosedur tersebut tidak dapat dipisahkan satu dengan yang lainnya (terintegrasi). PROCEDURE MERGESORT(low,high) INTEGER low,high IF low < high THEN mid ← ⎣ (low + high) / 2 ⎦ CALL MERGESORT(low,mid) CALL MERGESORT(mid+1,high) CALL MERGE(low,mid,high) ENDIF END MERGESORT PROCEDURE MERGE(low,mid,high) INTEGER h,I,j,k,low,mid,high GLOBAL A(low:high); LOCAL B(low:high) h ← low; j ← mid + 1; i ← low WHILE h ≤ mid AND j ≤ high DO IF A(h) ≤ A(j) THEN B(i) ← A(h); h ← h+1 ELSE B(i) ← A(j); j ← j+1 ENDIF i ← i+1 REPEAT IF h > mid THEN FOR k ← j TO high DO B(i) ← A(k); i ← i+1 REPEAT ELSE FOR k ← h TO mid DO B(i) ← A(k); i ← i+1 REPEAT ENDIF FOR k ← low TO high DO
Logika dan Algoritma – Yuni Dwi Astuti, ST
5
Metode Devide And Conquer ( DANDC) B(k) ← A(k) REPEAT END MERGE
Contoh : A(1:10) yakni : A = { 310, 285, 179, 652, 351, 423, 861, 254, 450, 520 }
Representasi di dalam tree dari CALL MERGESORT sbb :
Representasi di dalam tree dari CALL MERGE sbb :
T(n) = Ο(n 2log n)
Logika dan Algoritma – Yuni Dwi Astuti, ST
6
Metode Devide And Conquer ( DANDC) Quick Sort Algoritma Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTITION dan prosedur QUICKSORT. PROCEDURE QUICKSORT(p,q) IF p < q THEN j ← q+1 CALL PARTITION(p,j) CALL QUICKSORT(p,j-1) CALL QUICKSORT(j+1,q) ENDIF END QUICKSORT
PROCEDURE PARTITION(m,p) INTEGER m,p,i; GLOBAL A(m-1,p) V ← A(m); i ← m LOOP LOOP i ← i+1 UNTIL A(i) ≥ V REPEAT LOOP p ← p-1 UNTIL A(p) ≤ V REPEAT IF i < p THEN CALL INTERCHANGE(A(i),A(p)) ELSE EXIT REPEAT A(m) ← A(p); A(p) ← V END PARTITION
Contoh : Suatu array A berisi elemen-elemen : 65
70
75
80
85
60
55
50
45
1
2
3
4
5
6
7
8
9
Logika dan Algoritma – Yuni Dwi Astuti, ST
7
Metode Devide And Conquer ( DANDC) Hasil tracenya adalah sebagai berikut : i
p
1
2
3
4
5
6
7
8
9
10
65
70
75
80
85
60
55
50
45
+∞
2
9
65
45
75
80
85
60
55
50
70
+∞
3
8
65
45
50
80
85
60
55
75
70
+∞
4
7
65
45
50
55
85
60
80
75
70
+∞
5
6
65
45
50
55
60
85
80
75
70
+∞
6
5
60
45
50
55
65
85
80
75
70
+∞
5
4
55
45
50
60
65
85
80
75
70
+∞
4
3
50
45
55
60
65
85
80
75
70
+∞
3
2
45
50
55
60
65
85
80
75
70
+∞
10
9
55
45
50
60
65
70
80
75
85
+∞
9
8
50
45
55
60
65
70
75
80
85
+∞
8
7
45
50
55
60
65
70
75
80
85
+∞
Analisisnya : Worst Case = Ο(n2) Average Case = Ο(n log n)
Logika dan Algoritma – Yuni Dwi Astuti, ST
8
