1. Bubble Sort
Bubble sort (metode gelembung) adalah metode/algoritma
pengurutan dengan dengan cara melakukan penukaran data dengan tepat
disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi
tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah
terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan
lambat menggelembung ke posisinya yang tepat.
Metode pengurutan gelembung
(Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air.
Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka
gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada
pengurutan gelembung.
Algoritma bubble sort
adalah salah satu algoritma pengurutan yang paling simple, baik dalam hal
pengertian maupun penerapannya. Ide dari algoritma ini adalah mengulang proses
pembandingan antara tiap-tiap elemen
array dan menukarnya
apabila urutannya salah. Pembandingan elemen-elemen ini akan terus diulang
hingga tidak perlu dilakukan penukaran lagi. Algoritma
ini termasuk dalam
golongan algoritma comparison sort, karena menggunakan perbandingan dalam
operasi antar elemennya. Berikut ini adalah gambaran dari algoritma bubble
sort. Misalkan kita mempunyai sebuah array dengan. Elemen-elemen “4 2 5 3 9”. Proses yang akan
terjadi apabila digunakan algoritma bubblesort adalah sebagai berikut.
Pass pertama
(4 2 5 3 9) menjadi (2 4
5 3 9)
(2 4 5 3 9) menjadi (2 4
5 3 9)
(2 4 5 3 9) menjadi (2 4
3 5 9)
(2 4 3 5 9) menjadi (2 4
3 5 9)
Pass kedua
(2 4 3 5 9) menjadi (2 4
3 5 9)
(2 4 3 5 9) menjadi (2 3
4 5 9)
(2 3 4 5 9) menjadi (2 3
4 5 9)
(2 3 4 5 9) menjadi (2 3
4 5 9)
Pass ketiga
(2 3 4 5 9) menjadi (2 3
4 5 9)
(2 3 4 5 9) menjadi (2 3
4 5 9)
(2 3 4 5 9) menjadi (2 3
4 5 9)
(2 3 4 5 9) menjadi (2 3
4 5 9)
Dapat dilihat pada proses
di atas, sebenarnya pada pass kedua, langkah kedua, array telah terurut. Namun
algoritma tetap dilanjutkan hingga pass kedua berakhir. Pass ketiga dilakukan
karena definisi terurut dalam algoritma bubblesort adalah tidak ada satupun
penukaran pada suatu pass, sehingga pass ketiga dibutuhkan untuk memverifikasi
keurutan array tersebut.
2 SELECTION SORT
Selection Sort merupakan salah satu
algoritma pengurutan yang sederhana. Ide dasarnya adalah melakukan beberapa
kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting
ascending (menaik), elemen yang paling kecil di antara elemen-elemen yang belum
urut, disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan
indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut.
Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang
disimpan indeksnya kemudian ditukar.
Selection Sort diakui karena
kesederhanaan algoritmanya dan performanya lebih bagus daripada algoritma lain
yang lebih rumit dalam situasi tertentu. Algoritma ini bekerja sebagai berikut:
- Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list
- Menukarkan nilai ini dengan elemen pertama list
- Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua
Secara efisien
kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang
didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan
bagian list yang elemennya akan diurutkan.
3 Insertion sort
Penganalogian Insertion Sort dengan pengurutan kartu
Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingi mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.
1. Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. Dan anggaplah kita akan menyusun kartu ke tangan kiri kita.
2. Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
3. Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
4. Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang).
Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya.
Demikian juga halnya dalam pengurutan data.
Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.
Catatan : Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.