Macam-macam Teknik Pensortiran
Tuesday, October 21, 2014
Nama : Marla Nur Assyifa
NPM : 56414412
Kelas : 1IA17
Mata Kuliah : Algoritma Pemrograman 1A
Dosen : Kunto Bayu A,ST
Sorting data merupakan suatu proses penyusunan kembali data yang sebelumnya telah
disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut
aturan tertentu. Berikut macam-macam pengurutan data :
- Ascending, merupakan pengurutan dari angka yang nilainya lebih kecil kemudian menuju ke nilainya yang lebih besar.
- Descending, pengurutan dari nilainya yang lebih besar kemudian menuju ke nilainya yang lebih kecil.
Contoh : diberikan data berupa bilangan berikut ini= 4 9 7 3 8 1
Hasil sorting:
- Ascending : 1 3 4 7 8 9
- Descending : 9 8 7 4 3 1
Macam-macam Sorting
1. Bubble
Sort
Memindahkan elemen sekarang dengan elemen berikutnya , jika elemen
sekarang itu lebih besar atau lebih kecil dari elemen berikutnya maka di tukar
(berpindah posisi).
Proses Bubble Sort
- Ascending
- Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih kecil maka ditukar.
- Descending
- Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih besar maka ditukar.
Contoh Bubble Sort
2. Exchange Sort
Exchange sort mirip dengan buble sort. Bedanya jika bubble sort,
proses pertukarannya harus sistematis dari awal atau dari belakang. Sedangkan
exchange sort, proses pertukaran hanya akan dilakukan jika diperlukan saja.
Proses Exchange Sort
- Ascending
- Jika elemen sesudahnya lebih kecil dari elemen sebelumnya, maka ditukar
- Descending
- Jika elemen sesudahnya lebih besar dari elemen sebelumnya, maka ditukar
Contoh Exchange Sort
3. Selection
Sort
Memindahkan elemen dengan cara membandingkan elemen sekarang dengan
elemen yang berikutnya sampai dengan elemen terakhir. Jika ditemukan elemen
lain yang lebih kecil / lebih besar dari elemen sekarang maka dicatat posisinya
dan kemudian ditukar dan begitu seterusnya.
Proses Selection Sort
- Ascending
- Elemen
yang paling besar diletakkan di akhir
- Elemen
yang paling kecil diletakkan di awal
- Descending
- Elemen
yang paling kecil diletakkan di akhir
- Elemen
yang paling besar diletakkan di awal
Contoh Selection Sort
4. Insertion
Sort
Pengurutan yang dilakukan dengan cara membandingkan dengan data kedua sampai data terakhir. Jika ditemukan data yang lebih kecil atau lebih besar,
maka data tersebut disisipkan kedepan sesuai posisi yang seharusnya.
Contoh Insertion Sort
5. Shell
Sort
Proses pengurutan data yang sebelumnya acak menjadi data yang
terurut dengan cara menentukan jarak antar elemen yang akan dibandingkan.
Pada langkah
pertama, kita ambil elemen pertama dan kita bandingkan dengan elemen pada jarak tertentu dari elemen pertama
tersebut. Kemudian elemen kedua kita bandingkan dengan elemen lain dengan
jarak yang sama. Demikian
seterusnya sampai seluruh elemen dibandingkan. Pada langkah kedua proses
diulang dengan langkah yang lebih kecil, pada langkah ketiga jarak
tersebut diperkecil lagi. Seluruh proses dihentikan jika jarak sudah sama
dengan satu.
Contoh Shell Sort
6. Merge
Sort
Proses pengurutan data yang menggunakan merging dua buah
vecktor. Pada proses merge sort, data dibuat sepasang-sepasang, yang terdiri
dari dua elemen. Jika N ganjil, maka ada satu vektor yang terdiri dari 1
elemen. Lalu kemudian data tersebut di merging sampai terurut.
Contoh Merge Sort
7. Quick
Sort
Proses penyusunan elemen yang membandingkan suatu elemen (pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen-elemen lain yang lebih kecil dari pivot terletak disebelah kiri pivot. Elemen yang lebih besar dari pivot terletak disebelah kanan pivot. Dengan demikian, akan terbentuk dua sublist yang terletak disebelah
kanan dan kiri pivot. Lalu pada sublist kiri dan kanan itu kita anggap sebuah
list baru dan kita kerjakan proses yang sama seperti yang sebelumnya. Demikian
seterusnya sampai tidak terdapat sublist lagi.
Contoh Quick Sort
Proses :
- Bilangan yang di dalam kurung merupakan pivot
- Persegi panjang yang digambarkan dengan garis terputus-putus menunjukkan sublist
- i bergerak dari sudut kiri ke kanan sampai mendapatkan nilai yang lebih besar atau sama dengan pivot
- j bergerak dari sudut kanan ke kiri sampai menemukan nilai yang lebih kecil dari pivot
- i berhenti pada index ke 1 karena langsung mendapatkan nilai yang lebih besar dari pivot (15)
- j berhenti pada index ke 6 karena langsung mendapatkan nilai yang lebih kecil dari pivot
- Karena i<j, maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi : 2 10 15 3 8 22
- i berhenti pada index ke 3 karena tidak menemukan bilangan yang lebih besar dari pivot
- j berhenti pada index ke 5 menunjukan pada nilai yang lebih kecil dari pivot
- Karena i<j, maka data yang ditunjuk oleh i (pivot) ditukar dengan data yang ditunjuk oleh j sehingga menjadi : 2 10 8 3 15 22
- Proses yang sama seperti sebelumnya dilakukan terhadap dua buah sublist yang baru (ditandai dengan persegi panjang dengan garis terputus-putus). Dan menghasilkan : 2 3 8 10 15 22
Sumber:
- http://risasisteminformasi.blogspot.com/2013/02/sorting-pengurutan.html
- http://kael9001.blogspot.com/2013/02/bubble-sort.html
- http://elearning.gunadarma.ac.id/docmodul/pengantar_struktur_data/bab6-sortir.pdf
0 comments