Berbagi Ilmu: 3 Metode Sorting Dalam
Struktur Data
Yang termasuk dalam sorting data
adalah:
1.Bubble sort(Metode Gelembung)
2. Selection Sort (Metode Seleksi)
3. Insertion Sort (Metode
Penyisipan)
==>Bubble Sort
Bubble Sort merupakan cara
pengurutan yang sederhana. Konsep dari ide dasarnya
adalah seperti“gelembung air” untuk
elemen struktur data yang semestinya berada
pada posisi awal.
Cara kerjanya adalah dengan
berulang-ulang melakukan traversal(proses looping) terhadap elemen-elemen
struktur data yang belum diurutkan. Di dalam traversal tersebut,nilai dari dua
elemen struktur data dibandingkan. Jika ternyata urutannya tidak sesuai dengan
“pesanan”,maka
dilakukan pertukaran (swap).
Algoritma sorting ini disebut juga dengan comparison sort dikarenakan hanya
mengandalkan perbandingan nilai elemen untuk mengoperasikan elemennya.
Algoritma Bubble Sort Algoritma bubble sort dapat diringkas sebagai berikut,
jika N adalah panjang elemen struktur data, dengan elemen-elemennya adalah T1,
T2, T3, …, TN-1,TN,
maka:
1.) Lakukan traversal untuk membandingkan dua elemen
berdekatan. Traversal ini dilakukan dari belakang.
2.) Jika elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak, lanjutkan
ke proses traversal berikutnya sampai
bertemu dengan bagian struktur data yang telah diurutkan.
3.)
Ulangi langkah di atas untuk struktur data yang tersisa.
Contoh program Bubble sort :
Hasil setelah program dijalankan
akan seperti ini :
==>Insertion Sort
Cara kerja insertion sort
sebagaimana namanya.Pertama-tama, dilakukan proses iterasi, dimana di setiap
iterasi insertion sort memindahkan nilai elemen,kemudian menyisipkannya
berulang-ulang sampai ketempat yang tepat. Begitu seterusnya dilakukan. Dari proses
iterasi, seperti biasa, terbentuklah bagian yang telah di-sorting dan bagian
yang belum.
Algoritma Insertion Sort. Algoritma
Insertion Sort dapat dirangkum sebagai berikut:
1.) Simpan nilai Ti kedalam variabel
sementara, dengan i = 1.
2.) Bandingkan nilainya dengan
elemen sebelumnya.
3.) Jika elemen sebelumnya (Ti-1)
lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1
tersebut. Decrement i (kurangi nilainya dengan 1).
4.) Lakukan terus poin ke-tiga,
sampai Ti-1 ≤ Ti.
5.)Jika Ti-1 ≤ Ti terpenuhi, tindih
nilai di Ti dengan variabel sementara yang disimpan sebelumnya.
6.) Ulangi langkah dari poin 1 di
atas dengan i di-increment (ditambah satu).
Contoh Program Insertion Sort
Hasil output program:
==>Selection Sort
Algoritma sorting sederhana yang
lain adalah Selection Sort. 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.
Algoritma Selection Sort Algoritma
selection sort dapat dirangkum sebagai berikut:
1.) Temukan nilai yang paling
minimum (atau sesuai keinginan) di dalam struktur data. Jika ascending, maka
yang harus ditemukan adalah nilai yang paling minimum. Jika descending, maka
temukan nilai yang paling maksimum.
2.) Tukar nilai tersebut dengan nilai pada
posisi pertama di bagian struktur data yang belum diurutkan.
3.) Ulangi langkah di atas untuk
bagian struktur data yang tersisa.
Contoh Program Selection Sort
EmoticonEmoticon