Penerapan Algoritma Bucket

Sort Untuk melakukan

Pengurutan n buah Bilangan Mata Kuliah Pemrosesan Paralel

DEPARTEMEN ILMU KOMPUTER

SEKOLAH PASCASARJANA

INSTITUT PERTANIAN BOGOR

BOGOR

2010

OLEH : SUPRIYANTO (G651090191)

OKE HENDRADHY (G651090101)

KAMALUDDIN MAHFUDZ (G651090231)

i

KATA PENGANTAR

Puji syukur kehadirat Allah SWT, atas berkat rahmat dan hidayah-Nya kami dapat

menyelesaikan tugas mata kuliah pemrosesan paralel ini. Tulisan ini akan membahas penerapan

algoritma bucket sort secara sekuensial dan paralel. Algoritma paralel dirancang dalam rangka

untuk mengoptimalkan (mempercepat) proses pengurutan n buah bilangan.

Algoritma bucket sort sendiri merupakan variasi dari berbagai macam algoritma pengurutan

dengan prinsip divide dan conquer, yaitu membagi n buah bilangan yang akan diurutkan menjadi

m buah sub proses untuk diselesaikan. Setelah proses pengurutan di sub masalah selesai maka

solusi digabungkan ke dalam proses aslinya.

Penulis menyadari dalam penyusunan makalah ini masih banyak kekurangan. Kritik dan saran

demi kemajuan di kemudian hari sangat kami harapkan.

Hormat Kami,

Tim Penulis

i

DAFTAR ISI

KATA PENGANTAR ..................................................................................................................... i

DAFTAR ISI .................................................................................................................................... i

PENDAHULUAN .......................................................................................................................... 1

A. Latar Belakang .................................................................................................................... 1

B. Tujua ................................................................................................................................... 2

LANDASAN TEORI ...................................................................................................................... 3

A. Algoritma Divide and Conquer ........................................................................................... 3

B. Bucket Sort .......................................................................................................................... 3

METODE ........................................................................................................................................ 5

PEMBAHASAN ............................................................................................................................. 6

A. Prinsip Kerja Algoritma Bucket Sort .................................................................................. 6

B. Pseudocode Algoritma Bucket Sort .................................................................................... 7

C. Kompleksitas Algoritma Bucket Sort Sekuensial ............................................................... 7

KESIMPULAN DAN SARAN....................................................................................................... 8

A. Kesimpulan ......................................................................................................................... 8

B. Saran .................................................................................................................................... 8

DAFTAR PUSTAKA ..................................................................................................................... 9

1

PENDAHULUAN

A. Latar Belakang Sorting (pengurutan) adalah proses mengurutkan n buah bilangan dalam urut menaik

(ascending) atau urut menurun (descending) (Cormen, 2001). Proses mengurutkan 2 buah

bilangan merupakan proses membandingkan bilangan tersebut dengan operator pembanding

yang kemudian dilakukan proses tukar posisi (exchange position) sesuai dengan operator

pembandingnya apakan bilangan tersebut di urut secara ascending atau di urutkan secara

descending. Proses tersebut berlanjut sampai dengan n buah bilangan dapat terurut

sempurna.

Algoritma mengurutkan suatu array memiliki variasi yang cukup banyak tergantung

dari teknik mengurutkan array tersebut sehingga menghasilkan suatu kompleksitas waktu

proses mengurutkan yang berbeda-beda. Pada mesin sekuensial yaitu proses mengurutkan

suatu array oleh hanya satu buah prosesor, mengurutkan n buah bilangan merupakan proses

mengurutkan yang rutin prosesnya mengantri melalui urutan waktu (t) tertentu dalam

prosesor. Kompleksitas waktu pengurutan diuji dalam keadaan terburuk (worstcase) dan

keadaan rata-rata (average case), sehingga menghasilkan notasi O (Big Oh) dan notasi Ω

(Big Omega), dan memiliki variasi yang tergolong dalam 3 kategori sorting, yaitu :

comparison sort, not comparison sort dan external sort (Sedgewick, 1998).

