Merge Sort

 

Judul:

Merge Sort

Bahasa:

C

Penulis:

Philip J. Erdelsky

Tanggal:

31 Juli 1998

Pemakaian:

Area publik; tidak ada pembatasan pada penggunaan

portabilitas:

Apa C compiler

Kata kunci:

Menyortir

Abstrak:

Fungsi AC untuk menyortir file, menggunakan membaca sewenang-wenang, menulis dan fungsi perbandingan dan algoritma tape-merge, yang merupakan O (n log n) dalam semua kasus. Fungsinya adalah non-rekursif dan ulang peserta.

Fungsi merge_sort () akan semacam hampir semua jenis file, menggunakan membaca, menulis dan fungsi perbandingan yang disediakan oleh program menelepon.

  1. Itu macam catatan ukuran variabel.
  2. Hal ini membutuhkan O (n log n) perbandingan, di mana n adalah jumlah record, terlepas dari pesanan awal. Waktu untuk menyortir file diprediksi dan konsisten. Kinerja ini dikenal optimal untuk jenis umum.
  3. Jumlah kali record harus dibaca dari, atau ditulis ke, file disk juga O (n log n).
  4. Algoritma ini berulang, tidak rekursif, sehingga tidak ada masalah stack overflow. Persyaratan stack diprediksi, konsisten dan kecil.
  5. Hal ini membutuhkan ruang disk yang cukup sekitar untuk menahan dua salinan dari file. File diurutkan yang tersisa di ruang ini.
  6. Hal ini membutuhkan setidaknya cukup memori untuk menyimpan tiga rekor, tetapi akan berjalan lebih cepat jika diberikan dengan lebih banyak memori.
  7. Ini panggilan tmpfile () untuk membuat sebanyak empat file-file sementara pada suatu waktu.
  8. File disortir dibaca berurutan, dan file diurutkan ditulis berurutan. Oleh karena itu mereka mungkin kaset, I / O stream atau perangkat ketat berurutan lainnya.

Fungsi panggilan adalah sebagai berikut:

     Hasil = merge_sort (unsorted_file, sorted_file, membaca, menulis, bandingkan,
       pointer, max_record_size, block_size, pcount);

Program menelepon harus menyediakan parameter berikut:

FILE * unsorted_file;

Sebuah pointer file untuk file yang akan diurutkan. file harus telah berhasil dibuka untuk membaca, dan pointer file harus diposisikan pada awal file.

FILE * sorted_file;

Sebuah pointer file untuk file diurutkan. file harus telah berhasil dibuka untuk menulis, dan pointer file harus diposisikan pada awal file.

int (* baca) ();

Sebuah fungsi yang membaca satu catatan.

int (* write) ();

Sebuah fungsi yang menulis satu catatan.

int (* bandingkan) ();

Sebuah fungsi yang membandingkan dua catatan.

void * pointer;

Sebuah pointer ditetapkan pengguna untuk diteruskan ke (* baca) (), (* write) () dan (* bandingkan) () berfungsi saat mereka dipanggil.

max_record_size unsigned;

Jumlah maksimum byte dalam catatan, ketika dibaca ke dalam memori. Ini tidak perlu sama dengan ukuran catatan ketika berada dalam sebuah file.

unsigned block_size panjang;

Jumlah record yang akan diurutkan dalam memori, atau 1L jika pemilahan memori tidak akan digunakan.

unsigned long * pcount;

Sebuah pointer ke variabel untuk menerima jumlah record (jika semacam ini berhasil), atau NULL jika informasi ini tidak dikembalikan.

Fungsi mengembalikan nilai berikut:

int hasil;

kode hasil:

  • 0 untuk semacam sukses
  • 1 untuk memori tidak cukup
  • 2 untuk kesalahan pembuatan file
  • 3 untuk kesalahan menulis file

File-file disortir dan diurutkan tidak akan memutar ulang atau tertutup. Setiap file akan dibiarkan terbuka, dengan pointer file diposisikan pada akhir file. Namun, jika dua berkas pointer identik, file tersebut akan memutar ulang dan catatan diurutkan akan ditulis di atasnya.

