Konsep Beberapa Jenis Sorting Pada Pemrograman
Bubble Sort
Bubble sort merupakan salah satu metode sorting yang paling sederhana dan paling umum digunakan. Secara sederhana, algoritma Bubble Sort yaitu pengurutan dengan cara pertukaran data dengan data di sebelahnya secara terus menerus hingga tidak ada lagi perubahan. Keunggulan bubble sort ini yaitu konsepnya yang sederhana dan mudah dipahami, sehingga implementasi ke dalam source code menjadi lebih mudah. Walaupun sederhana, metode ini dinilai tidak efisien karena ketika mengurutkan data yang sangat besar akan sangat lambat prosesnya. Untuk kasus terburuknya, bubble sort dapat memiliki kompleksitas waktu O(n2). Bubble sort lebih tepat digunakan pada dataset yang tidak terlalu besar dan juga pada dataset yang hampir terurut, sehingga tidak terlalu memerlukan terlalu banyak pertukaran.
Salah satu contoh kasus yang lebih tepat menggunakan bubble sort yaitu ketika suatu mesin yang hanya memiliki 2 buah register dan tidak memiliki RAM. Mesin ini ingin mengurutkan beberapa data yang terdapat pada suatu tape. Mesin ini hanya bisa membaca tape secara 1 arah, dan ketika mesin ini membaca 2 buah data, mesin ini bisa memilih untuk menukar kedua datanya, atau melanjutkan proses pembacaan tape. Ketika sudah berada di akhir tape, kita bisa memilih untuk me-rewind kembali tape tersebut sebanyak yang kita butuhkan, dengan catatan kita hanya bisa me-rewind ke awal isi tape, tidak ke sembarang posisi dari tape. Konsep ini sama dengan proses yang terjadi pada bubble sort. Oleh karena itu, algoritma bubble sort sangat cocok dipakai pada kondisi ini, walaupun kondisi ini sangat jarang ditemui.
Berikut ini merupakan contoh implementasi bubble sort pada java :
Ketika source code tersebut dijalankan, maka hasilnya akan jadi seperti berikut :
Selection Sort
Selection sort merupakan salah satu metode pengurutan data, dimana algorimtanya yaitu program akan mencari elemen terkecil dari sebuah untuk masing-masing tempat. Konsep dari selection sort ini juga termasuk yang mudah dipahami, sehingga implementasi dalam source code menjadi lebih mudah. Namun, selection sort ini hanya akan efisien jika digunakan pada data yang berjumlah sedikit. Ketika data bertambah banyak, selection sort menjadi tidak efisien, bahkan ketika datanya sudah hampir terurut. Untuk kasus terburuknya, selection sort dapat memiliki kompleksitas waktu O(n2). Berikut ini merupakan contoh implementasi selection sort pada java :
Ketika source code tersebut dijalankan, maka hasilnya akan jadi seperti berikut :
Insertion Sort
Ide dasar dari algoritma insertion sort adalah mencari posisi yang tepat untuk setiap elemen array. Algoritma ini dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Insertion sort lebih cocok digunakan untuk mengurutkan data yang sudah hampir terurut atau data yang berjumlah sedikit. Untuk kasus terburuknya, selection sort dapat memiliki kompleksitas waktu O(n2). Berikut ini merupakan contoh implementasi insertion sort :
Ketika source code tersebut dijalankan, maka hasilnya akan jadi seperti berikut :
Source code dari program-program di atas dapat diakses disini
References :
- https://www.geeksforgeeks.org/bubble-sort/
- https://www.geeksforgeeks.org/selection-sort/
- https://www.geeksforgeeks.org/insertion-sort/
- https://www.quora.com/What-is-the-use-of-bubble-sort
- https://stackoverflow.com/questions/736920/is-there-ever-a-good-reason-to-use-insertion-sort
- https://www.quora.com/When-should-one-use-Insertion-vs-Selection-sort
Comments
Post a Comment