SORTIR

Secara umum sortir dapat dilakukan terhadap suatu himpunan bilangan ataupun terhadap himpunan string ataupun himpunan lain yang bersifat ordinal. 

Ada 2 bilangan sortir berdasar media yang digunakan.

1.Sortir internal, Metode ini dipakai jika himpunan data yang akan disortir itu adalah kecil sehingga proses sortir tidak membutuhkan tempat yang besar di memori utama computer.

2.Sortir Eksternal, Metode ini baik untuk dipakai jika himpunan data yang akan disortir cukup besar. Disini kita membutuhkan media atau alat tambahan seperti magnetic tape, disket, dan sebagainya.

Metode Sortir Gabung (Merge Sort)

Misalkan kita mempunyai 200 record yang akan kita sortir namun hanya 1000 record yang dapat disimpan didalam memori utama. Masalah ini akan diselesaikan dengan suatu metode “Sortir Gabung”. Yakni record 1 sampai 1000, dan 1001 sampai dengan 2000. Hasil penerapan dari sortir internal terhadap masing-masing kelompok, akan berbentuk dua buah sublist terurut. Kemudian kedua sublist tersebut kita gabung(merge) menghasilkan file yang terurut yang kita inginkan.

Metode Sortir Natural Merge dan Balanced Merge

Ada beberapa jenis sorting gabung diantaranya sorting gabung natural (natural merge) dan sortir gabung seimbang (balance merge).

Jika pada natural merge kita menggunakan 1 output file, maka balanced merge banyaknya output file tergantung pada input filenya. Bila kita gunakan 2 way balanced merge, maka input file ada 2 dan output file ada 2 pula sedangkan jika dengan 3 way balanced merge, maka input file ada 3 dan output file ada 3. Secara umum, jika digunakan M-way balanced merge , maka terdapat M buah input file dan M buah output file.

Balanced Merge

Balanced Merge adalah metode yang paling sederhana dan mudah untuj menggabungkan file partisi yang dihasilkan dari pengolahan suatu file yang tidak disortir. Metode ini benar-benar efeltof dan diperbaiki dengan mengelompokannya dalam 2-way, 3-way atau merge M-way  yang urutannya lebih tinggi.

Teknik Sortir Penyisipan

Dua hal yang mempengaruhi kecepatan algoritma sortir adalah perbandingan yang dilakukan dan jumlah operasi pemindahan data dilakukan. Berlainan dengan proses pencarian data, pada proses sortir data juga harus diperhatikan jumlah pemindahan data atau data movement yang dilakukan. Hal ini penting sekali karena pada proses sortir, isi daftar sebagai input akan berubah menjadi output daftar yang sudah terurut. 

Pada garis besarnya ada tiga teknik utama yang dapat dilakukan dalam melakukan sortir. Ketiga teknik tersebut adalah

1.Sortir penyisipan atau insertion sort

2.Sortir pemilihan atau selection sort

3.Sortir penukaran atau exchange sort

Teknik  Sortir Pemilihan

Algoritma sortir pemilihan atau selection sort bekerja berdasarkan prinsip berikut :

1.Pilih data dengan key terkecil

2.Tukarkan data tersebut dengan elemen a[1].

Teknil  Sortir Penukaran

Algoritma yang termasuk didalam kelas ini mempunyai ciri khusus yakni dengan membandingkan dan apabila urutan data tidak terpenuhi diadakan pertukaran. Seperti hanya algoritma pada selection sort pada tiap iterasi, data denga key terkecil dalam sisa daftar akan bergerak ke bagian kiri dan sisa daftar tersebut. Algoritma yang paling sederhana dan termasuk ke dalam kelas ini adalah sortir gelembung atau bubble sort.

Sumber : Pengantar Struktur Data, D.Suyadi H.S, Universitas Gunadarma