The (* read) () fungsi disebut oleh merge_sort () sebagai berikut, dan harus membaca satu record setiap kali disebut (kecuali saat akhir file unsorted terdeteksi):

     n = (* baca) (fp, penyangga, pointer);

FILE * fp;

Sebuah pointer file untuk file disortir atau file sementara yang dibuat dengan memanggil tmpfile ().

void * penyangga;

Sebuah pointer ke buffer untuk menerima satu record. buffer ini dapat menahan byte paling max_record_size.

void * pointer;

Salinan pointer melewati sebagai argumen untuk merge_sort ().

int n;

Jumlah byte dalam catatan, atau nol jika upaya yang dilakukan untuk membaca melewati akhir dari file yang tidak dipisahkan.

Ketika fungsi ini kembali nol, tidak akan dipanggil lagi untuk file yang sama. Tidak ada upaya akan dilakukan untuk membaca melewati akhir file sementara.

Sebuah catatan yang lebih besar dari ukuran maksimum yang ditentukan harus dipotong atau ditangani dalam beberapa cara lain yang cocok. fungsi akan gagal serempak jika buffer diperbolehkan meluap, atau jika nilai yang dikembalikan oleh (* baca) () lebih besar dari ukuran record maksimum.

Format record dapat diubah ketika dibaca ke dalam memori, asalkan:

  1. Perubahan yang kompatibel dengan (* write) () dan (* bandingkan) () fungsi, dan
  2. Nilai yang dikembalikan oleh () function (* baca) harus jumlah byte dalam catatan ketika sedang dalam buffer memori.

Misalnya, garis terminator \ r \ n di DOS / Windows mungkin akan dikonversi ke \ n ketika dibaca ke dalam memori.

The (* write) () fungsi disebut sebagai berikut, dan harus menulis satu catatan setiap kali hal itu disebut:

     n = (* write) (fp, penyangga, pointer);

FILE * fp;

Sebuah pointer file untuk file diurutkan atau file sementara yang dibuat dengan memanggil tmpfile ().

void * penyangga;

Sebuah pointer ke buffer memegang satu catatan, sebagai dibaca ke dalam memori oleh (* baca) ().

void * pointer;

Salinan pointer melewati sebagai argumen untuk merge_sort ().

int n;

Nol untuk menulis sukses; nol untuk ruang disk yang tidak mencukupi.

Perhatikan bahwa panjang record tidak lulus sebagai parameter. Ini harus terkandung, secara eksplisit maupun implisit, dalam catatan sendiri atau dalam beberapa () fungsi tempat lainnya dapat diakses oleh (* write).

The (* bandingkan) () fungsi dipanggil untuk membandingkan dua catatan, sebagai berikut:

     n = (* bandingkan) (p, q, pointer);

void * p;

Sebuah pointer ke buffer yang berisi rekaman pertama, sebagai dibaca ke dalam memori dengan (* baca) ().

void * q;

Sebuah pointer ke buffer yang berisi catatan kedua, sebagai dibaca ke dalam memori dengan (* baca) ().

void * pointer;

Salinan pointer melewati sebagai argumen untuk merge_sort ().

int n;

Hasil perbandingan, sebagai berikut:

  • > 0 jika * p adalah menjadi setelah * q untuk disortir
  • <0 jika * p adalah menjadi sebelum * q untuk disortir
  • 0 jika urutan * p dan * q tidak relevan

 

Mengurutkan hasil sebagai berikut:

  1. Catatan dibaca dari file disortir dan ditulis untuk dua berkas sementara di blok. Setiap blok berisi jumlah record yang ditentukan oleh argumen block_size (kecuali blok terakhir, yang mungkin berisi catatan yang lebih sedikit), dan diurutkan dalam memori dengan memanggil linked_list_sort () sebelum ditulis ke file sementara.
  2. File-file sementara kemudian diurutkan dengan menggabungkan blok di sejumlah berlalu. Dalam setiap lulus, blok dari dua file sumber digabung menjadi blok-blok yang mengandung dua kali lebih banyak catatan, dan ditulis untuk dua file output. Proses ini berakhir ketika ukuran blok sama atau melebihi ukuran file dan semua catatan yang dalam satu file, yang adalah file diurutkan.

