Elemen Berpikir Komputasional
(Chapter 2)
Sorting - Insertion Short & Selection Short
B. Pengurutan (Sorting)
Saat merapikan sesuatu, misalnya koleksi buku, kita menyusun buku tersebut dengan menggunakan suatu aturan. Misalnya, jika kita memiliki koleksi buku cerita berseri, kemungkinan besar kita akan menyusunnya secara berurut dari volume pertama hingga volume yang terbaru. Atau, ketika sedang berbaris, kita diminta untuk membentuk barisan berdasarkan tinggi badan. Hal-hal tersebut merupakan sebuah proses pengurutan atau sorting.
Pengurutan merupakan suatu permasalahan klasik pada komputasi yang dilakukan untuk mengatur agar suatu kelompok benda, objek, atau entitas diletakkan mengikuti aturan tertentu. Urutan yang paling sederhana misalnya mengurutkan angka secara terurut menaik atau menurun.
Misal, kita memperoleh 5 buah angka acak berikut:
Kita dapat membuat angka tersebut terurut menaik dengan melakukan satu kali pertukaran, yaitu dengan menukar nilai 4 dengan nilai 3. Terdapat 2 langkah penting dalam melakukan sebuah pengurutan. Langkah pertama ialah melakukan pembandingan. Untuk melakukan pengurutan, dipastikan ada dua buah nilai yang dibandingkan. Pembandingan ini akan menghasilkan bilangan yang lebih besar dari, lebih kecil dari, atau memiliki nilai sama dengan sebuah bilangan lainnya. Langkah kedua ialah melakukan penempatan bilangan setelah melakukan pembandingan. Penempatan bilangan ini dilakukan setelah didapatkan bilangan lebih besar atau lebih kecil (bergantung pada pengurutan yang digunakan).
Terdapat beberapa teknik (algoritma) untuk melakukan pengurutan seperti bubble sort, insertion sort, quick sort, merge sort, dan selection sort. Pada unit ini, hanya akan diberikan penjelasan untuk setiap tiga teknik ialah sebagai berikut.
1. Insertion Sort
Insertion Sort adalah salah satu algoritma yang digunakan untuk permasalahan pengurutan dalam list (daftar objek). Sesuai namanya, insertion sort mengurutkan sebuah list dengan cara menyisipkan elemen satu per satu sesuai dengan urutan besar kecilnya elemen hingga semua elemen menjadi list yang terurut.
Ilustrasi Insertion Sort
Terdapat sebuah deret bilangan seperti berikut: 2, 3, 7, 6, 5 yang direpresentasikan dengan menggunakan kartu. Urutkan bilangan tersebut secara menaik dengan menggunakan algoritma insertion sort.
Proses Iterasi Pertama
Langkah pertama, tinjau bilangan kedua, bandingkan bilangan pertama dan kedua, yaitu 2 dan 3. Didapatkan 2 lebih kecil dari 3, maka urutan bilangan tersebut tetap (2,3). (2, 3, 7, 6, 5) menjadi (2, 3, 7, 6, 5)
Proses Iterasi Kedua
Pada iterasi selanjutnya, kita mengambil bilangan ketiga, yaitu 7. Lalu bandingkan dengan bilangan sebelumnya. Karena 3 lebih kecil dari 7, urutan tetap. (2, 3, 7, 6, 5) menjadi (2, 3, 7, 6, 5)
Proses Iterasi Ketiga
Pada iterasi selanjutnya, kita mengambil bilangan keempat, yaitu 6. Lalu, bandingkan dengan bilangan sebelumnya. Didapatkan bahwa 7 lebih besar dari 6. Oleh karena itu, selanjutnya, kita akan membandingkan dengan bilangan-bilangan sebelumnya, lalu menukarnya apabila bilangan tersebut lebih besar. Pertama, kita akan membandingkan 6 dan 7. Apakah 6 lebih kecil dari 7? Karena iya, kita akan menukar 6 dengan 7. Lalu, kita akan membandingkan lagi dengan bilangan sebelumnya, yaitu 3. Apakah 6 lebih kecil dari 3? Karena 6 tidak lebih kecil dari 3, maka 6 sudah berada pada posisi yang benar, yaitu sebelum 7 dan setelah 3. Proses memindahkan 6 di antara 3 dan 7 ini biasa disebut penyisipan (insertion) sehingga nama algoritma ini disebut insertion sort. (2, 3, 7, 6, 5) menjadi (2, 3, 6, 7, 5)
Proses Iterasi Keempat
Pada iterasi selanjutnya, kita mengambil bilangan kelima, yaitu 5. Didapatkan bahwa 7 lebih besar dari 5. Oleh karena itu, selanjutnya, kita akan membandingkan dengan bilangan-bilangan sebelumnya, lalu menukarnya apabila bilangan tersebut lebih besar. Pertama, kita akan membandingkan 5 dan 6. Apakah 5 lebih kecil dari 6? Karena iya, kita akan menukar 5 dengan 6. Setelah itu, kita akan mengecek dengan bilangan sebelumnya lagi, yaitu 3. Apakah 5 lebih kecil dari 3? Karena 5 tidak lebih kecil dari 3, maka 5 sudah pada posisi seharusnya, yaitu setelah 3 dan sebelum 6. Terjadi lagi proses penyisipan kartu 5 di antara 3 dan 6. (2, 3, 6, 7, 5) menjadi (2, 3, 5, 6, 7)
Selection sort merupakan algoritma pengurutan yang juga cukup sederhana, dengan algoritma mencari (menyeleksi) bilangan terkecil/terbesar (bergantung pada urut naik atau turun) dari daftar bilangan yang belum terurut dan meletakkannya dalam daftar bilangan baru yang dijaga keterurutannya. Algoritma ini membagi daftar bilangan menjadi dua bagian, yaitu bagian terurut dan bagian yang belum terurut. Bagian yang terurut di sebelah kiri dan bagian yang belum terurut di sebelah kanan. Awalnya, semua elemen bilangan dalam daftar ialah bagian yang belum terurut, dan bagian yang terurut kosong.
Berikut langkah-langkah yang terdapat pada algoritma selection sort.
1. Cari bilangan terkecil yang ada pada bagian belum terurut.
2. Tukar bilangan tersebut dengan bilangan pertama bagian belum terurut, lalu masukkan ke bagian terurut.
3. Ulangi langkah 1 dan 2 sampai bagian yang belum terurut habis.
Ilustrasi urut-urutan selection sort dapat dilihat pada tabel berikut.
Secara rinci, algoritma selection sort yang dikaitkan dengan pemrograman dijelaskan sebagai berikut.
Terdapat sebuah daftar bilangan tidak terurut seperti berikut: 2, 3, 7, 6, 5. Urutkan bilangan tersebut secara menaik dengan menggunakan algoritma selection sort.
Proses Iterasi Pertama
Data Awal:
Cari bilangan terkecil di bagian belum terurut: ditemukan 2 sebagai bilangan terkecil.
Tukar bilangan 2 dengan bilangan pertama bagian belum terurut. Geser batas bagian yang sudah terurut ke kanan sehingga 2 menjadi bagian yang sudah terurut. Dalam ilustrasi ini, angka yang dicetak tebal menunjukkan bilangan yang sudah terurut.
Proses Iterasi Kedua
Cari bilangan terkecil di bagian belum terurut, ditemukan angka 3 sebagai bilangan terkecil.
Tukar bilangan 3 dengan bilangan pertama bagian belum terurut. Geser batas bagian yang sudah terurut ke kanan sehingga 3 menjadi bagian yang sudah terurut.
Proses Iterasi Ketiga
Cari bilangan terkecil di bagian belum terurut, ditemukan angka 5 sebagai bilangan terkecil.
Tukar bilangan 5 dengan bilangan pertama bagian belum terurut, yaitu 7. Geser batas bagian yang sudah terurut ke kanan, sehingga 5 menjadi bagian yang sudah terurut.
Proses Iterasi Keempat
Cari bilangan terkecil di bagian belum terurut, ditemukan angka 6 sebagai bilangan terkecil.
Tukar bilangan 6 dengan bilangan pertama bagian belum terurut. Di bagian akhir, karena data tinggal dua, setelah proses penukaran, algoritma telah selesai dilaksanakan.
Aktivitas Individu/Berkelompok : Bermain Kartu
Apa yang kalian perlukan? 10 kartu yang masing-masing bertuliskan angka 1 sampai 10.
Skenario Permainan, Aktivitas dapat dilakukan secara mandiri atau berkelompok.
1. Kalian akan diberikan sebuah kartu bertuliskan angka dari 1 - 10.
2. Kelima belas kartu tersebut kalian kocok dan letakkan dalam bentuk barisan di atas meja. Kartu diletakkan tertutup.
3. Kalian harus dapat mengurutkan semua kartu secara menaik. Kartu yang berada di paling kiri barisan harus yang paling kecil.
4. Untuk mengurutkan, kalian harus melakukan serangkaian pertukaran kartu. Pertukaran dilakukan dengan membuka dua buah kartu. Apabila diperlukan, kalian dapat menukar posisi kedua kartu tersebut.
5. Kalian diminta untuk menyusun algoritma pertukaran yang dapat dilakukan untuk memastikan semua kartu dalam posisi terurut. Kalian dapat memilih untuk menggunakan salah satu dari tiga algoritma pengurutan yang disampaikan pada bagian konsep.
Apa yang kalian diskusikan? Setelah bermain, saatnya memikirkan permainan tersebut dan cara kalian bermain. Beberapa poin yang penting untuk didiskusikan seperti berikut.
1. Apakah permainan tadi merupakan masalah pengurutan?
2. Strategi pengurutan seperti apa yang kalian lakukan untuk melakukan pengecekan dan pertukaran sesedikit mungkin?
3. Apakah strategi kalian berbeda dengan strategi yang dilakukan oleh teman kalian? Jika berbeda, apa perbedaannya?
4. Strategi paling bagus apa yang dapat kalian temukan untuk mengurutkan dengan banyaknya pertukaran paling sedikit?
5. Adakah kondisi yang membuat kalian melakukan banyak sekali pertukaran untuk mengurutkan kartu secara menaik?
Jawablah pertanyaan berikut
1. Apakah kalian sudah pernah melakukan permainan ini?
2. Saat mengurutkan kartu, apakah kalian senang?
3. Apakah kalian paham bahwa mengurutkan kartu itu suatu proses pengurutan?
4. Apakah kalian berhasil menemukan cara yang paling cepat untuk mengurutkan kartu tersebut?
5. Apakah kalian merasa ada masalah lain yang serupa dengan permainan tadi?
6. Pelajaran paling berkesan apa yang kalian dapatkan dari permainan ini?
Tidak ada komentar:
Posting Komentar