Sort / Pengurutan
- Waktu yang paling banyak dihabiskan dalam pengelolaan file adalah waktu untuk menata ulang record dan waktu aktivitas pencarian.
- Alasan diperlukan pengurutan data :
- Penyajian data :Hasil laporan dari analisis data dari file dapat disajikan kepada user dengan cepat dan akurat.
- Penggabungan file :Adanya 2 atau lebih file dengan susunan record yang berbeda harus digabungkan untuk keperluan analisis data.
- Pembuatan index : Index diperlukan untuk proses pencarian data.
- Dalam system penyortiran dikenal 2 metode, yaitu :
- Metode Sort Internal
- Metode Sort Eksternal
PengurutanEksternal
- Ketika data yang akan disortir terlalu besar untuk dapat masuk kedalam memori utama, maka diperlukan Pengurutan Eksternal (External Sorting).
- Algoritma External Sorting ini digunakan untuk meminimalkan waktu akses disk.
- Pengurutan eksternal yang paling efektif adalah algoritma Merge Sort.
- Pengurutan eksternal merge sort dibagi dalam 2 tahap, yakni :
- Sort Phase : Pengurutan terhadap masing-masing blok file sumber dan mengisinya kedalam sort-block buffer.
- Merge Phase : Penggabungan blok-blok file sumber yang telah terurut di dalam buffer menjadi 1 blok file tujuan.
Contoh
Sebuah file berisi 2000 record harus disortir kedalam memori yang hanya dapat menampung 1000 record sekaligus. Untuk itu digunakan metode sort eksternal.
Langkah-langkah penyortiran ini adalah :
- Record-record dibagi kedalam beberapa file agar dapat ditampung sekaligus di memori komputer, lalumasing-masing bagian disortir internal. Bagian-bagian file yang terlah tersortir ini disebut sorted sublist.
Maka didapat :
ü Sorted sublist 1 (record 1 – 1000) dan
ü Sorted sublist 2 (record 1001 – 2000)
Contoh
- Setelah itu kedua sorted sublist ini (RUN) digabung (merge), sehingga didapat berkas gabungan (merge file) yang record-recordnya telah disortir.
PengurutanEksternal
v Faktor-faktor yang mempengaruhi metode sort eksternal :
- Jumlah record yang akan disortir
- Ukuran record (panjang record)
- Jumlah storage yang digunakan
- Kapasitas internal memori
- Distribusi nilai key dalam input file
v Teknik sort/merge file ini berbeda satu dengan yang lainnya dalam hal :
- Metode sort internal yang digunakan
- Jumlah main memori yang disediakan untuk sort internal
- Distribusi dari sorted sublist di secondary storage menjadi satu atau lebih file gabungan dalam satu langkah gabungan (merge pass)
TeknikPengurutanEksternal
- Natural Merge,adalah M input file dan hanya 1 output file.
- Balanced Merge, adalah M input file, maka file yang dipakai adalah2 M file. Jumlah input file sama dengan jumlah output file, walaupun pada akhirnya takadalagi keseimbangan antara input dan output file.
- Polyphase Merge, adalah Pada M way polyphase merge digunakan 2 M-1 input file dengan 1 output file.
- Cascade Merge, Jenis lain dari unbalanced merge yang berusaha mengurangi penyalinan/copy dari record-record.
- Cascade merge dengan derajat M menggunakan : 2 M-1, 2 M-2, 2 M-3, … , kemudian 2 input file selama merge
- Setiap merge pass dimulai dengan merge dari : 2 M-1 input file ke 1 output file
Two-Way Merge Sort
- External Sorting memanfaatkan algoritma Two-Way Merge Sort.
- Hanya memanfaatkan 3 halaman memori utama, sedangkan halaman memori utama yang tersedia sangat banyak.
- Pengurutan dilakukan dalam beberapa tahap.
- Tahap pertama, halaman dalam file dibaca satu per satu, record didalamnya diurutkan dan halaman yang telah terurut ditulis kembali.
- Pengurutan di dalam halaman dapat menggunakan algoritma pengurutan yang umum digunakan.
- Pada tahap berikutnya, pasangan run dari output pada tahap sebelumnya akan dibaca dan digabungkan untuk menghasilkan run yang panjangnya 2 kali lipat sebelumnya.
- Jika jumlah halaman dalam file input = 2k, untuk beberapa k, maka :
- Tahap 0 diperoleh 2k run terurut masing-masing 1 halaman
- Tahap 1 diperoleh 2k–1 run terurut masing-masing 2 halaman
- Tahap 2 diperoleh 2k–2 run terurut masing-masing 4 halaman
- Tahap k diperoleh 1 run 2khalaman terurut
- Algoritma ini hanya menggunakan 3 halaman buffer dalam memori utama, meskipun ruang buffer yang dimiliki lebih dari 3, algoritma ini tidak memanfaatkannya secaraefektif.
- Pengembangan dari algoritma ini adalah algoritma External Merge Sort yang akan memanfaatkan ruang buffer yang tersedia secara efektif.
External Merge Sort
- Jika memori utama memiliki halaman buffer sebanyak B ruang buffer, maka untuk mengurutkan file yang besar yang memiliki N halaman, maka :
– Tahap 0, baca B halaman dan urut secara internal, diperoleh run éN / Bùuntuk masing-masing B halaman (kecuali run terakhir yang mungkin berisi sedikit halaman).
– Tahap i = 1, 2, …,baca (B – 1) halaman buffer untuk input dan gunakan sisa halaman untuk output, dengan demikian, telah dilakukan (B – 1) cara penggabungan dalam tiap tahap.
- Jika ingin mengurutkan file yang memiliki 108 halaman dengan menggunakan buffer 5 halaman, maka :
– Tahap 0 diperolehé108 / 5ù = 22 run terurut dengan masing-masing 5 halaman, kecuali run terakhir yang hanya 3 halaman.
– Tahap 1 diperolehé22 / 4ù = 6 run terurut dengan masing-masing 20 halaman, kecuali run terakhir yang hanya 8 halaman.
– Tahap 2 diperolehé6 / 4ù = 2 run terurut dengan 1 run 80 halaman dan sisanya 28 halaman.
– Tahap 3 diperolehé2 / 2ù = 1 run dengan menggabungkan 2 run dari tahap 2 untuk menghasilkan file terurut.
Muhammad Iqbal 