Pengertian Sorting
Pengurutan data dalam struktur data sangat penting terutama
untuk data yang beripe data numerik ataupun karakter. Pengurutan dapat
dilakukan secara ascending (urut naik) dan descending (urut turun). Pengurutan
(Sorting) adalah proses pengurutan data yang sebelumnya disusun secara acak
sehingga tersusun secara teratur menurut aturan tertentu.
Contoh:
Data Acak :
5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25
Descending : 25 10 8 6 5 3 1
Deklarasi Array Sorting
Mendeklarasikan array secara global:
int data[100];
int n; //untuk jumlah data
Fungsi Tukar 2 Buah
Data:
void tukar(int a,int
b)
{
int tmp;
tmp = data[a];
data[a] = data[b];
data[b] = tmp;
}
Sorting merupakan suatu proses untuk menyusun kembali himpunan
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.
Mengapa harus melakukan sorting data?
Ada banyak alasan dan keuntungan
dengan mengurutkan 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.
Metode-metode sorting meliputi:
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 program setelah dijalankan:
==>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 :
Hasil setelah dijalankan:
Sekianlah pembahasan saya tentang Materi Sorting kali ini
^,^
Sumber:
1.Referensi dari Buku : ALGORITMA DAN PEMROGRAMAN DENGAN C++
(edisi II)
Oleh : Andri Kristanto,S.Kom
2. http://www.academia.edu/6136390/laporan_sorting_script_di_dalamnya_juga_searching_kok_
