Bagian 5: Divide and Conquer

S1-Informatika UNDIP

2026

Sejarah

• Divide and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes.

​

• Sekarang strategi tersebut menjadi strategi fundamental di dalam ilmu komputer dengan nama Divide and Conquer.

Definisi

• Divide: membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (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.

• Obyek permasalahan yang dibagi seperti apa? (instances yang berukuran n, bergantung pada masalahnya )

​

• Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif.

Skema Umum Algoritma Divide and Conquer

Jika pembagian selalu menghasilkan dua upa-masalah yang berukuran sama:

Contoh-contoh masalah

1. Mencari Nilai Minimum dan Maksimum (MinMaks)

​

Persoalan: Misalkan diberikan tabel A yang berukuran n elemen dan sudah berisi nilai integer.

Carilah nilai minimum dan nilai maksimum sekaligus di dalam tabel tersebut.

​

Penyelesaian dengan Algoritma Brute Force

T(n) = (n – 1) + (n – 1) = 2n – 2 = O(n)

Penyelesaian dengan Divide and Conquer

• MinMaks1 secara brute force :

T(n) = 2n – 2

​

• MinMaks2 secara divide and conquer:

T(n) = 3n/2 – 2

​

• Perhatikan: 3n/2 – 2 < 2n – 2 , n ≥ 2.

​

• Kesimpulan: algoritma MinMaks lebih mangkus dengan metdoe Divide and Conquer.

2. Algoritma Pengurutan dengan� Metode Divide and Conquer

(a) Merge Sort

Algoritma:

1. Untuk kasus n = 1, maka tabel A sudah terurut dengan sendirinya (langkah SOLVE).

​

2. Untuk kasus n > 1, maka

(a) DIVIDE: bagi tabel A menjadi dua bagian,

bagian kiri dan bagian kanan, masing-masing

bagian berukuran n/2 elemen.

(b) CONQUER: Secara rekursif, terapkan

algoritma D-and-C pada masing-masing

bagian.

(c) MERGE: gabung hasil pengurutan kedua

bagian sehingga diperoleh tabel A yang terurut.

(b) Insertion Sort

Prosedur Merge dapat diganti dengan prosedur penyisipan sebuah elemen

pada tabel yang sudah terurut (lihat algoritma Insertion Sort versi iteratif).

c. Quicksort

• Algoritma pengurutan Quicksort merupakan algoritma pengurutan yang terkenal dan tercepat (sesuai namanya).

​

• Quicksort ditemukan oleh Tony Hoare tahun 1959 dan dipublikasikan tahun 1962.

​

• Quicksort merupakan algoritma pengurutan secara divide and conquer, dan termasuk ke dalam pendekatan sulit membagi, mudah menggabung (hard split/easy join)

24

25

• Di dalam Quicksort, larik A dibagidua (istilahnya: dipartisi) menjadi dua buah upalarik, A1 dan A2, sedemikian sehingga:

​

semua elemen di A1 ≤ semua elemen di A2.

• Terdapat beberapa varian algoritma Quicksort. Versi orisinal adalah dari Hoare seperti di bawah ini:

​

Misalkan larik A akan diurut menaik (ascending order).

​

Teknik mempartisi larik menjadi dua bagian:

(i) pilih x ∈ { A[1], A[2], ..., A[n] } sebagai pivot,

(ii) pindai larik dari kiri sampai ditemukan elemen A[p] ≥ x

(iii) pindai larik dari kanan sampai ditemukan elemen A[q] ≤ x

(iv) pertukarkan A[p] ⇔ A[q]

(v) ulangi (ii), dari posisi p + 1, dan (iii), dari posisi q – 1 , sampai kedua pemindaian bertemu di tengah larik (p ≥ q)

26

27

Contoh 6. Misalkan larik A berisi elemen-elemen berikut:

​

8 1 4 6 9 3 5 7

​

Misalkan pivot = 6 (elemen tengah larik). Langkah-langkah partisi adalah sbb:

​

(i): 8 1 4 6 9 3 5 7

pivot

​

→ ←

(ii) & (iii): 8 1 4 6 9 3 5 7

↑p ↑q

​

(iv): 5 1 4 6 9 3 8 7

↑ ↑

tukar

awal pindai

awal pindai

28

→ ←

(ii) & (iii): 5 1 4 6 9 3 8 7

↑p ↑q

​

(iv): 5 1 4 3 9 6 8 7

↑ ↑

​

← →

(ii) & (iii): 5 1 4 3 9 6 8 7

↑q ↑p (q < p, berhenti)

​

Hasil partisi pertama:

​

kiri: 5 1 4 3 ( < 6)

kanan: 9 6 8 7 ( ≥ 6)

tukar

awal pindai

awal pindai

29

Teruskan partisi untuk setiap bagian sampai berukuran satu elemen:

Versi kedua Quicksort: Partisi sedemikian rupa sehingga elemen-elemen larik kiri ≤ pivot dan elemen-elemen larik kanan ≥ dari pivot.

​

​

​

p = pivot = elemen pertama.

​

Contoh:

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

​

​

Partisi 2, 3, 1, 4, 5, 8, 9, 7

31

pivot

pivot

semua ≤ pivot

semua ≥ pivot

→ ←

5 3 1 9 8 2 4 7

↑p ↑q

5 3 1 4 8 2 9 7

​

5 3 1 4 8 2 9 7

↑p ↑q

5 3 1 4 2 8 9 7

​

5 3 1 4 2 8 9 7

↑q ↑p 🡪 stop sebab p > q

2 3 1 4 5 8 9 7

32

Contoh 7 (Levitin, 2003):

tukar

tukar posisi pivot dengan A[q]

2 3 1 4 5 8 9 7

→ ← → ←

2 3 1 4 8 9 7

↑p ↑q ↑p ↑q

2 1 3 4 8 7 9

​

2 1 3 4 8 7 9

↑q ↑p ↑q ↑p

1 2 3 4 7 8 9

1 3 4 7 9

↑q ↑p

4

Terurut:

1 2 3 4 5 7 8 9

​

​

33

• Cara pemilihan pivot (khusus pada Quicksort versi 1):

​

1. Pivot = elemen pertama/elemen terakhir/elemen tengah larik

​

• Pivot dipilih secara acak dari salah satu elemen larik.

3. Pivot = elemen median larik

​

• Cara pemilihan pivot menentukan kompleksitas algoritma Quicksort

​

34

Kompleksitas Algoritma Quicksort:

1. Kasus terbaik (best case)

• Kasus terbaik terjadi bila pivot adalah elemen median larik sehingga larik selalu terbagi menjadi dua upalarik yang berukuran relatif sama setiap kali proses partisi.

35

2. Kasus terburuk (worst case)

​

• Kasus ini terjadi bila pada awalnya larik sudah terurut (menaik atau menurun), dan pivot selalu elemen pertama larik (elemen pertama merupakan elemen maksimum atau elemen minimum larik).

​

• Akibatnya, proses partisi menghasilkan ketidakseimbangan ukuran, upalarik pertama berukuran satu elemen, upalarik kedua berukuran n – 1 elemen.

36

3. Kasus rata-rata (average case)

​

• Kasus ini terjadi jika pivot dipilih secara acak dari elemen-elemen larik, dan peluang setiap elemen dipilih menjadi pivot adalah sama.

​

• Kompleksitas algoritma Quicksort untuk kasus rata-rata:

T_avg(n) = O(n ²log n).

37

5. Teorema Master

​

• Teorema Master dapat digunakan untuk menentukan notasi asimptotik kompleksitas waktu yang berbentuk relasi rekurens dengan mudah tanpa harus menyelesaikannya secara iteratif.

​

• Misalkan T(n) adalah fungsi monoton menaik yang memenuhi relasi rekurens:

T(n) = aT(n/b) + cn^d

yang dalam hal ini n = b^k , k = 1, 2, …, a ≥ 1, b ≥ 2, c dan d ≥ 0, maka

​

T(n) adalah

​

38

Contoh 10: Pada algoritma Mergesort/Quick Sort,

​

​

​

Menurut Teorema Master, T(n) = aT(n/b) + cn^d, diperoleh a = 2, b = 2, d = 1, dan memenuhi a = b^d (yaitu 2 = 2¹) maka relasi rekurens:

T(n) = 2T(n/2) + cn

memenuhi case 2 (jika a = b^d)

​

sehingga

T(n) = O(n log n)

​

Catatan: basis logaritma tidak penting di dalam notasi Big-O, sebab fungsi logaritma tumbuh pada laju yang sama untuk sembarang basis.

39