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.
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.
Bubble sort adalah teknik pengurutan data berbasis perbandingan di mana setiap elemen yang berdekatan dibandingkan dan elemen-elemen tersebut ditukar jika tidak berurutan.
Penukaran data dilakukkan secara terus menerus hingga dipastikan dalam suatu iterasi tertentu tidak ada lagi penukaran
Proses pengurutan tiap elemen terjadi secara berangsur-angsur berpindah ke urutan yang tepat seperti gelembung yang naik ke permukaan. Karena itulah dinamakan Bubble (gelembung)
Contoh :
Urutkan data : 5, 1, 4, 2, 8 secara ascending (dari kecil sampai terbesar) menggunakan teknik bubble sort.
Proses Iterasi pertama
Data awal : 5, 1, 4, 2, 8
Bandingkan angka ke-2 dengan angka ke-1 yaitu 5, 1 ditukar menjadi 1, 5, 4, 2, 8
Bandingkan angka ke-3 dengan angka ke-2 yaitu 5, 4 ditukar menjadi 1, 4, 5, 2, 8
Bandingkan angka ke-4 dengan angka ke-3 yaitu 5, 2 ditukar menjadi 1, 4, 2, 5, 8
Bandingkan angka ke-5 dengan angka ke-4 yaitu 5, 8 tetap menjadi 1, 4, 2, 5, 8
Proses Iterasi Kedua
Data hasil iterasi pertama : 1, 4, 2, 5, 8
Bandingkan angka ke-2 dengan angka ke-1 yaitu 1, 4 tetap menjadi 1, 4, 2, 5, 8
Bandingkan angka ke-3 dengan angka ke-2 yaitu 4, 2 ditukar menjadi 1, 2, 4, 5, 8
Bandingkan angka ke-4 dengan angka ke-3 yaitu 4, 5 tetap menjadi 1, 2, 4, 5, 8
Bandingkan angka ke-5 dengan angka ke-4 yaitu 5, 8 tetap menjadi 1, 2, 4, 5, 8
karena masih ada penukaran, maka dilanjutkan ke proses iterasi ketiga
Proses Iterasi Ketiga
Data hasil interasi kedua : 1, 2, 4, 5, 8
Bandingkan angka ke-2 dengan angka ke-1 yaitu 1, 2 tetap menjadi 1, 2, 4, 5, 8
Bandingkan angka ke-3 dengan angka ke-2 yaitu 2, 4 tetap menjadi 1, 2, 4, 5, 8
Bandingkan angka ke-4 dengan angka ke-3 yaitu 4, 5 tetap menjadi 1, 2, 4, 5, 8
Bandingkan angka ke-5 dengan angka ke-4 yaitu 5, 8 tetap menjadi 1, 2, 4, 5, 8
Setelah proses iterasi ketiga tidak ada penukaran, proses pengurutan selesai.
Data setelah pengurutan : 1, 2, 4, 5, 8
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:
Urutkan data : 2, 3, 7, 6, 5 secara ascending (dari kecil sampai terbesar) menggunakan teknik Insertion sort.
Proses Iterasi pertama
Data Awal : 2, 3, 7, 6, 5
Bandingkan angka kedua dengan angka pertama yaitu 2, 3 ,
maka urutan tetap 2, 3, 7, 6, 5
Proses Iterasi kedua
Data hasil iterasi sebelumnya: 2, 3, 7, 6, 5
Bandingkan angka ketiga dengan angka kedua yaitu 3, 7,
maka urutan tetap 2, 3, 7, 6, 5
Proses Iterasi ketiga
Data hasil iterasi sebelumnya: 2, 3, 7, 6, 5
Bandingkan angka keempat dengan angka ketiga yaitu 7, 6,
maka sisipkan 6 sebelum 7 menjadi 2, 3, 6, 7, 5
Bandingkan lagi angka 6 dengan angka sebelumnya (angka kedua) yaitu 3, 6,
maka tetap menjadi 2, 3, 6, 7, 5
Proses Iterasi keempat
Data hasil iterasi sebelumnya: 2, 3, 6, 7, 5
Bandingkan angka kelima dengan angka keempat yaitu 7, 5,
maka sisipkan 5 sebelum 7 menjadi 2, 3, 6, 5, 7
Bandingkan lagi angka 5 dengan angka sebelumnya (angka ketiga) yaitu 6, 5,
maka sisipkan 5 sebelum 6 menjadi 2, 3, 5, 6, 7
Bandingkan lagi angka 5 dengan angka sebelumnya (angka kedua) yaitu 3, 5,
maka urutan tetap menjadi 2, 3, 5, 6, 7
proses insertion sort selesai, data setelah pengurutan : 2, 3, 5, 6, 7
Selection sort merupakan sebuah teknik pengurutan dengan cara mencari nilai tertinggi / terendah dari data kemudian menempatkan nilai tersebut di tempat semestinya.
Ascending (naik): memilih elemen terkecil dari data yang belum urut di setiap iterasi dan menempatkan elemen itu di awal data yang belum urut tersebut
Desdending (turun) : memilih elemen terbesar dari data yang belum urut di setiap iterasi dan menempatkan elemen itu di awal data yang belum urut tersebut
Ilustrasi selection sort:
Urutkan data : 2, 3, 7, 6, 5 secara ascending (dari kecil sampai terbesar) menggunakan teknik selection sort.
Proses Iterasi pertama
Data hasil iterasi sebelumnya: 2, 3, 6, 7, 5
Asumsikan data terkecil adalah data pertama
terkecil = 2
Ambil data kedua, didapatkan 3, maka tetap terkecil = 2
Ambil data ketiga, didapatkan 6, maka tetap terkecil = 2
Ambil data keempat, didapatkan 7, maka tetap terkecil = 2
Ambil data kelima, didapatkan 5, maka tetap terkecil = 2
Jadi terkecil =2 sudah tepat di posisi pertama menjadi: 2 , 3, 6, 7, 5
Proses Iterasi kedua
Data hasil iterasi sebelumnya: 2 , 3, 6, 7, 5
Asumsikan data terkecil adalah data kedua
terkecil = 3
Ambil data ketiga, didapatkan 6, maka tetap terkecil = 3
Ambil data keempat, didapatkan 7, maka tetap terkecil = 3
Ambil data kelima, didapatkan 5, maka tetap terkecil = 3
Jadi terkecil = 3 sudah tepat di posisi kedua menjadi: 2 , 3, 6, 7, 5
Proses Iterasi ketiga
Data hasil iterasi sebelumnya: 2 , 3, 6, 7, 5
Asumsikan data terkecil adalah data ketiga
terkecil = 6
Ambil data keempat, didapatkan 7, maka tetap terkecil = 6
Ambil data kelima, didapatkan 5, maka ganti terkecil = 5
Tukar data 5 dengan 6 menjadi: 2 , 3, 5 , 7, 6
Proses Iterasi keempat
Data hasil iterasi sebelumnya: 2 , 3, 5 , 7, 6
Asumsikan data terkecil adalah data keempat
terkecil = 7
Ambil data kelima, didapatkan 6, maka ganti terkecil = 6
Tukar data 6 dengan 7 menjadi 2 , 3, 5, 6, 7
pengurutan selesai data setelah pengurutan : 2, 3, 5, 6 , 7