PENGGABUNGAN
EKSTERNAL DENGAN KESEIMBANGAN P-WAY
Karena kendala utama untuk menggunakan pengurutan
gabungan sebagai rutin pengurutan eksternal adalah diperlukannya ruitin
pengurutan eksternal jumlah besar berkas pada saat awal, maka perlu melakukan modifikasi
proses penggabungan untuk membatasi jumlah berkas yang terbuka.
Berkas asli didekomposisi menjadi beberapa “run” dengan
cara melkukan pengurutan internal terhadap sejumlah besar blok rekaman yang
dapat dibuat dalam memori utama. “Keseimbangan” dalam nama ini merupakan hasil
dari kenyataan bahwa “run” dihasilkan merata pada P buah berkas eksternal.
Berkas-berkas tersebut bisa berada secara fisik pada disks dari pada penggunaan
pita-magnetik karena disks memiliki akses yang lebih cepat, tidak memerlukan penggulungan-balik
(rewinding), dan memungkinkan rekaman dapat di akses secara langsung.
“Run”
awal pada masing-masing berkas input P digabung dengan menggunakan pengurutan
gabungan. Output gabungan membentuk “run”
yang besarnya dalah P kali ukuran “run” yang asli; “run” yang dihasilkan
tersebut secara merata berada pada set kedua berkas output P. Ketika semiua
“run” pada berkas P asli telah di proses, maka satu “pass” sudah selesai. Pada
“pass” berikutnya, berkas output dari “pass” yang dihasilkan sebelumnya menjadi
berkas input yang sebelumnya menjkadi berkas output. “Pass” berikutnya
menggabungkan berkas yang dihasilkan dari “pass” pertama membentuk berkas yang
memiliki ukuran sebesar P-kali ukuran sebelumnya.
Proses
penggabungan terus berjalan membentuk “run” yang lebih besar sampai diperoleh
sebuah “run” tunggal, yaitu berkas yang sudah di urutkan. Karena ada berkas
masukan Yang terpisah dari berkas output, maka diperlukan berkas sebanyak total
2P. Jika digunakan pita-magnetik, karena di perlukan berkas yang cukup besar,
maka dibutuhkan sebanyak 2P penggerak pita-magnetik. Keseimbangan dua arah
pengurutan gabungan membutuhkan empat berkas. Jika jumlah penggerak
pita-magnetis yang tersedia atau berkas adalah F, berjumlah gasal, maka jumlah
berkas masukan berada di antaranya.
Contoh: dengan asumsi bahwa digunakan berkas disk dengan P = 3, maka data standar dapat di proses, sebagai berikut :
27, 18, 29, 28, 13, 16, 18 and 53
Untuk ilustrasi,
dianggap bahwa ukuran “run” awal berjumlah satu, dalam praktik yang sebenarnya,
jelas akan terlibat sejumlah besar rekaman, sehingga jumlah “run” juga akan
sangat banyak. Rekaman contoh tersebut kemudian didistribusikan sebagaimana
diperlihatkan sebagai berikut :
Disk yang menerima
hasil penggabunggabungan rekaman dari “pass” pertama,menjadi disk-input untuk
“pass” kedua yang akan menghasilkan berkas urut final,sebagai berikut:
PEMBAHASAN
Jumlah “pass” yang diperlukan dalam pengurutan gabungan
P-way seimbang menunjukkan indikasi adanya unjuk-kerja yang baik karena semua
rekaman diproses setiap “pass” dan waktu input/output yang diperlukan untuk
mengakses rekaman pada penyimpanan tambahan mendominasi waktu untuk melakukan
operasi. Sementara itu pengurutan gabungan dua-arah yang seimbang membutuhkan
“pass” sebanyak :
Dengan r adalah jumlah awal “run”. Dengan kata
lain, untuk kisaran “run” sejumlah r,
membutuhkan “pass” sejumlah k, dengan
2k-1 < r ≤ 2k.
Perhatikan bahwa jumlah “pass” adalah sama dengan “pass” yang diperlukan untuk
pengurutan gabungan internal jika “run” dianggap sama dengan jumlah berkas
awal. Berapa banyak “pass” akan diperlukan jika rekaman standar yang diurutkan
dengan algoritma pengurutan gabungan dua-arah yang seimbang dengan “run” awal
masing-masing terdiri atas dua rekaman ? karena r akan menjadi lima dalam kasus tersebut, maka tiga “pass” akan
diperlukan.