Pada mesin paralel, yaitu proses yang memanfaatkan n buah prosesor sebagai media

proses sorting, n bilangan yang akan di sorting di pecah terlebih dahulu melalui teknik foster

(Grama, 2003), yang selanjutnya di bandingkan antar bilangan yang ada dimasing-masing

prosesor yang kemudian di satukan kembali dalam keadaan terurut. Tentunya proses ini

menghasilkan algoritma yang secara prinsip lebih cepat di bandingkan proses sekuential,

karena masalah yang ada di pecah-pecah terlebih dahulu dalam sub masalah yang lebih kecil

untuk kemudian di proses. Akan tetapi faktor lain dapat menghasilkan kondisi sebaliknya,

karena dengan semakin menaiknya jumlah prosesor yang digunakan maka semakin menaik

juga kebutuhan akan komunikasi antar prosesor yang ada. Hal ini dapat menyebabkan bahwa

tidak setiap penambahan jumlah prosesor dapat meningkatkan waktu proses dari suatu

algoritma sorting paralel.

Salah satu algoritma sorting yang cukup menarik untuk di uji pada kondisi sekuential

maupun kondisi paralel adalah algoritma bucket sort (Grama, 2003). Algoritma ini memiliki

teknik yang cukup menarik karena algoritma ini akan memilah elemen array n dalam suatu

interval [a, b] dibagi menjadi subintervals sama besar m dalam suatu bucket, setiap bucket

akan berisikan n/m buah bilangan untuk kemudian bucket yang ada di urutkan dan

dibandingkan antar bucket yang ada sehingga menghasilkan suatu proses terurut.

Dengan asumsi bahwa setiap bucket merupakan procesor yang ada, maka pada proses

paralel algoritma bucket akan dirumuskan dalam 3 langkah yaitu : proses mempartisi blok n

buah bilangan ke dalam setiap prosesor p, lalu mengirimkan setiap subblok yang ada ke

prosesor yang sesuai dan terakhir proses yang ada disetiap bucket yang didefinisikan sebagai

p buah prosesor dilakukan proses pengurutan secara sekuensial.

2

Dilihat dari kompleksitas algoritma, algoritma bucket sort secara sekuential menjadi

paralel, maka perlu dilakukan uji atas algoritma bucket sort ini dalam kondisi sekuensial dan

kondisi paralel dan sampai dimana algoritma tersebut dalam keadaan optimal. Pada

percobaan ini hanya dibatasi pada analisis terhadap algoritma sekuensial dari bucket sort.

B. Tujuan Tujuan dari penulisan makalah ini adalah untuk :

1. Melakukan perbandingan antara proses algoritma bucket sort secara sekuential dan

paralel;

2. Menguji nilai kompleksitas waktu, speedup, efisiensi dan iso efisiensi dari bucket sort

secara paralel

3. Menganalisa kinerja algoritma bucket sort tersebut pada mesin paralel

3

LANDASAN TEORI

A. Algoritma Divide and Conquer

Algoritma divide and conquer sudah lama diperkenalkan sebagai sumber dari

pengendalian proses paralel, karena masalah-masalah yang terjadi dapat diatasi secara

independen. Banyak arsitektur dan bahasa pemrograman paralel mendesain implementasinya

(aplikasi) dengan struktur dasar dari algoritma divide and conquer. Untuk menyelesaikan

masalah-masalah yang besar, dan dibagi (dipecah) menjadi bagian yang lebih kecil dan

menggunakan sebuah solusi untuk menyelesaikan problem awal adalah prinsip dasar dari

pemrograman/strategi divide and conquer.

Gambar 2.1. Ilustrasi pemecahan masalah dengan divide dan Conquer

Divide and conquer adalah varian dari beberapa strategi pemrograman topdown,

tetapi keistimewaannya adalah membuat sub-sub problem dari problem yang besar, oleh

karena itu strategi ini ditunjukkan secara berulang-ulang (recursively), didalam menerapkan

algoritma yang sama dalam sub-sub problem seperti yang diterapkan pada masalah aslinya

