Pengertian Berkas Sort Dan Merge

Pengertian Berkas Sort Dan Merge

Dalam sistem penyortiran dikenal 2 metode, yaitu :

_ Metode Sort Internal

_ Metode Sort Eksternal

Perbedaannya :

_ Pada metode sort internal, semua record yang akan diproses dimuat ke dalam memori

komputer lalu diproses sort (sortir).

_ Pada metode sort eksternal, record-record yang diproses tidak semuanya dapat dimuat

ke dalam memori komputer, karena keterbatasan memori komputer.

_ Metode sort eksternal di dalam penerapannya nanti, menggunakan pula metode sort

internal.

Contoh :

Sebuah file berisi 2000 record harus disortir ke dalam memori yang hanya dapat

menampung 1000 record sekaligus. Untuk itu digunakan metode sort eksternal.

Langkah-langkah penyortiran ini adalah :

_ Record-record dibagi ke dalam beberapa file agar dapat ditampung sekaligus di

memori komputer, lalu masing-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)

_ Setelah itu kedua sorted sublist ini (RUN) digabung (merge), sehingga didapat

berkas gabungan (merge file) yang record-recordnya telah disortir.

2

Maka dapat disimpulkan langkah-langkah untuk metode sort eksternal ini adalah :

o Sort internal, dimana file dibagi menjadi beberapa bagian file, kemudian disortir.

o 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 disortir.

o Output, yang menyalin file gabungan yang telah tersortir ke media storage terakhir.

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

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)

Ada 4 teknik dalam sort/merge file, yaitu :

• Natural Merge

• Balanced Merge

• Polyphase Merge

• Cascade Merge

MERGE

Sorted sublist 1

(records 1 – 1000)

Sorted sublist 2

(records 1001 – 2000)

Merge List

(Sorted list of

records 1 – 2000)

3

Natur Natural Merge

al 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.

Pada natural merge terbagi lagi menjadi :

2 way natural merge

3 way natural merge

:

:

M way natural merge

Pada M way natural merge, dapat didefinisikan sebagai merge dengan :

M input file dan hanya 1 output file.