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.
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.
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.
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.
Tumpukan (Stack) dan
Antrean (Queue)
Kita akan mempelajari
dua buah konsep cara penyimpanan data / objek dalam sebuah
struktur yang akan
menentukan urutan pemrosesan data/objek tersebut, yaitu tumpukan (stack)
dan antrean (queue).
Kedua konsep ini memiliki prosedur yang berbeda dalam menyimpan dan
mengeluarkan data.
Kedua konsep tersebut masing-masing memiliki peranan yang berbeda dan
digunakan pada situasi
yang berbeda pula.
Bayangkan sebuah loket
di sebuah rumah sakit, di mana para pasien yang akan berobat
diminta untuk
mendaftar lebih dahulu di loket penerimaan serta mengisi formulir pendaftaran.
Setelah formulir
tersebut diisi, para pasien akan mengembalikan formulir ke loket dan menunggu
dipanggil oleh
petugas. Kebetulan, di pagi hari, dokter yang bertugas belum datang sehingga
para
pasien harus menunggu.
Ketika sang dokter tiba, petugas loket akan memanggil para pasien satu
per satu untuk
mendapat layanan Perhatikan sekarang bagaimana urutan pasien itu dipanggil oleh
petugas loket.
