Merge sort ialah salah satu daripada algoritma sains komputer asas, yang dirumus pada tahun 1945 oleh ahli matematik yang hebat John von Neumann. Semasa mengambil bahagian dalam Projek Manhattan, Neumann berhadapan dengan keperluan untuk memproses sejumlah besar data dengan cekap. Kaedah yang dibangunkannya menggunakan prinsip "bahagi dan takluk", yang mengurangkan masa yang diperlukan untuk bekerja dengan ketara.
Prinsip dan penggunaan algoritma
Kaedah isihan gabungan digunakan dalam masalah menyusun struktur yang telah memesan akses kepada elemen, seperti tatasusunan, senarai, strim.
Semasa pemprosesan, blok data awal dibahagikan kepada komponen kecil, sehingga satu elemen, yang sebenarnya sudah menjadi senarai diisih. Kemudian ia dipasang semula dalam susunan yang betul.
Mengisih tatasusunan dengan panjang tertentu memerlukan kawasan memori tambahan dengan saiz yang sama, di mana tatasusunan yang diisih dikumpulkan dalam bahagian.
Kaedah ini boleh digunakan untuk memesan sebarang jenis data yang setanding, seperti nombor atau rentetan.
Gabung diisihplot
Untuk memahami algoritma, mari kita mulakan analisisnya dari akhir - daripada mekanisme menggabungkan blok yang diisih.
Mari bayangkan bahawa kita mempunyai dua tatasusunan nombor yang diisih dalam apa jua cara yang perlu digabungkan antara satu sama lain supaya pengisihan tidak rosak. Untuk memudahkan, kami akan mengisih nombor dalam tertib menaik.
Contoh asas: kedua-dua tatasusunan terdiri daripada satu elemen setiap satu.
int arr1={31}; int arr2={18};
Untuk menggabungkannya, anda perlu mengambil elemen sifar tatasusunan pertama (jangan lupa bahawa penomboran bermula dari sifar) dan unsur sifar tatasusunan kedua. Ini adalah, masing-masing, 31 dan 18. Mengikut syarat pengisihan, nombor 18 harus didahulukan, kerana ia kurang. Hanya letakkan nombor dalam susunan yang betul:
int hasil={18, 31};
Mari kita lihat contoh yang lebih rumit, di mana setiap tatasusunan terdiri daripada beberapa elemen:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Algoritma gabungan akan terdiri daripada membandingkan secara berurutan elemen yang lebih kecil dan meletakkannya dalam tatasusunan yang terhasil dalam susunan yang betul. Untuk menjejaki indeks semasa, mari kita perkenalkan dua pembolehubah - indeks1 dan indeks2. Pada mulanya, kami menetapkannya kepada sifar, memandangkan tatasusunan diisih dan unsur terkecil berada pada permulaan.
int index1=0; int index2=0;
Mari kita tulis keseluruhan proses penggabungan langkah demi langkah:
- Ambil elemen dengan indeks1 daripada tatasusunan arr1, dan elemen dengan indeks2 daripada tatasusunan arr2.
- Bandingkan, pilih yang terkecil dan masukkantatasusunan yang terhasil.
- Naikkan indeks semasa bagi elemen yang lebih kecil sebanyak 1.
- Teruskan dari langkah pertama.
Pada orbit pertama, keadaan akan kelihatan seperti ini:
indeks1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indeks1++; hasil[0]=arr1[0]; // hasil=[2]
Pada giliran kedua:
indeks1=1; indeks2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indeks2++; hasil[1]=arr2[0]; // hasil=[2, 5]
Ketiga:
indeks1=1; indeks2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indeks2++; hasil[2]=arr2[1]; // keputusan=[2, 5, 6]
Dan seterusnya, sehingga hasilnya ialah tatasusunan yang diisih sepenuhnya: {2, 5, 6, 17, 21, 19, 30, 45}.
Kesukaran tertentu boleh timbul jika tatasusunan dengan panjang yang berbeza digabungkan. Bagaimana jika salah satu daripada indeks semasa telah mencapai elemen terakhir, dan masih ada ahli yang tinggal dalam tatasusunan kedua?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 langkah indeks1=0, indeks2=0; 1 2 hasil={1, 2}; // 3 langkah indeks1=1, indeks2=1; 4 < 5 hasil={1, 2, 4}; //4 langkah indeks1=2, indeks2=1 ??
Pembolehubah indeks1 telah mencapai nilai 2, tetapi tatasusunan arr1 tidak mempunyai elemen dengan indeks tersebut. Segala-galanya mudah di sini: hanya pindahkan baki elemen tatasusunan kedua kepada yang terhasil, mengekalkan susunannya.
hasil={1, 2, 4, 5, 6, 7, 9};
Situasi ini menunjukkan kepada kita keperluanpadankan indeks semakan semasa dengan panjang tatasusunan yang digabungkan.
Gabung skema untuk urutan tertib (A dan B) dengan panjang yang berbeza:
- Jika panjang kedua-dua jujukan lebih besar daripada 0, bandingkan A[0] dan B[0] dan gerakkan yang lebih kecil ke penimbal.
- Jika panjang salah satu jujukan ialah 0, ambil baki elemen jujukan kedua dan, tanpa mengubah susunannya, pindah ke penghujung penimbal.
Pelaksanaan peringkat kedua
Contoh menyertai dua tatasusunan yang diisih dalam Java diberikan di bawah.
int a1=int baharu {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=int baharu {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=int baharu[a1.length + a2.length]; int i=0, j=0; untuk (int k=0; k a1.panjang-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } lain jika (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
Di sini:
- a1 dan a2 ialah tatasusunan isih asal untuk digabungkan;
- a3 – tatasusunan akhir;
- i dan j ialah indeks unsur semasa untuk tatasusunan a1 dan a2.
Kondisi pertama dan kedua jika memastikan indeks tidak melebihi saiz tatasusunan. Blok keadaan ketiga dan keempat, masing-masing, dialihkan ke tatasusunan terhasil bagi elemen yang lebih kecil.
Bahagi dan Takluki
Jadi, kami telah belajar untuk menggabungkan yang diisihkoleksi nilai. Boleh dikatakan bahawa bahagian kedua algoritma isihan cantuman - cantuman itu sendiri - telah diisih.
Walau bagaimanapun, anda masih perlu memahami cara untuk beralih daripada tatasusunan nombor asal yang tidak diisih kepada beberapa nombor yang diisih yang boleh digabungkan.
Mari kita pertimbangkan peringkat pertama algoritma dan pelajari cara mengasingkan tatasusunan.
Ini tidak sukar - senarai nilai asal dibahagikan kepada separuh, kemudian setiap bahagian juga dicabangkan, dan seterusnya sehingga blok yang sangat kecil diperolehi.
Panjang elemen minimum sedemikian boleh sama dengan satu, iaitu, ia sendiri boleh menjadi tatasusunan yang diisih, tetapi ini bukan syarat yang diperlukan. Saiz blok ditentukan terlebih dahulu dan sebarang algoritma pengisihan yang sesuai yang berfungsi dengan cekap dengan tatasusunan saiz kecil (contohnya, isihan pantas atau isihan sisipan) boleh digunakan untuk memesannya.
Ia kelihatan seperti ini.
// tatasusunan asal {34, 95, 10, 2, 102, 70}; // pecahan pertama {34, 95, 10} dan {2, 102, 70}; // pemisahan kedua {34} dan {95, 10} dan {2} dan {102, 70}
Blok yang terhasil, terdiri daripada 1-2 elemen, sangat mudah diatur.
Selepas itu, anda perlu menggabungkan tatasusunan kecil yang telah diisih secara berpasangan, mengekalkan susunan ahli, yang telah kami pelajari untuk lakukan.
Pelaksanaan peringkat pertama
Pembahagian rekursif tatasusunan ditunjukkan di bawah.
void mergeSort(T a, permulaan panjang, penamat panjang) { belah panjang; jika(mula < penamat) { split=(mula + penamat)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); merge(a, mula, belah, selesai); } }
Apa yang berlaku dalam kod ini:
-
Fungsi mergeSort mendapat tatasusunan awal
a
dan sempadan kiri dan kanan wilayah untuk diisih (indeks bermula dan
- finish).
-
Jika panjang bahagian ini lebih besar daripada satu (
mula < selesai
), maka bahagian ini dibahagikan kepada dua bahagian (mengikut indeks
- split), dan setiap satu diisih secara rekursif.
-
Dalam panggilan fungsi rekursif untuk sebelah kiri, indeks permulaan plot dan indeks
split
diluluskan. Untuk yang betul, masing-masing, permulaan ialah
- (split + 1) dan penghujungnya ialah indeks terakhir bahagian asal.
-
Fungsi
cantum
mendapat dua urutan tersusun (
a[mula]…a[split]
dan
- a[split +1]…a[finish]) dan cantumkannya mengikut susunan.
Mekanik fungsi cantum dibincangkan di atas.
Skema umum algoritma
Kaedah tatasusunan isihan gabungan terdiri daripada dua langkah besar:
- Belah tatasusunan asal yang tidak diisih kepada kepingan kecil.
- Kumpulkannya secara berpasangan, mengikut peraturan pengisihan.
Tugas yang besar dan kompleks dipecahkan kepada banyak tugas yang mudah, yang diselesaikan secara berurutan, membawa kepada hasil yang diingini.
Penilaian kaedah
Kerumitan masa isihan cantum ditentukan oleh ketinggian pokok terbelahalgoritma dan adalah sama dengan bilangan elemen dalam tatasusunan (n) darab logaritmanya (log n). Anggaran sedemikian dipanggil logaritma.
Ini adalah kelebihan dan kelemahan kaedah. Masa berjalannya tidak berubah walaupun dalam kes yang paling teruk, apabila tatasusunan asal diisih dalam susunan terbalik. Walau bagaimanapun, apabila memproses data yang diisih sepenuhnya, algoritma tidak memberikan keuntungan masa.
Adalah juga penting untuk mengambil perhatian kos memori kaedah isihan gabungan. Mereka sama dengan saiz koleksi asal. Dalam kawasan yang diperuntukkan tambahan ini, tatasusunan yang diisih disusun daripada kepingan.
Pelaksanaan algoritma
Isihan cantum Pascal ditunjukkan di bawah.
Prosedur MergeSort(nama: rentetan; var f: teks); Var a1, a2, s, i, j, kol, tmp: integer; f1, f2: teks; b: boolean Begincol:=0; Tugaskan(f, nama); set semula(f); Walaupun bukan EOF(f) mula membaca(f, a1); inc(col); akhir; tutup(f); Assign(f1, '{name of 1st auxiliary file}'); Assign(f2, '{name of 2nd auxiliary file}'); s:=1; Manakala (s<kol) mulakan Reset(f); tulis semula(f1); tulis semula(f2); Untuk i:=1 hingga kol div 2 mulakan Baca(f, a1); Tulis(f1, a1, ' '); akhir; Jika (kol div 2) mod s0 maka mulakan tmp:=kol div 2; Semasa tmp mod s0 mulakan Baca(f, a1); Tulis(f1, a1, ' '); inc(tmp); akhir; akhir; Walaupun bukan EOF(f) mulakan Baca(f, a2); Tulis(f2, a2, ' '); akhir; tutup(f); tutup(f1); tutup(f2); tulis semula(f); set semula(f1); set semula (f2); Baca(f1, a1); Baca(f2, a2); Walaupun (bukan EOF(f1)) dan (bukan EOF(f2)) bermula i:=0; j:=0; b:=benar; Manakala (b) dan (bukan EOF(f1)) dan (bukan EOF(f2)) bermula Jika (a1<a2) kemudian mulakanTulis(f, a1, ' '); Baca(f1, a1); inc(i); Tamat lain mula Tulis(f, a2, ' '); Baca(f2, a2); inc(j); akhir; Jika (i=s) atau (j=s) maka b:=false; akhir; Jika bukan b maka mulakan While (i<s) dan (bukan EOF(f1)) mulakan Write(f, a1, ' '); Baca(f1, a1); inc(i); akhir; Manakala (j<s) dan (bukan EOF(f2)) mulakan Write(f, a2, ' '); Baca(f2, a2); inc(j); akhir; akhir; akhir; Walaupun bukan EOF(f1) mula tmp:=a1; Baca(f1, a1); Jika bukan EOF(f1) maka Tulis(f, tmp, ' ') else Tulis(f, tmp); akhir; Walaupun bukan EOF(f2) mula tmp:=a2; Baca(f2, a2); Jika bukan EOF(f2) maka Tulis(f, tmp, ' ') else Tulis(f, tmp); akhir; tutup(f); tutup(f1); tutup(f2); s:=s2; akhir; Padam(f1); Padam(f2); Tamat;
Secara visual, operasi algoritma kelihatan seperti ini (atas - urutan tidak tertib, bawah - tersusun).
Isih data luaran
Selalunya terdapat keperluan untuk mengisih beberapa data yang terdapat dalam memori luaran komputer. Dalam sesetengah kes, ia mempunyai saiz yang mengagumkan dan tidak boleh diletakkan dalam RAM untuk memudahkan akses kepada mereka. Untuk kes sedemikian, kaedah pengisihan luaran digunakan.
Keperluan untuk mengakses media luaran merendahkan kecekapan masa pemprosesan.
Kerumitan kerja ialah algoritma hanya boleh mengakses satu elemen aliran data pada satu masa. Dan dalam kes ini, salah satu hasil terbaik ditunjukkan oleh kaedah isihan gabungan, yang boleh membandingkan elemen dua fail secara berurutan satu demi satu.
Membaca data daripadasumber luaran, pemprosesan dan penulisannya ke fail akhir dijalankan dalam blok tertib (siri). Mengikut cara bekerja dengan saiz siri yang dipesan, terdapat dua jenis pengisihan: penggabungan mudah dan semula jadi.
Gabungan mudah
Dengan gabungan mudah, panjang siri ditetapkan.
Oleh itu, dalam fail asal yang tidak diisih, semua siri terdiri daripada satu elemen. Selepas langkah pertama, saiznya meningkat kepada dua. Seterusnya - 4, 8, 16 dan seterusnya.
Ia berfungsi seperti ini:
- Fail sumber (f) dibahagikan kepada dua fail tambahan - f1, f2.
- Ia sekali lagi digabungkan menjadi satu fail (f), tetapi pada masa yang sama semua elemen dibandingkan secara berpasangan dan membentuk pasangan. Saiz siri pada langkah ini menjadi dua.
- Langkah 1 diulang.
- Langkah 2 diulang, tetapi 2 yang telah dipesan digabungkan untuk membentuk 4s yang diisih.
- Gelung diteruskan, meningkatkan siri pada setiap lelaran, sehingga keseluruhan fail diisih.
Bagaimana anda tahu bahawa pengisihan luar dengan cantuman mudah telah selesai?
- panjang siri baharu (selepas digabungkan) tidak kurang daripada jumlah elemen;
- hanya tinggal satu episod;
- Fail tambahan f2 dibiarkan kosong.
Kelemahan cantuman ringkas ialah: memandangkan panjang larian ditetapkan pada setiap pas cantuman, data yang tertib separa akan mengambil masa yang lama untuk diproses sebagai data rawak sepenuhnya.
Paduan semula jadi
Kaedah ini tidak mengehadkan panjangsiri, tetapi memilih maksimum yang mungkin.
Algoritma pengisihan:
- Membaca urutan awal daripada fail f. Elemen pertama yang diterima ditulis pada fail f1.
- Jika entri seterusnya memenuhi syarat pengisihan, ia ditulis di sana, jika tidak, kemudian ke fail tambahan kedua f2.
- Dengan cara ini, semua rekod fail sumber diedarkan dan urutan tertib dibentuk dalam f1, yang menentukan saiz semasa siri.
- Fail f1 dan f2 digabungkan.
- Kitaran berulang.
Disebabkan saiz siri yang tidak tetap, adalah perlu untuk menandakan penghujung jujukan dengan aksara khas. Oleh itu, apabila bergabung, bilangan perbandingan meningkat. Selain itu, saiz salah satu fail tambahan mungkin hampir dengan saiz asal.
Secara purata, cantuman semula jadi adalah lebih cekap daripada cantuman mudah dengan isihan luaran.
Ciri algoritma
Apabila membandingkan dua nilai yang sama, kaedah itu mengekalkan susunan asalnya, iaitu, ia adalah stabil.
Proses pengisihan boleh dibahagikan kepada berbilang urutan dengan sangat berjaya.
Video dengan jelas menunjukkan pengendalian algoritma isihan gabungan.
