Berpikir Komputasional - Bagian Sorting

Pada pembelajaran sebelumnya kita telah belajar dan bermain tentang Searching atau Pencarian, di mana dalam hal pencarian ternyata kita tidak serta merta mencari sesuatu itu dengan sembarangan, malah ada strategi yang harus digunakan agar pencarian tersebut tidak terlalu lama dan langsung menuju apa yang kita cari.

Apakah kalian ingat pada permainan tebak angka? Bagaimanakah strategi yang dilakukana agar pencarian angka tersebut bisa langsung ditebak? setidaknya hanya membutuhkan waktu yang cukup singkat untuk menebaknya. Masih ingatkah kalian tentang strategi binary searching?

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. 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!

$ads={1}

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.

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 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 elemenelemen 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 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)

   
   
   
   
   
   

2. Selection sort
   

   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.

   • Cari bilangan terkecil yang ada pada bagian belum terurut.
   • Tukar bilangan tersebut dengan bilangan pertama bagian belum terurut, lalu masukkan ke bagian terurut.
   • Ulangi langkah 1 dan sampai bagian yang belum terurut habis. Ilustrasi urut-urutan selection sort dapat dilihat pada tabel berikut.

   Bagian terurut Bagian yang belum terurut Nilai terkecil dari bagian belum terurut

   Bagian terurut	Bagian yang belum terurut	Nilai terkecil dari bagian belum terurut
   ()	(2,3,7,6,5)	2
   -2	(3,7,6,5)	3
   -2,3	(7,6,5)	5
   (2,3,5)	-6,7	6
   (2,3,5,6)	-7	7
   (2,3,5,6,7)	()

   Secara rinci, algoritma selection sort yang dikaitkan dengan pemrograman dijelaskan sebagai berikut.

   Terdapat sebuah daftar bilangan tidak terurut seperti berikut: , 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 sebagai bilangan terkecil.

   

   Tukar bilangan dengan bilangan pertama bagian belum terurut. Geser batas bagian yang sudah terurut ke kanan sehingga 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.

Materi akan dilanjut ke Bagian Materi Tumpukan dan Antrean. Silahkan klik di sini