 |
Salam Programmer Indonesia, kali ini saya akan membahas tentang sorting, mungkin postingan kali ini agak sedikit meloncat dari permasalahan program sebelumnya, namun ini pun sangat berguna dalam program pascal.
A.
PENGERTIAN SORTING DATA
Sorting
merupakan suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan
tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan
kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa
kunci dalam tiap-tiap elemen. Pada dasarnya ada dua macam urutan yang biasa
digunakan dalam suatu proses sorting:
1.
Urut naik (ascending)
Mengurutkan
dari data yang mempunyai nilai paling kecil sampai paling besar
2.
Urut turun (descending)
Mengurutkan
dari data yang mempunyai nilai paling besar sampai paling kecil.
B.
TUJUAN SORTING DATA
Data yang
terurut mudah untuk dicari, mudah untuk diperiksa, dan mudah untuk dibetulkan
jika terdapat kesalahan. Data yang terurut dengan baik juga mudah untuk dihapus
jika sewaktu-waktu data tersebut tidak diperlukan lagi. Selain itu, dengan
mengurutkan data maka kita semakin mudah untuk menyisipkan data atapun
melakukan penggabungan data.
C.
METODE SORTING DATA
Metode-metode
sorting meliputi:
1.
Bubble Sort (Metode Gelembung)
Bubble Sort adalah metode pengurutan data dengan prinsip: data di lokasi/indeks
I dibandingkan dengan data lain di lokasi/indeks sebelahnya I+1, apabila
terdapat ketidakcocokan data, maka data di lokasi I tersebut akan ditukar
dengan data di lokasi I+1. Maka secara perlahan, data akan bergerak menuju ke
lokasi yang tepat. Dari sifat inilah, istilah bubble yang artinya gelembung diambil. Seperti
gelembung dalam minuman soda, yang perlahan bergerak naik ke atas.
Disajikan
contoh cara kerjanya, untuk 5 buah data yaitu 4, 5, 1, 3, 2. Pengurutan dimulai
dari lokasi pertama (I adalah 1), dan dibandingkan dengan lokasi sebelahnya
(I+1 adalah 2). Karena data 4 dan 5 sudah berada pada urutan yang cocok, maka
tidak terjadi pertukaran. Kemudian dicek data lokasi berikutnya (I adalah 2)
dengan lokasi sebelahnya (I+1 adalah 3), ternyata data 5 dan 1 tidak cocok,
maka ditukar. Lokasi berikutnya (I adalah 3) dibandingkan dengan lokasi
sebelahnya (I+1 adalah 4), ternyata data 5 dan 3, tidak cocok lagi, maka
ditukar lagi. Demikian seterusnya, dikerjakan sampai dipastikan bahwa semua
data ada pada lokasi yang cocok, yang dilakukan dengan cara sudah
tidak ada lagi pertukaran yang dilakukan. Berikut adalah proses perubahan
data untuk contoh data 4, 5, 1, 3, 2 tersebut:
1.
Perulangan Pertama (First
Pass)
4 5 1 3 2 (cocok)
4 5 1 3
2 (tukar 5 dan 1) 4 1 5 3
2
4 1 5 3 2
(tukar 5 dan 3) 4 1 3 5 2
4 1 3 5 2 (tukar
5 dan 2) 4 1 3 2 5
2.
Perulangan Kedua (Second
Pass)
4 1 3 2 5 (tukar 4 dan 1) 1 4 3
2 5
1 4 3 2
5 (tukar 4 dan 3) 1 3 4 2
5
1 3 4 2 5
(tukar 4 dan 2) 1 3 2 4 5
1 3 2 4 5 (cocok)
3.
Perulangan Ketiga (Third
Pass)
1 3 2 4 5 (cocok)
1 3 2 4
5 (tukar 3 dan 2) 1 2 3 4
5
1 2 3 4 5
(cocok)
1 2 3 4 5 (cocok)
4.
Perulangan Keempat (Fourth
Pass)
1 2 3 4 5 (cocok)
1 2 3 4
5 (cocok)
1 2 3 4 5
(cocok)
1 2 3 4 5 (cocok)
Pada waktu Perulangan
Keempat, sudah tidak terjadi pertukaran lagi (semua sudah cocok), maka sudah
dapat dipastikan bahwa semua data sudah berada di lokasi yang tepat.
2.
Selection Sort (Metode Seleksi)
Cara kerja
metode ini didasarkan pada pencarian elemen dengan nilai terkecil. kemudian dilakukan
penukaran dengan elemen ke-I. Secara singkat metode ini bisa dijelaskan sebagai
berikut. Pada langkah pertama, dicari data yang terkecil dari data pertama
sampai terakhir. Kemudian data tersebut kita tukar dari data pertama. Dengan
demikian, data pertama sekarang mempunyai nilai paling kecil dibanding dengan
data lain. Pada langkah kedua, data terkecil kita cari mulai dari data kedua
sampai data terakhir. Data terkecil yang kita peroleh kita tukar dengan data
kedua. Demikian seterusnya sampai seluruh data terurut.
1.
Proses Pertama
i = 1 2
3 4 5 6
22 10 15
3 8 2
Pembanding Posisi
22 > 10 2
10 < 15 2
10 > 3 4
3 < 8 4
3 > 2 6
Posisi data ke-1 (22) = 6
Tukar data ke-1 dengan data ke-6
2 10
15 3 8 22
2.
Proses Kedua
i = 1 2 3
4 5 6
2 10
15 3 8 22
Pembanding Posisi
10 < 15 2
10 > 3 4
3 < 8 4
3 < 22 4
Posisi data ke-2 (10) = 4
Tukar data ke-1 dengan data ke-4
2 3 15
10 8 22
3.
Insertion Sort (Metode Penyisipan)
Pengurutan dilakukan
dengan cara membandingkan data ke-I (dimana I dimulai dari data ke-2 sampai
dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih
kecil maka data tersebut disisipkan ke depan sesuai posisi yang seharusnya.
1.
Proses Pertama
i = 1 2
3 4 5 6
22 10 15
3 8 2
Temp cek geser
10 temp<22 data ke-1 -> posisi 2
Temp
menempati posisi ke-1
10
22 15 3
8 2
2.
Proses Kedua
i = 1 2
3 4 5 6
10 22 15 3 8 2
Temp cek geser
15 temp<22 data ke-2 -> posisi 3
Temp>10
Temp
menempati posisi ke-2
10
15 22 3
8 2
Sekian pembahasan kali ini, mohon maap jika postingannya kurang dimengerti untuk pertanyaan lebih lanjut boleh dikolom komentar.
Terimakasih
Salam Programmer Indonesia