sistem berkas 2iahelen.staff.gunadarma.ac.id/downloads/files/48406/03...polyphase merge • pada m...

SISTEM BERKAS2IA

SORT & MERGE BERKAS

helen.staff.gunadarma.ac.idhelentugas@outlook.com

Overview

• Metode Sort Berkas

• Sort Eksternal

• Natural Merge Sort

• Balanced Merge Sort

• Polyphase Merge Sort

helen.staff.gunadarma.ac.idhelentugas@outlook.com

Metode Sort Berkas

• Internal : semua record yang akan diproses dimuatke dalam memori komputer lalu diproses sort(sortir).

• Eksternal : record-record yang diproses tidaksemuanya dapat dimuat ke dalam memorikomputer, karena keterbatasan memori komputer.

• Metode sort eksternal di dalam penerapannyananti, menggunakan pula metode sort internal.

helen.staff.gunadarma.ac.idhelentugas@outlook.com

Contoh

• Sebuah file berisi 2000 record harus di sortirke dalam memori yang hanya dapatmenampung 1000 record sekaligus.

• Untuk itu digunakan metode sort eksternal.

helen.staff.gunadarma.ac.idhelentugas@outlook.com

Metode Sort Eksternal

• Sort eksternal, dimana file dibagi menjadi beberapa bagian file,kemudian di sortir. Bagian-bagian ini dinamakan sorted sublist.

• Merge, dimana sorted sublist digabung menjadi satu atau lebih filegabungan. File-file gabungan kemudian digabung lagi sampaiakhirnya didapatkan sebuah file gabungan yang berisi semuarecord-record yang telah di sortir.

• Output, yang menyalin file gabungan yang telah tersortir ke mediastorage terakhir.

Natural Merge Sort

• Merge yang menangani M input file sekaligus disebut Mway natural merge. M menunjukkan derajat merge.

• Pada M way natural merge, dapat didefinisikan sebagaimerge dengan:

M input file -> 1 output file

helen.staff.gunadarma.ac.idhelentugas@outlook.com

Contoh Soal

• Sebuah file yang terdiri dari 6000 recordhendak di sortir kedalam memori komputeryang kapasitasnya 500 record.

• Buatlah dengan menggunakan 2 way naturalmerge!

helen.staff.gunadarma.ac.idhelentugas@outlook.com

2-Way Natural Merge

3-Way Natural Merge

Balanced Merge

• Dari metode natural merge kita lihat bahwa, jikakita gunakan M input file, maka file seluruhnya yangkita gunakan adalah M + 1 file.

• Sedangkan pada balanced merge, jika kita gunakanM input file, maka file seluruhnya yang dipakaiadalah 2 M file.

M input file -> M output file

helen.staff.gunadarma.ac.idhelentugas@outlook.com

2-Way Balanced Merge

Polyphase Merge

• Pada M way polyphase merge digunakan 2M-1input file dengan 1 output file.

• Jadi jika kita menggunakan 2 way polyphase Merge,maka banyaknya input file yang digunakan ada 3input file.

2M-1 input file -> 1 output file

helen.staff.gunadarma.ac.idhelentugas@outlook.com

2-Way Polyphase Merge