PERTEMUAN 13 SORT DAN MERGE FILE
Juli 14, 2020SORT DAN MERGE FILE
SORT / PENGURUTAN
Waktu yang paling banyak dihabiskan dalam pengelolaan file adalah waktu untuk menata ulang record dan waktu aktivitas pencarian.
A. Pengertian Sort
Sort merupakan suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu.
B. Alasan diperlukan pengurutan data :
a. Penyajian data : Hasil laporan dari analisis data dari file dapat disajikan kepada user dengan cepat dan akurat.
b. Penggabungan file : Adanya 2 atau lebih file dengan susunan record yang berbeda harus digabungkan untuk keperluan analisis data.
c. Pembuatan index : Index diperlukan untuk proses pencarian data.
C. Metode dalam sistem penyortiran :
a. Metode sort internal
b. Metode sort eksternal
D. Perbedaan Metode sort internal dan metode sort eksternal
a. Pada metode sort internal, semua record yang akan diproses dimuat kedalam memori komputer lalu diproses sort (sortir).
b. Pada metode sort eksternal, record-record yang diproses tidak semuanya dapat dimuat kedalam memori komputer, karena keterbatasan memori komputer. Metode sort eksternal didalam penerapannya nanti, menggunakan pula metode sort internal
E. Contoh
Sebuah file berisi 2000 record harus disortir kedalam memori yang hanya dapat menampung 1000 record sekaligus. Untuk itu digunakan metode sort eksternal.
a. Langkah-langkah dalam penyortiran ini adalah:
Record-record dibagi kedalam beberapa file agar dapat ditampung sekaligus di memori komputer, lalu masing-masing bagian di sortir internal. Bagian-bagian file yang telah tersortir ini disebut sorted sublist.
Maka didapat:
a. sublist 1 (record 1 – 1000) dan
b. Sorted sublist 2 (record 1001 – 2000)
Setelah itu kedua sorted sublist ini (RUN) digabung (merge), sehingga didapat berkas gabungan (merge file) yang record-record nya telah di sortir.
Maka dapat disimpulkan langkah-langkah untuk metode sort eksternal ini adalah:
Sort eksternal, dimana file dibagi menjadi beberapa bagian file, kemudian di sortir.
F. Faktor-faktor yang mempengaruhi metode sort eksternal:
a. Jumlah record yang akan di sortir
b. Ukuran record (panjang record)
c. Jumlah storage yang digunakan
d. Kapasitas internal memori
e. Distribusi nilai key dalam input file.
MERGE
A. Pengertian Merge
Merge, dimana bagian-bagian file ini (sorted sublist) digabung menjadi satu atau lebih file gabungan. File-file gabungan kemudian digabung lagi sampai akhirnya didapatkan sebuah file gabungan yang berisi semua record-record yang telah di sortir. Output, yang menyalin file gabungan yang telah ter sortir ke media storage terakhir.
B. Teknik sort/merge file ini berbeda satu dengan yang lainnya dalam hal:
1. Metode sort internal yang digunakan
2. 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).
C. Teknik sort/merge file, yaitu:
a. Natural Merge
b. Balanced Merge
c. Polyphase Merge
d. Cascade Merge
e. Natural Merge
D. Merge yang menangani 2 input file sekaligus disebut 2 way natural merge.
Merge yang menangani M input file sekaligus disebut M way natural merge.
M menunjukkan derajat merge.
1. Pada natural merge, dibagi lagi menjadi:
a. 2 way natural merge’
b. 3 way natural merge
c. way natural merge
Pada M way natural merge, dapat didefinisikan sebagai merge dengan:
a. M input file dan hanya 1 output file Balanced Merge. Dari metode natural merge kita lihat bahwa, jika kita gunakan M input file, maka file seluruhnya yang kita gunakan adalah M + 1 file. Sedangkan pada balanced merge, jika kita gunakan M input file, maka file seluruhnya yang dipakai adalah 2 M file.
2. Pada balanced merge dibagi lagi menjadi:
a. way balanced merge
b. 3 way balanced merge
c. M way balanced merge
Pada balanced merge, jumlah input file sama dengan jumlah output file, walaupun pada akhirnya tak ada lagi keseimbangan antara input dan output file.
Polyphase Merge
Pada M way polyphase merge digunakan 2M-1 input file dengan 1 output file. Jadi jika kita menggunakan 2 way polyphase Merge, maka banyaknya input file yang digunakan ada 3 input file.
A. Cascade Merge
Jenis lain dari unbalanced merge yang berusaha mengurangi penyalinan/copy dari record-record disebut cascade merge.
B. Cascade merge dengan derajat M menggunakan:
2M-1, 2M-2, 2M-3,…, kemudian 2 input file selama merge
C. Setiap merge pass dimulai dengan merge dari:
2M-1 input file ke 1 output file
Pada cascade merge pendistribusian run-nya sama dengan pendistribusian run pada polyphase merge, hanya berbeda pada phase merge-nya.
0 komentar