BAB
I
PENDAHULUAN
Divide
and Conquer (D&C) adalah algoritma pemrograman yang
melakukan pemecahan masalah menjadi dua
sub-masalah secara rekursif
sampai setiap sub-masalah cukup
sederhana untuk diselesaikan
secara langsung. Tiap solusi
dari masing-masing sub-masalah akan digabungkan untuk
mendapatkan solusi dari masalah utama
tersebut. Algoritma D&C
menjadi basis dari algoritma-algoritma efisien untuk
masalah-masalah seperti sorting
(quick sort, merge
sort) dan transformasi diskrit Fourier.
Dasar
dari algoritma ini dikemukakan pertama kali oleh Anatolii Karatsuba Alexeevich pada
tahun 1960 sebagai algoritma perkalian
dua buah angka
n-digit dengan kompleksitas algoritma O(n.2log3). Algoritma ini sekarang dikenal
dengan nama Algoritma
Karatsuba, membuktikan bahwa ada
algoritma perkalian yang
lebih cepat dari O(n2)
[Kolmogorov, 1956]. Buah
pikiran Kolmogorov dan penemuan Karatsuba kemudian membantu merintis
penelitian performa algoritma.
Algoritma Divide
and Conquer secara
natural diimplementasikan
secara rekursif sebagai
pemanggilan prosedur dalam dirinya sendiri. Sub-masalah-sub-masalah
akan dikerjakan dalam
procedure-call stack. Setiap
sub-masalah yang merupakan hasil
pembagian dari masalah utama
biasanya dibagi tanpa
menimbulkan overlapping sehingga tidak
ada pengerjaan redundan.
Semuanya akan dimasukkan ke dalam
stack dan dikerjakan mulai dari submasalah terkecil. Tetapi, selain
pengimplementasian rekursif,
dengan metode lain sub-masalah yang
dibentuk dapat juga disimpan dalam
struktur data yang
dibuat sendiri seperti
stack, queue, dan priority
queue. Pengimplementasian non-rekursif ini menambah kebebasan dalam
pemilihan sub-masalah mana yang akan dipecahkan
berikutnya. Konsep ini
dikembangkan dalam
algoritma-algoritma seperti Breadth First
Search dan optimalisasi Branch and Bound.
Terdapat
dua metode sorting paling umum yang dipakai dalam implementasi algoritma Divide
and Conquer, yaitu quick sort
dan merge sort
(di luar kedua
ini masih ada metode
lain seperti (insertion sort).
Keduanya berfungsiuntuk mengurutkan
sebuah array berisi
nilai-nilai yang acak dengan
cara mengurutkan sebagian
dari array terlebih dahulu sebelum mengurutkan semua array secara
keseluruhan.Pembahasan mendalam akan
menjelaskan lebih, tetapipada saat ini yang akan dibahas adalah
metode sorting merge sort dan heap sort.
BAB
II
PEMBAHASAN
2.1. Merge Sort
Merge
sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk
memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan
untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar.
Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.
(id.wikipedia.org)
Algoritma
pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer
yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian
menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian
pertama merupakan setengah (jika data genap) atau setengah minus satu (jika
data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk
masing-masing blok sampai hanya terdiri dari satu data tiap blok.
Setelah
itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data
pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1
dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah
digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai
menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan
metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.
Dengan
hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola
divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.
1.
Divide
Memilah elemen – elemen dari rangkaian
data menjadi dua bagian.
2.
Conquer
Conquer setiap bagian dengan memanggil
prosedur merge sort secararekursif
3.
Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif
untuk mendapatkanrangkaian data berurutan
Proses
rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian
yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen
tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
2.1.1. Contoh 1
Contoh penerapan atas
sebuah larik/array sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2}
adalah sebagai berikut:
·
pertama kali larik tersebut dibagi menjadi
dua bagian, {3, 9, 4} dan {1, 5, 2}
·
Kedua larik kemudian diurutkan secara
terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}
·
Sebuah larik baru dibentuk yang sebagai
penggabungan dari kedua larik tersebut {1}, sementara nilai-nilai dalam masing
larik {3, 4, 9} dan {2, 5} (nilai 1 dalam elemen larik ke dua telah dipindahkan
ke larik baru)
·
langkah berikutnya adalah penggabungan
dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya.
·
{1, 2} <-> {3, 4, 9} dan {5}
·
{1, 2, 3} <-> {4, 9} dan {5}
·
{1, 2, 3, 4} <-> {9} dan {5}
·
{1, 2, 3, 4, 5} <-> {9} dan {null}
·
{1, 2, 3, 4, 5, 9} <-> {null} dan
{null}
2.1.2. Contoh 2
Inputan datanya adalah sebagai
berikut:
Membagi rangkaian menjadi dua
bagian:
Kedua bagian tersebut bisa dinamai A
dan B
Membagi A menjadi dua bagian:
Membandingkannya kemudian
dikombinasikan:
7 dan 2 kemudian tukar posisi karena 2 < 7
Membagi B menjadi dua bagian:
Membandingkannya kemudian
dikombinasikan:
6 dan 5 kemudian tukar posisi karena 5 < 6
Membandingkan A dan B
Kemudian dilakukan proses
membandingkan lagi antara angka di A dengan B.
Pembandingan biasanya dimulai dari
angka terdepan di masing-masing bagian.
Mengkombinasikan A dengan B.
Sehingga menjadi: 2<5 span="">
2.2. Heap Sort
2.2.1. Pengertian Heap
Pohon
heap adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap
yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih
besar atau sama dengan nilai yang tersimpan di simpul B. Hal ini mengakibatkan
elemen dengan nilai terbesar selalu berada pada posisi akar, dan heap ini
disebut max heap. (Bila perbandingannya diterbalikkan yaitu elemen terkecilnya
selalu berada di simpul akar, heap ini disebut adalah min heap). Karena itulah,
heap biasa dipakai untuk mengimplementasikan priority queue. Operasi-operasi
yang digunakan untuk heap adalah Heap Sort
Heap
Sort adalah sebuah algoritma pengurutan yang paling lambat dari algoritma yang
memiliki kompleksitas O(n log n). Tetapi tidak seperti algoritma Merge Sort dan
Quick Sort, algoritma Heap Sort tidak memerlukan rekursif yang besar atau
menggunakan banyak tabel (array). Oleh karena itu, Heap Sort adalah pilihan
yang baik untuk sebuah kumpulan data yang besar.
Algoritma
ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah
daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap
sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut
heap.
Algoritma
ini dimulai dengan membangun sebuah array heap dengan membangun tumpukan dari
kumpulan data, lalu memindahkan data terbesar ke bagian belakang dari sebuah
tabel hasil. Setelah itu, array heap dibangun kembali, kemudian mengambil
elemen terbesar untuk diletakkan di sebelah item yang telah dipindahkan tadi.
Hal ini diulang sampai array heap habis.
Jadi
secara umum, algoritma ini memerlukan dua buah tabel; satu tabel untuk
menyimpan heap, dan satu tabel lainnya untuk menyimpan hasil. Walaupun lebih
lambat dari Merge Sort atau Quick Sort, algoritma ini cocok untuk digunakan pada
data yang berukuran besar.
Perbandingan kompleksitas
jenis-jenis heap
Tabel 1. Perbandingan
macam-macam heap
1.
Algoritma Heapify
Algoritma
Heapify adalah membangun sebuah heap dari bawah ke atas, secara berturut-turut
berubah ke bawah untuk membangun heap. Permasalahan pertama yang harus kita
pertimbangkan dalam melakukan operasi heapify adalah dari bagian mana kita
harus memulai. Bila kita mencoba operasi heapify dari akar maka akan terjadi
operasi runut-naik seperti algoritma bubble sort yang akan menyebabkan
kompleksitas waktu yang ada akan berlipat ganda. Sebuah versi lain adalah
membangun heap secara atas-bawah dan berganti-ganti ke atas untuk secara
konseptual lebih sederhana untuk ditangani. Versi ini mulai dengan sebuah heap
kosong dan secara berturut-turut memasukkan data. Versi lainnya lagi adalah
dengan membentuk pohon heap-pohon heap mulai dari subtree-subtree yang paling bawah.
Jika subtree-subtree suatu simpul sudah membentuk heap maka pohon dari simpul
tersebut mudah dijadikan pohon heap dengan mengalirkannya ke bawah. Setelah
diuji, maka ide yang paling efisien adalah versi yang terakhir, yang
kompleksitas algoritmanya pada kasus terburuk adalah O(n), sedangkan versi
membentuk heap tree-heap tree dari atas ke bawah kompleksitas nya O(n log n).
Jadi,
algoritma utama heapify adalah melakukan iterasi mulai dari internal simpul
paling kanan bawah(pada representasi larik, adalah elemen yang berada di indeks
paling besar) hingga akar, kemudian kearah kiri dan naik ke level di atasnya,
dan seterusnya hingga mencapai akar (sebagai larik [0..N-1]). Oleh karena itu,
iterasi dilakukan mulai dari j= N/2 dan berkurang satu-satu hingga mencapai
j=0. Pada simpul internal tersebut, pemeriksaan hanya dilakukan pada simpul
anaknya langsung (tidak pada level-level lain di bawahnya). Pada saat iterasi
berada di level yang lebih tinggi, subtreesubtree selalu sudah membentuk heap.
Jadi, kasus yang paling buruk adalah restrukturisasi hanya akan mengalirkan
simpul tersebut kearah bawah. Dengan demikian, heapify versi ini melakukan
sebanyak N/2 kali iterasi, dan pada kasus yang paling buruk akan melakukan
iterasi sebanyak ²log(N) kali.
2.
Algoritma Remove
Algoritma
remove ini menukar akar (yang berisi nilai maksimum) dari heap dengan elemen
terakhir. Secara logika, simpul yang berada paling kanabawah dipindahkan ke
akar untuk menggantikan simpul akar yang akan diambil.
3.
Algoritma Reheapify
Algoritma
reheapify ini melakukan pembuatan ulang heap dari atas ke bawah seperti halnya
iterasi terakhir dari algoritma metoda heapify. Perbedaan antara metode heapify
dengan metode reheapify ada pada iterasi yang dilakukan oleh kedua algoritma
tersebut. Algoritma metode reheapify ini hanya melakukan iterasi terakhir dari
algoritma heapify. Hal ini disebabkan baik subtree kiri maupun subtree kanannya
sudah merupakan heap, sehingga tidak perlu dilakukan iterasi lengkap seperti
algoritma heapify. Dan setelah reheapify maka simpul yang akan diiterasikan
berikutnya akan berkurang satu.
2.2.2. Penerapan Algoritma Pengurutan Heap Sort
Salah
satu contoh penerapan algoritma pengurutan (sorting algorithm) heap sort adalah
sebagai berikut: Misalkan terdapat suatu array bilangan bulat yang terdiri dari
sepuluh buah anggota dengan nilai data 11, 9, 8, 27, 16, 25, 12, 13, 34, dan
43. Kita akan mengurutkan data diatas dengan menggunakan heapsort. Pertama-tama,
array di atas dapat dipandang sebagai suatu Complete Binary Tree (CBT) sebagai
berikut:
Selanjutnya
algoritma metoda heapify dilakukan dengan iterasi dari subtree node ke-4, ke-3,
dan seterusnya berturut-turut hingga mencapai root (akar). Iterasi dilakukan
mulai dari node ke-4 karena N/2 dalam contoh di atas adalah 5. Dan elemen
kelima dari array memiliki nilai indeks 4 sebab indeks array biasanya diawali
dari 0. Penerapan algoritma metoda heapify terhadap Complete Binary Tree (CBT)
pada contoh di atas menghasilkan operasi-operasi pertukaran sebagai berikut:
1.
Subtree node ke-4: pertukaran 16 dengan 43
2.
Subtree node ke-3: pertukaran 27 dengan 34
3.
Subtree node ke-2: pertukaran 8 dengan 25
4.
Subtree node ke-1: pertukaran 9 dengan 43,
lalu pertukaran 9 dengan 16
5.
Subtree node ke-0: pertukaran 11 dengan
43, lalu pertukaran 11 dengan 34, serta akhirnya pertukaran 11 dengan 27
Perubahan-perubahan (pertukaran) tersebut dapat digambarkan sebagai berikut:
Semua
perubahan di atas terjadi dalam array yang bersangkutan, sehingga pada akhirnya
diperoleh tree terakhir yang merupakan heap tree. Sementara itu, dalam iterasi
yang melakukan/menerapkan algoritma metoda remove( ) dan algoritma metoda
reheapify() akan terjadi pemrosesan berikut:
1.
Setelah 43 di-remove dan 9 menggantikan
posisi yang ditinggalkan oleh 43, maka terjadi reheapify: penukaran 9 dengan
34, 9 dengan 27, dan 9 dengan 13.
dan
data yang telah terurut adalah 43.
2.
Setelah 34 di-remove dan 11 menggantikan
posisi yang ditinggalkan oleh 34, maka terjadi reheapify: penukaran 11 dengan
27, dan 11 dengan 16.
dan
data yang telah terurut adalah 34, 43.
3.
Setelah 27 di-remove dan 9 menggantikan
posisi yang ditinggalkan oleh 27, maka terjadi reheapify: penukaran 9 dengan
25, dan 9 dengan 12.
dan
data yang telah terurut adalah 27, 34, 43.
4.
Demikian seterusnya dilakukan algoritma
metoda remove dan algoritma metoda reheapify hingga tidak ada lagi node yang
tersisa. Dan pada akhirnya akan didapatkan hasil data yang telah terurut adalah
8, 9, 11, 12, 13, 16, 25, 27, 34, 43.
BAB
III
PENUTUP
3.1.Kesimpulan
Merge
Sort adalah metode pengurutan data dengan cara data dibagi menjadi subkumpulan
- subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan
kemudian digabungkan kembali dengan metode merging.
Algoritma
pengurutan heap sort dapat digunakan untuk menyelesaikan masalah-masalah
pengurutan dalam membangun suatu program aplikasi dengan mangkus.
Keunggulan
algoritma pengurutan heap sort terletak pada kompleksitas waktu asimptotiknya
yang sangat baik.
Meskipun
lebih lambat dari algoritma pengurutan data yang lain, algoritma heap sort memiliki
kelebihan ketika menangani data dalam skala yang besar/massive. Karena
algoritma ini memiliki kelebihan tidak menggunakan banyak tabel, tetapi hanya
satu tabel yang dipakai untuk menyimpan hasil dari pengurutan tersebut.
