Sorting - Pengurutan Data - Struktur Data

Pengurutan atau “Sorting“ adalah suatu proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu ( untuk data yang bertipe numerik atau karakter).

Dua Macam Pengurutan

• Ascending (urut naik) merupakan pengurutan dari angka yang nilainya lebih kecil kemudian menuju ke nilainya yang lebih besar.
• Descending (urut turun) adalah sebaliknya, yaitu pengurutan dari nilainya yang lebih besar kemudian menuju ke nilainya yang lebih kecil.

Macam-Macam Sorting


1. Bubble Sort

Memindahkan element sekarang dengan elemen berikutnya , jika elemen sekarang itu lebih besar / lebih kecil dari elemen berikutnya maka di tukar (berpindah posisi).

 Ascending

• Data yang paling awal dibandingkan dengan data berikutnya jika ternyata lebih besar maka tukar.
• Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih kecil maka tukar.

Descending

• Data yang paling awal dibandingkan dengan data berikutnya jika ternyata lebih kecil maka tukar.
• Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih besar maka tukar.

Contoh Bubble Sort
Ascending (Urutan Naik) 

2. Exchange Sort

Exchange sort itu sangat mirip dengan buble sort. Bahkan banyak yang mengatakan bahwa exchange sort sama 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.

1. Ascending

• Jika terdapat elemen sebelumnya lebih besar dari elemen berikutnya maka tukar.
• Jika terdapat elemen sesudahnya lebih kecil dari elemen sebelumnya maka tukar.

2. Descending

• Jika terdapat elemen sebelumnya lebih kecil dari elemen berikutnya maka tukar.
• Jika terdapat elemen sesudahnya lebih besar dari elemen sebelumnya maka tukar.

Contoh Exchange Sort

Ascending (Urutan Naik)

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.

1. Ascending

• Elemen yang paling besar diletakkan di akhir.
• Elemen yang paling kecil diletakkan di awal.

2. Descending

• Elemen yang paling kecil diletakkan di akhir.
• Elemen yang paling besar diletakkan di awal.

Contoh Selection Sort
Ascending (Urutan Naik)

4. Insertion Sort

Pengurutan yang dilakukan dengan cara membandingkan dengan data ke-2 sampai data terakhir. Jika ditemukan data yang lebih kecil atau lebih besar maka data tersebut disisipkan kedepan sesuai posisi yang seharusnya.

Contoh Insertion Sort
Ascending (Urutan Naik)

5. Shell Sort

Merupakan proses pengurutan data yang sebelumnya acak menjadi data yang terurut dengan cara menentukan jarak antar elemen yang akan dibandingkan.

Contoh Shell Sort
Ascending (Urutan Naik)

6. Merge Sort

Merupakan proses pengurutan data yang menggunakan merging dua buah vector. Pada proses merge sort, data dibuat sepasang-sepasang, yang terdiri dari dua elemen. Jika N ganjil, maka ada satu vector yang terdiri dari 1 elemen. Lalu kemudian data tersebut di merging sampai terurut.

Contoh Merge Sort
Ascending (Urutan Naik)

7. Quick Sort

Merupakan proses penyusunan elemen yang membandingkan suatu elemen (pivot) denan elemen yang lain, dan menyusunnya sedemikian rupa sehingga elemen –elemen lain yang lebih kecil dari pivot terletak disebelah kiri pivot. Dan 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.