Jenis dapat gagal jika

  1. Panggilan pada malloc () mengembalikan NULL karena tidak ada cukup memori, atau
  2. Panggilan pada tmpfile () mengembalikan NULL karena ada terlalu banyak file yang terbuka, atau
  3. Panggilan pada (* write) () kembali nol karena ada ruang disk tidak mencukupi.

Apakah semacam ini berhasil atau tidak, semua blok memori yang dialokasikan akan deallocated, dan semua file-file sementara akan ditutup dan dihapus. Jika seperti itu gagal, pointer file untuk file disortir dan diurutkan akan ditinggalkan di mana pun mereka kebetulan.

The merge_sort () fungsi reentrant jika fungsi yang mereka sebut adalah reentrant:

  • (*membandingkan)()
  • fclose ()
  • bebas()
  • malloc ()
  • memcpy ()
  • (*Baca baca)()
  • mundur ()
  • tmpfile ()
  • (*menulis)()

Di bawah DOS / Windows, tmpfile () menciptakan sebuah file Binary. Namun, hal ini biasanya tidak menciptakan masalah, bahkan jika file disortir dan diurutkan adalah file teks, karena DOS / Windows menangani konversi secara konsisten.

Jika ruang disk sangat ketat, semacam itu dapat dimodifikasi untuk menggunakan ruang yang ditempati oleh file yang tidak dipisahkan. File disortir, file-file sementara, dan file yang diurutkan kemudian dapat masuk ke dalam ruang sekitar dua kali lebih besar file disortir. Untuk membuat modifikasi ini, hanya memasukkan kode untuk menghapus file disortir setelah telah dibaca. Perhatikan bahwa jika teknik ini digunakan, file diurutkan dan disortir harus berbeda, dan argumen struktur lewat dapat menjadi sedikit kurang elegan karena fungsi panggilan untuk menghapus file biasanya membutuhkan spesifikasi file bukan hanya pointer file.

The merge_sort () fungsi tidak stabil; yaitu, itu tidak menjaga posisi relatif dari dua catatan untuk yang (* bandingkan) () mengembalikan fungsi nol. Fungsi stable_merge_sort () memang memiliki properti ini. Namun, fitur tambahan membawa harga: catatan jumlah empat byte ditambahkan ke setiap record ketika sedang dalam memori atau file sementara. Hal ini meningkatkan disk dan memori persyaratan, dengan jumlah yang besar jika catatan kecil.

Utilitas SORT menggambarkan penggunaan stable_merge_sort (). Ini adalah DOS atau UNIX filter yang macam baris file teks. Panjang garis maksimum adalah karakter MAX_LINE, tidak termasuk carriage return dan line feed pada akhir setiap baris. Utilitas yang akan membatalkan semacam itu dan menampilkan pesan kesalahan jika membaca baris yang mengandung lebih dari MAX_LINE karakter. Nilai MAX_LINE ditetapkan pada 255, tetapi dapat diubah dengan mengkompilasi ulang utilitas.

Utilitas disebut sebagai berikut:

    SORT <unsorted_file> sorted_file MN

Semacam ini termasuk jumlah kolom M ke N, inklusif, di mana kolom paling kiri adalah nomor nol. Jika N diabaikan, semacam termasuk kolom M dan semua kolom di sebelah kanan itu. Jika kedua M dan N dihilangkan, semua kolom yang digunakan dalam semacam itu.

Sebuah garis yang mengandung kurang dari N + 1 kolom diurutkan seolah-olah itu empuk dengan nulls di ujung kanan.

Karakter berdasarkan peringkat kode ASCII mereka, dianggap sebagai byte unsigned.

Paket ini menyerukan paket lain:

Source code dalam format teks: