.jpeg)
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.
Proses pengurutan akan menjadi bagian yang tidak terpisahkan dari program komputer atau aplikasi yang sering kita gunakan.
Pada aktivitas ini, kita akan melihat bagaimana proses pengurutan dapat dilakukan dengan menggunakan berbagai strategi.
Pelajarilah strateginya! 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. Biasanya, masalah pengurutan terdiri atas sekumpulan objek yang disusun secara acak yang harus diurutkan. Setelah itu, secara sistematis, posisi objek diperbaiki dengan melakukan pertukaran posisi dua buah objek. Hal ini dilakukan secara terus-menerus hingga semua posisi objek benar.
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. Teknik lainnya dapat kalian pelajari dari referensi yang diberikan.
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. Misalnya, dalam kasus mengurutkan elemen list dari yang terkecil hingga terbesar (ascending), tahap pertama ialah kita akan membaca suatu elemen dengan elemen yang berdekatan.
Apabila elemen yang berdekatan dengan elemen saat ini lebih kecil, elemen yang lebih kecil akan ditukar dengan elemen yang lebih besar dan dibandingkan kembali dengan elemen-elemen sebelumnya yang sudah terurut. Apabila elemen saat ini sudah lebih besar dari elemen sebelumnya, iterasi berhenti.
Hal ini dijalankan satu per satu hingga semua list menjadi 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)
Apa yang kalian diskusikan?
Setelah bermain, saatnya memikirkan permainan tersebut dan cara kalian bermain. Beberapa poin yang penting untuk didiskusikan seperti berikut.
- Apakah permainan tadi merupakan masalah pengurutan?
- Strategi pengurutan seperti apa yang kalian lakukan untuk melakukan pengecekan dan pertukaran sesedikit mungkin?
- Apakah strategi kalian berbeda dengan strategi yang dilakukan oleh teman kalian? Jika berbeda, apa perbedaannya?
- Strategi paling bagus apa yang dapat kalian temukan untuk mengurutkan dengan banyaknya pertukaran paling sedikit?
- Adakah kondisi yang membuat kalian melakukan banyak sekali pertukaran untuk mengurutkan kartu secara menaik?
.jpeg)
.jpeg)
.jpeg)
.jpeg)
.jpeg)
.jpeg)
.png)
.jpeg)
