My first Magazine pemrograman-kompetitif-dasar | Page 40

3 Pencarian dan Pengurutan
Persoalan ini meminta kita melakukan pengurutan N bilangan dengan rentang datanya antara
1 sampai 100.000. Terdapat sejumlah algoritma pengurutan, yang akan dibahas pada bagian
berikutnya.
3.2.1 Bubble Sort
Kita dapat melakukan bubble sort dengan memproses setiap pasang elemen yang bersebe-
lahan satu per satu. Mulai dari elemen pertama, cek apakah elemen sesudahnya (yaitu elemen
kedua) lebih kecil. Bila ya, artinya elemen pertama ini harus terletak sesudah elemen kedua.
Untuk itu, lakukan penukaran. Bila tidak, tidak perlu lakukan penukaran. Lanjut periksa elemen
kedua, ketiga, dan seterusnya. Proses ini mengakibatkan elemen dengan nilai terbesar pasti
digiring ke posisi terakhir seperti pada Gambar 3.7.
4
3
3
3
3
3
3
4
2
2
2
2
2
2
4
4
4
4
8
8
8
8
5
5
5
5
5
5
8
3
3
3
3
3
3
8
ditukar
tidak ditukar
Gambar 3.7: Ilustrasi penggiringan elemen terbesar ke posisi terakhir.
Bila proses ini dilakukan lagi, maka elemen kedua terbesar akan terletak di posisi kedua dari
terakhir. Kali ini pemeriksaan cukup dilakukan sampai 1 elemen sebelum posisi terakhir, sebab
elemen terakhir sudah pasti tidak akan berubah posisi.
3
2
2
2
2
2
3
3
3
3
4
4
4
4
4
5
5
5
5
3
3
3
3
3
5
8
8
8
8
8
ditukar
tidak ditukar
Gambar 3.8: Ilustrasi penggiringan elemen kedua terbesar ke posisi kedua dari akhir.
Demikian pula untuk eksekusi yang ketiga kalinya, yang kebetulan data sudah menjadi terurut
seperti pada Gambar 3.9.
30