SORT AND MARGE

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

2.      Sort / Pengurutan

• Waktu yang paling banyak dihabiskan dalam pengelolaan file adalah waktu untuk menata ulang record dan waktu aktivitas pencarian.
•  Alasan diperlukan pengurutan data :

1. Penyajian data :Hasil laporan dari analisis data dari file dapat disajikan kepada user dengan cepat dan akurat.
2. Penggabungan file :Adanya 2 atau lebih file dengan susunan record yang berbeda harus digabungkan untuk keperluan analisis data.
3. Pembuatan index : Index diperlukan untuk proses pencarian data

3.      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 :

1. Sort Phase 
2. Merge Phase

4.      PengurutanEksternal

v  Faktor-faktor yang mempengaruhi metode sort eksternal 

v  Teknik sort/merge file ini berbeda satu dengan yang lainnya dalam hal 

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

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

7.      External Merge Sort

• Jika memori utama memiliki halaman buffer sebanyak B ruang buffer, maka untuk mengurutkan file yang besar yang memiliki N halaman