(original problem). Sebagaimana prinsip dasar algoritma perulangan dibutuhkan sebuah

kondisi untuk mengakhiri perulangan tersebut. Biasanya untuk mengecek apakah problem

sudah cukup kecil untuk diselesaikan dengan metode secara langsung. Mungkin dari segi

ilustrasi kita, bahwa proses-proses pada komputer paralel tentunya memiliki

proses/problem/job yang cukup kompleks sehingga harus dipecah-pecah menjadi sub-sub

problem. Salah satu penerapan algoritma divide and conquer adalah pengurutan data dengan

metode merge.

B. Bucket Sort Bucket sort merupakan salah satu bentuk algoritma divide & conquer melalui metode

partisi dan berjalan dalam keadaan linear time (Wilkinson & Allen, 2005). Secara teoritis,

proses pengurutan dilakukan dengan membagi dan memecahkan himpunan array ke dalam

beberapa ember virtual secara merata.

4

32 45 2 11 67 5 8 12 1 22 23 10 90 15 27 19 33 ...... 26 28 7

1 2 5 7 8 10 11 12 15 19 22 23 26 27 28 32 33 ...... 45 67 90

Bilangan belum terurut

Bucket

Pengurutan isi bucket

Proses merge

Bilangan telah terurut

Gambar 2.2. Proses pengurutan bucket

Adapun ember yang dijadikan partisi atas n data kemudian diurutkan secara

individual, menggunakan algoritma sorting yang berbeda atau melalui penerapan bucket sort

secara rekursif. Ember virtual yang merupakan partisi atas n array dan merupakan proses

acak yang mendistribusikan elemen seragam pada interval [0,1), dimana pembagian tersebut

dilakukan merata sama besar. Dengan asumsi input dalam n elemen pada array A, untuk

masing-masing A memenuhi 0 ≤ A [i] ≤ 1, sehingga membutuhkan array bantu B yang

merupakan ember sub interval (Wilkinson & Allen, 2005).

Secara teoritis langkah-langkah algoritma bucket sort adalah sebabagi berikut :

1. Menginisiasi sejumlah m ember yang akan digunakan (bucket)

2. Membagi n element data yang diurutkan ke dalam, m bucket (wadah), dari suatu

himpunan data S dengan interval [a,b]

3. S dibagi ke dalam m sub interval (buckets) sama rata.

4. Satu wadah akan mendapatkan n/m elemen data.

5. Bucket diurutkan dengan menggunakan algoritma sekuensial.

6. Lihat semua bucket kemudian kembalikan ke array aslinya.

5

METODE

Metode yang digunakan dalam implementasi algoritma sekuensial pengurutan dengan

bucket sort adalah dengan menggunakan Divide dan conquer. Prinsip kerja dari metode ini

adalah memecah masalah menjadi sub-sub masalah kemudian menyelesaikannya. Setelah

masalah diselesaikan maka digabungkan kembali untuk mendapatkan solusi.

6

PEMBAHASAN

A. Prinsip Kerja Algoritma Bucket Sort Proses pengurutan yang dilakukan dengan menggunakan algoritma bucket sort

adalah dengan cara membagi dan memecahkan himpunan array ke dalam beberapa

ember(bucket) virtual secara merata. Kemudian pada masing-masing ember dilakukan

pengurutan dengan menggunakan algoritma lainnya misalnya merge sort atau quick sort.

Setelah selesai maka dikumpulkan kembali ke array aslinya, sehingga mendapatkan susunan

array yang sudah terurut. Gambar 3.1 berikut mengilustrasikan proses yang dilakukan.

32 45 2 11 67 5 8 12 1 22 23 10 90 15 27 19 33 ...... 26 28 7

1 2 5 7 8 10 11 12 15 19 22 23 26 27 28 32 33 ...... 45 67 90

Bilangan belum terurut

Bucket

Pengurutan isi bucket

Proses merge

Bilangan telah terurut

Gambar 4.1. Proses pengurutan bucket

