Algoritma & Pemrograman 1A
PENGURUTAN BILANGAN METODE BUBBLE SORT
PROSES PENGURUTAN Untuk mengurutkan bilangan diperlukan variabel array untuk menampung semua bilangan yang akan diurutkan. Proses pengurutan dilakukan dengan membandingkan semua elemen array satu per satu. Dibawah ini terlampir contoh array berisi sederet bilangan yang belum diurutkan.
20 1
12 2
35 3
11 4
17 5
9 6
58 7
23 8
Indeks yg menunjukkan posisi elemen
Dimetode bubble sort, proses pengurutan dimulai dengan membandingkan elemen pertama untuk mendapatkan angka terbesar. Lalu angka tersebut ditempatkan pada elemen terakhir. Sebagai langkah awal, isi elemen pertama dibandingkan dengan elemen ke-2. Jika isi elemen ke2 lebih kecil dari elemen pertama, maka isi kedua elemen tersebut ditukar. Sehingga isi array berubah menjadi :
12
20
35
11
17
9
58
23
1
2
3
4
5
6
7
8
Elemen array setelah ditukar
Lalu elemen ke-2 dibandingkan dengan elemen ke-3. jika isi elemen ke-3 lebih besar, maka isi kedua elemen tersebut tidak ditukar.
12
20
35
11
17
9
58
23
1
2
3
4
5
6
7
8
Isi elemen ke-3 lebih besar dari elemen ke-2
Metode Bubble Sort
Algoritma & Pemrograman 1A Perbandingan selanjutnya dilakukan terhadap elemen ke-3 dengan ke-4. Karena elemen ke-4 lebih kecil, maka isi kedua elemen tersebut ditukar. Sehingga isi array sebelumnya berubah menjadi :
12
20
11
35
17
9
58
23
1
2
3
4
5
6
7
8
Isi elemen setelah ditukar
Proses perbandingan seperti diatas dilakukan secara berulang sampai pada elemen terakhir. Sehingga pada akhirnya akan dihasilkan bilangan terbesar yang ditempatkan pada posisi elemen terakhir. Dibawah ini kondisi array setelah perbandingan elemen terakhir.
12
20
11
17
9
35
23
58
1
2
3
4
5
6
7
8
Elemen terakhir berisikan bilangan terbesar
Proses diatas hanya mencari bilangan terbesar pertama. Ulangi proses tersebut untuk mencari bilangan terbesar lainnya setelah bilangan terbesar pertama tadi. Namun proses perbandingan hanya dilakukan mulai dari elemen pertama sampai elemen ke-7. Isi elemen pertama dibandingkan dengan elemen ke-2. Karena isi elemen ke-2 lebih besar, maka isi kedua elemen tersebut tidak ditukar. Kemudian elemen ke-2, dibandingkan dengan elemen ke-3. Karena elemen ke-3 lebih kecil, maka isi kedua elemen tersebut ditukar sehingga isi array menjadi :
12
11
20
17
9
35
23
58
1
2
3
4
5
6
7
8
Isi array setelah ditukar
Metode Bubble Sort
Algoritma & Pemrograman 1A Lanjutkan proses diatas sampai pada elemen ke-7. Hasilnya isi array menjadi ;
12
11
17
9
20
23
35
58
1
2
3
4
5
6
7
8
Isi elemen array yg sudah diurut
Kini isi elemen ke-7 dan ke-8 sudah urut berdasarkan bilangan kecil ke besar. Namun elemen lainnya belum terurut. Untuk itu ulangi proses diatas, namun elemen yang dibandingkan hanya sampai pada elemen ke-6 saja. Setelah itu, proses perbadingan diulangi lagi sampai elemen terakhir yang dibandingkan yaitu elemen ke-2. Hasil akhirnya menjadi :
9
11
12
17
20
23
35
58
1
2
3
4
5
6
7
8
IMPLEMENTASI DALAM BENTUK FLOWCHART Seperti telah dijelaskan sebelumnya, proses pengurutan memakai variabel array untuk menampung semua bilangan yang akan diurutkan. Oleh karena itu sebelum proses pengurutan dilakukan, terlebih dahulu dibuat proses untuk mengisi semua bilangan ke dalam array. Setelah array tersebut terisi, barulah proses pengurutan dilakukan untuk mengurutkan isinya. Seperti diketahui, jika salah satu elemen array diisi dengan nilai baru, maka nilai lama akan terhapus. Oleh sebab itu untuk mempertukarkan isi elemen array harus mengggunakan satu variabel cadangan. Variabel ini digunakan untuk menyimpan isi array yang akan ditukar. BILARR
9
11
12
17
20
23
35
58
1
2
3
4
5
6
7
8
Misalnya isi elemen ke-2 dari variabel BILARR akan ditukar dengan elemen ke-3. Maka isi elemen ke-2 disimpan terlebih dahulu ke variabel cadangan ( misalnya untuk variabel ini diberi nama TEMP). Setelah itu, isi elemen ke-3 dipindahkan ke elemen ke-2, lalu isi dari variabel TEMP dipindahkan ke elemen ke-3. Ilustrasi dibawah ini memperlihatkan pertukaran kedua elemen tersebut.
Metode Bubble Sort
Algoritma & Pemrograman 1A
TEMP
11
BILARR
9
11
12
17
20
23
35
58
1
2
3
4
5
6
7
8
Proses tersebut dapat dituliskan sebagai berikut : TEMP = BILARR (2) BILARR(2) = BILARR (3) BILARR(3) = TEMP
Dari proses yang telah dijelaskan, pengurutan bilangan dari kecil ke besar dengan metode bubble sort dapat digambarkan melalui flowchart seperti berikut (lihat gambar 10.1)
Metode Bubble Sort
Algoritma & Pemrograman 1A start
1
I=0 J=0 N=0
J=J+1 2 N=N+1
Input BIL
BILARR(I) < BILARR(I+1) BIL = 0
N=N+1
1
TEMP = BILARR(I) BILARR(I)=BILARR(I+1) BILARR(I+1)=TEMP
BILARR(N) = BIL
I=N-J
2
gambar 10.1 ( bersambung )
Metode Bubble Sort
3
Algoritma & Pemrograman 1A 3
J=N-1
I=0
3
I=0
I=I+1
PRINT BILARR(I)
I=N
END
Gambar 10.1 ( sambungan )
Berdasarkan flowchart diatas, proses pengurutan bilangan dari kecil ke besar dapat dirangkum sebagai berikut : 1. persiapan variabel yang dipakai dalam proses, yaitu : N : variabel untuk menyatakan jumlah elemen array. Jumlah ini diketahui berdasarkan banyaknya bilangan yang diinputkan melalui keyboard. I, J : variabel indeks untuk membandingkan isi array 2. prose pertama yang dilakukan adalah mengisi semua bilangan yang akan diurutkan ke array. Pada flowchart diatas, array tersebut diberi nama BILARR. Bilangan diinput melalui keyboard dan disimpan didalam variabel BIL. 3. periksa isi variabel BIL. Pada flowchart diatas, diasumsikan pengisian bilangan berakhir jika operator mengetik 0 untuk bilangan yang diinput. Oleh karena itu, jika BIL = 0 maka proses dilanjutkan ke langkah 7 untuk mulai pengurutan bilangan. Jika BIL tidak sama dengan 0 berarti pengisian bilnagan belum berakhir, maka proses dilanjutkan ke langkah 4. 4. variabel N ditambah 1. variabel ini untuk menentukan elemen array yang akan diisi nilai dari variabel BIL. 5. isi elemen array dengan nilai yang tersimpan di variabel BIL. Posisi elemen tersebut ditentukan berdasarkan harga N. 6. kembali ke langkah 2 untuk menginput bilangan lainnya. Metode Bubble Sort
Algoritma & Pemrograman 1A 7. variabel J ditambah 1. 8. variabel I ditambah 1. 9. bandingkan isi elemen array pada posisi sesuai dengan nilai variabel I atau BILARR (I) dengan elemen array didepannya yaitu posisi I+1 atau BILARR (I+1). Jika isi BILARR(I) lebih kecil dari BILARR (I+1) maka isi kedua elemen tersebut tidak ditukar. Untuk itu proses dilanjutkan ke lankah 11. namun juka isi BILARR(I) > dari BILARR(I+1) lanjutkan ke langkah 10 untuk menukar isi kedua elemen tersebut. 10. pindahkan isi BILARR(I) ke variabel sementara yaitu TEMP. pindahkan isi BILARR(I+1) ke BILARR(I). pindahkan isi TEMP ke BILARR(I+1). 11. periksa isi variabel I. jika I sama dengan N-J maka proses perbandingan untuk mencari bilangan terbesar pertama selesai. Untuk itu proses dilanjutkan ke langkah 12. jika isi I belum sama, maka proses perbandingan untuk mencari bilangan terbesar belum selesai. Untuk itu proses selanjutnya kembali ke langkah 8. 12. periksa isi variabel J. jika J sama dengan N-1, maka semua elemen telah diperbandingkan dan proses pengurutan telah selesai. Untuk itu proses dilanjutkan ke langkah 15 untuk mencetak seluruh isi arrray. Jika isi J masih belum sama dengan N-1 maka semua bilangan belum terurut. Proses dilanjutkan ke langkah 13 untuk mencari bilangan terbesar lainnya. 13. variabel I diisi nilai 0. 14. kembali ke langkah 7 untuk mencari bilangan terbesar lainnya. 15. Variabel I diisi nilai 0. 16. variabel I ditambah 1. 17. cetak isi BILARR(I). 18. periksa isi I. jika I sama dengan N berarti semua elemen array telah dicetak maka proses selesai. Jika isi I belum sama dengan N berarti semua elemen array belum tercetak. Untuk itu kembali ke langkah 16 untuk mencetak elemen lainnya.
Metode Bubble Sort