Secara mudah proses-proses yang terjadi pada algoritma pengurutan dengan

menggunakan algoritma bucket sort adalah sebagai berikut :

1. Menginisiasi sejumlah m ember yang akan digunakan (bucket)

2. Membagi n element data yang diurutkan ke dalam, m bucket (wadah), dari suatu

himpunan data S dengan interval [a,b]

3. S dibagi ke dalam m sub interval (buckets) sama rata.

4. Satu wadah akan mendapatkan n/m elemen data.

5. Bucket diurutkan dengan menggunakan algoritma sekuensial.

6. Lihat semua bucket kemudian kembalikan ke array aslinya.

7

B. Pseudocode Algoritma Bucket Sort Berdasarkan pada proses-proses yang dilakukan pada algoritma bucket sort maka

dapat disusun pseudocode algoritma sekuensialnya. Berikut adalah implementasi

pseudocode algoritma bucket sort :

function bucket-sort(array, n) is

buckets ← new array of n empty lists

for i = 0 to (length(array)-1) do

insert array[i] into buckets[msbits(array[i], k)]

for i = 0 to n - 1 do

next-sort(buckets[i])

return the concatenation of buckets[0], ..., buckets[n-1]

C. Kompleksitas Algoritma Bucket Sort Sekuensial Untuk melakukan analisis terhadap kompleksitas suatu algoritma dilakukan dengan

cara mempelajari langkah-langkah yang dilakukan di dalam algoritma tersebut.

Kompleksitas sendiri menentukan baik atau tidaknya suatu algoritma. Berikut adalah

penjabaran proses yang dilakukan algoritma berpengaruh terhadap kompleksitas dari

algoritma bucket sort sekuensial :

1. Untuk menempatkan n buah bilangan ke dalam m buah bucket diperlukan n langkah.

2. Pengurutan di tiap-tiap bucket (quick sort atau mergsort) dengan kompleksitas O(n log

n), jika dibagi ke dalam m bucket kompleksitas masing-masing dapat diasumsikan n/m

log (n/m)

3. Pengumpulan kembali (asumsi tidak ada lankah lain)

Maka jika diformulasikan dalam formulasi matematis berikut adalah nilai

kompleksitas dari algoritma bucket sort :

Ts = n + m((n/m) log (n/m)) = n + n log (n/m) = O( n log (n/m))

dimana

n = jumlah array

m = jumlah bucket

8

KESIMPULAN DAN SARAN

A. Kesimpulan Metode divide and conquer pada algoritma sekuensial berguna untuk mengoptimalkan

waktu yang digunakan (kompleksitas) untuk menjalankan algoritma. Salah satu algoritma

pengurutan yang dapat diterapkan dengan menggunakan prinsip divide and conquer adalah

algoritma bucket sort. Dari hasil analisis dapat disimpulkan bahwa kompleksitas algoritma

bucket sort dengan menggunakan metode divide and conquer adalah sebesar O( n log (n/m),

dimana n adalah jumlah array dan m adalah jumlah bucket yang digunakan.

B. Saran Sementara itu untuk melakukan mempercepat waktu komputasi maka perlu dilakukan

ujicoba terhadap kinerja algoritma paralel.

9

DAFTAR PUSTAKA

Grama, A; Gupta, A; Karypis, George; dan Kumar, V. 2003. Introduction to Parallel Computing,

Second Edition - Chapter 9. Sorting. Addison Wesley. USA.

Cormen, Thomas H. Charles E. Leiserson. Ronald L. Rivest. Clifford Stein. 2001. Introduction

to Algorithms, second Edition. Massachusetts Institute of Technology.

Petersan, W.P. dan Arbenz, P. 2004. Introduction to Parallel Computing, A Practical Guide With

Examples in C. Oxford University.

Quinn, Michael J. 2004. Parallel Programming in C with MPI and OpenMP. Mc Graw Hill.

Wilkinson, Barry dan Michael Allen. 2010. Tehcniques and Apllications Using Networked and

Parallel Computers – second editons : Terjemahan. Andi : Yogyakarta.