Merge sort adalah salah satu algoritma dasar ilmu komputer, yang diformulasikan pada tahun 1945 oleh ahli matematika hebat John von Neumann. Saat berpartisipasi dalam Proyek Manhattan, Neumann dihadapkan pada kebutuhan untuk memproses data dalam jumlah besar secara efisien. Metode yang ia kembangkan menggunakan prinsip "membagi dan menaklukkan", yang secara signifikan mengurangi waktu yang dibutuhkan untuk bekerja.
Prinsip dan penggunaan algoritma
Metode pengurutan gabungan digunakan dalam masalah pengurutan struktur yang telah memerintahkan akses ke elemen, seperti larik, daftar, aliran.
Selama pemrosesan, blok data awal dipecah menjadi komponen-komponen kecil, hingga satu elemen, yang sebenarnya sudah merupakan daftar yang diurutkan. Kemudian dipasang kembali dalam urutan yang benar.
Mengurutkan larik dengan panjang tertentu memerlukan area memori tambahan dengan ukuran yang sama, di mana larik yang diurutkan dikumpulkan dalam beberapa bagian.
Metode ini dapat digunakan untuk mengurutkan semua tipe data yang sebanding, seperti angka atau string.
Gabung diurutkanplot
Untuk memahami algoritme, mari kita mulai analisisnya dari akhir - dari mekanisme penggabungan blok yang diurutkan.
Mari kita bayangkan bahwa kita memiliki dua larik angka yang diurutkan dengan cara apa pun yang perlu digabungkan satu sama lain agar pengurutannya tidak terputus. Untuk mempermudah, kami akan mengurutkan angka dalam urutan menaik.
Contoh dasar: kedua array masing-masing terdiri dari satu elemen.
int arr1={31}; int arr2={18};
Untuk menggabungkannya, Anda perlu mengambil elemen nol dari larik pertama (jangan lupa bahwa penomoran dimulai dari nol) dan elemen nol dari larik kedua. Ini adalah, masing-masing, 31 dan 18. Menurut kondisi penyortiran, angka 18 harus didahulukan, karena lebih sedikit. Letakkan saja angka-angka dalam urutan yang benar:
int hasil={18, 31};
Mari kita lihat contoh yang lebih rumit, di mana setiap array terdiri dari beberapa elemen:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Algoritme penggabungan akan terdiri dari membandingkan elemen yang lebih kecil secara berurutan dan menempatkannya dalam larik yang dihasilkan dalam urutan yang benar. Untuk melacak indeks saat ini, mari kita perkenalkan dua variabel - index1 dan index2. Awalnya, kami menyetelnya ke nol, karena array diurutkan, dan elemen terkecil ada di awal.
int indeks1=0; int indeks2=0;
Mari kita tulis seluruh proses penggabungan langkah demi langkah:
- Ambil elemen dengan index1 dari array arr1, dan elemen dengan index2 dari array arr2.
- Bandingkan, pilih yang terkecil dan masukkanarray yang dihasilkan.
- Tingkatkan indeks elemen yang lebih kecil saat ini sebanyak 1.
- Lanjutkan dari langkah pertama.
Pada orbit pertama, situasinya akan terlihat seperti ini:
indeks1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indeks1++; hasil[0]=arr1[0]; // hasil=[2]
Di belokan 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]; // hasil=[2, 5, 6]
Dan seterusnya, hingga hasilnya adalah array yang benar-benar terurut: {2, 5, 6, 17, 21, 19, 30, 45}.
Kesulitan tertentu dapat muncul jika array dengan panjang yang berbeda digabungkan. Bagaimana jika salah satu indeks saat ini telah mencapai elemen terakhir, dan masih ada anggota yang tersisa di larik 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 ??
Variabel index1 telah mencapai nilai 2, tetapi array arr1 tidak memiliki elemen dengan indeks tersebut. Semuanya sederhana di sini: cukup transfer elemen yang tersisa dari larik kedua ke yang dihasilkan, pertahankan urutannya.
hasil={1, 2, 4, 5, 6, 7, 9};
Situasi ini menunjukkan kepada kita kebutuhancocokkan indeks pemeriksaan saat ini dengan panjang larik yang digabungkan.
Menggabungkan skema untuk urutan berurutan (A dan B) dengan panjang yang berbeda:
- Jika panjang kedua barisan lebih besar dari 0, bandingkan A[0] dan B[0] dan pindahkan yang lebih kecil ke buffer.
- Jika panjang salah satu barisan adalah 0, ambil elemen yang tersisa dari barisan kedua dan, tanpa mengubah urutannya, pindah ke akhir buffer.
Pelaksanaan tahap kedua
Contoh menggabungkan dua array yang diurutkan di Java diberikan di bawah ini.
int a1=new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=baru int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; saya++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; saya++; } else { int b=a2[j]; a3[k]=b; j++; } }
Di sini:
- a1 dan a2 adalah array terurut asli yang akan digabungkan;
- a3 – larik terakhir;
- i dan j adalah indeks elemen saat ini untuk array a1 dan a2.
Kondisi if pertama dan kedua memastikan bahwa indeks tidak melebihi ukuran array. Blok kondisi ketiga dan keempat, masing-masing, dipindahkan ke larik yang dihasilkan dari elemen yang lebih kecil.
Membagi dan Menaklukkan
Jadi, kami telah belajar menggabungkan yang diurutkankumpulan nilai. Dapat dikatakan bahwa bagian kedua dari algoritma merge sort - penggabungan itu sendiri - telah diurutkan.
Namun, Anda masih perlu memahami cara berpindah dari larik bilangan asli yang tidak diurutkan ke beberapa nomor yang diurutkan yang dapat digabungkan.
Mari kita pertimbangkan tahap pertama dari algoritme dan pelajari cara memisahkan array.
Ini tidak sulit - daftar nilai asli dibagi menjadi dua, kemudian setiap bagian juga bercabang, dan seterusnya hingga diperoleh blok yang sangat kecil.
Panjang elemen minimal tersebut dapat sama dengan satu, yaitu, elemen tersebut sendiri dapat berupa array yang diurutkan, tetapi ini bukan kondisi yang diperlukan. Ukuran blok ditentukan terlebih dahulu, dan algoritme pengurutan apa pun yang sesuai yang bekerja secara efisien dengan larik berukuran kecil (misalnya, quicksort atau insertion sort) dapat digunakan untuk mengurutkannya.
Terlihat seperti ini.
// larik asli {34, 95, 10, 2, 102, 70}; // pembagian pertama {34, 95, 10} dan {2, 102, 70}; // pembagian kedua {34} dan {95, 10} dan {2} dan {102, 70}
Blok yang dihasilkan terdiri dari 1-2 elemen, sangat mudah disusun.
Setelah itu, Anda perlu menggabungkan array kecil yang sudah diurutkan secara berpasangan, menjaga urutan anggota, yang telah kita pelajari.
Pelaksanaan tahap pertama
Partisi rekursif dari sebuah array ditunjukkan di bawah ini.
void mergeSort(T a, awal panjang, akhir panjang) { split panjang; jika(mulai < selesai) { split=(mulai + selesai)/2; mergeSort(a, mulai, pisah); mergeSort(a, split+1, selesai); menggabungkan (a, mulai, membagi, selesai); } }
Apa yang terjadi dalam kode ini:
-
Fungsi mergeSort mendapatkan larik awal
a
dan batas kiri dan kanan wilayah yang akan diurutkan (indeks mulai dan
- selesai).
-
Jika panjang bagian ini lebih besar dari satu (
mulai < selesai
), maka dibagi menjadi dua bagian (dengan indeks
- split), dan masing-masing diurutkan secara rekursif.
-
Dalam panggilan fungsi rekursif untuk sisi kiri, indeks awal plot dan indeks
split
dilewatkan. Untuk yang kanan, masing-masing, awalnya adalah
- (split + 1), dan akhirnya akan menjadi indeks terakhir dari bagian asli.
-
Function
merge
mendapat dua urutan berurutan (
a[start]…a[split]
dan
- a[split +1]…a[finish]) dan menggabungkannya dalam urutan.
Mekanisme fungsi gabungan dibahas di atas.
Skema umum algoritma
Metode array sortir gabungan terdiri dari dua langkah besar:
- Pisahkan array asli yang tidak disortir menjadi potongan-potongan kecil.
- Kumpulkan secara berpasangan, ikuti aturan penyortiran.
Tugas besar dan kompleks dipecah menjadi banyak tugas sederhana, yang diselesaikan secara berurutan, yang mengarah ke hasil yang diinginkan.
Evaluasi metode
Kompleksitas waktu pengurutan gabungan ditentukan oleh ketinggian pohon terbelahalgoritma dan sama dengan jumlah elemen dalam array (n) dikalikan logaritmanya (log n). Estimasi seperti ini disebut logaritma.
Ini adalah keuntungan dan kerugian dari metode ini. Waktu berjalannya tidak berubah bahkan dalam kasus terburuk, ketika array asli diurutkan dalam urutan terbalik. Namun, saat memproses data yang diurutkan secara lengkap, algoritme tidak memberikan penambahan waktu.
Penting juga untuk mencatat biaya memori dari metode merge sort. Mereka sama dengan ukuran koleksi aslinya. Di area yang dialokasikan tambahan ini, array yang diurutkan dirakit dari potongan-potongan.
Implementasi algoritma
Pengurutan gabungan pascal ditunjukkan di bawah ini.
Procedure MergeSort(nama: string; var f: teks); Var a1, a2, s, i, j, kol, tmp: integer; f1, f2: teks; b: boolean Mulaikol:=0; Tetapkan (f, nama); ulang (p); Meskipun bukan EOF(f) mulailah membaca(f, a1); inc(kol); akhir; tutup (p); Assign(f1, '{nama file tambahan ke-1}'); Assign(f2, '{nama file tambahan ke-2}'); s:=1; Sementara (s<kol) lakukan mulai Reset(f); menulis ulang (f1); menulis ulang (f2); Untuk i:=1 hingga kol div 2 lakukan mulai Baca(f, a1); Tulis(f1, a1, ' '); akhir; Jika (kol div 2) mod s0 maka mulai tmp:=kol div 2; Sementara tmp mod s0 lakukan mulai Baca(f, a1); Tulis(f1, a1, ' '); inc(tmp); akhir; akhir; Meskipun bukan EOF(f) lakukan mulai Baca(f, a2); Tulis(f2, a2, ' '); akhir; tutup (p); tutup (f1); tutup(f2); menulis ulang (f); setel ulang (f1); ulang (f2); Baca(f1, a1); Baca(f2, a2); Sementara (bukan EOF(f1)) dan (bukan EOF(f2)) lakukan mulai i:=0; j:=0; b:=benar; Sementara (b) dan (bukan EOF(f1)) dan (bukan EOF(f2)) dimulai Jika (a1<a2) maka mulaiTulis(f, a1, ' '); Baca(f1, a1); termasuk(i); Akhiri lain mulai Tulis(f, a2, ' '); Baca(f2, a2); termasuk(j); akhir; Jika (i=s) atau (j=s) maka b:=false; akhir; Jika tidak b maka mulai While (i<s) dan (bukan EOF(f1)) lakukan mulai Write(f, a1, ' '); Baca(f1, a1); termasuk(i); akhir; While (j<s) dan (bukan EOF(f2)) lakukan mulai Write(f, a2, ' '); Baca(f2, a2); termasuk(j); akhir; akhir; akhir; Meskipun bukan EOF(f1), mulailah tmp:=a1; Baca(f1, a1); Jika bukan EOF(f1) maka Write(f, tmp, ' ') else Write(f, tmp); akhir; Meskipun bukan EOF(f2), mulailah tmp:=a2; Baca(f2, a2); Jika bukan EOF(f2) maka Tulis(f, tmp, ' ') else Write(f, tmp); akhir; tutup (p); tutup (f1); tutup(f2); s:=s2; akhir; Hapus (f1); Hapus (f2); Selesai;
Secara visual, operasi algoritma terlihat seperti ini (atas - urutan tidak berurutan, bawah - berurutan).
Penyortiran data eksternal
Sangat sering ada kebutuhan untuk mengurutkan beberapa data yang terletak di memori eksternal komputer. Dalam beberapa kasus, mereka memiliki ukuran yang mengesankan dan tidak dapat ditempatkan di RAM untuk memfasilitasi akses ke sana. Untuk kasus seperti itu, metode penyortiran eksternal digunakan.
Kebutuhan untuk mengakses media eksternal menurunkan efisiensi waktu pemrosesan.
Kompleksitas pekerjaannya adalah algoritme hanya dapat mengakses satu elemen aliran data pada satu waktu. Dan dalam hal ini, salah satu hasil terbaik ditunjukkan oleh metode merge sort, yang dapat membandingkan elemen dari dua file secara berurutan satu demi satu.
Membaca data darisumber eksternal, pemrosesan dan penulisannya ke file akhir dilakukan dalam blok (seri) yang dipesan. Menurut cara bekerja dengan ukuran seri yang dipesan, ada dua jenis pengurutan: penggabungan sederhana dan penggabungan alami.
Penggabungan sederhana
Dengan penggabungan sederhana, panjang seri adalah tetap.
Jadi, dalam file asli yang tidak disortir, semua seri terdiri dari satu elemen. Setelah langkah pertama, ukurannya bertambah menjadi dua. Selanjutnya - 4, 8, 16 dan seterusnya.
Ini bekerja seperti ini:
- File sumber (f) dibagi menjadi dua tambahan - f1, f2.
- Mereka kembali digabungkan menjadi satu file (f), tetapi pada saat yang sama semua elemen dibandingkan secara berpasangan dan membentuk pasangan. Ukuran seri pada langkah ini menjadi dua.
- Langkah 1 diulang.
- Langkah 2 diulang, tetapi 2s yang sudah dipesan digabungkan untuk membentuk 4s yang diurutkan.
- Perulangan berlanjut, meningkatkan seri pada setiap iterasi, hingga seluruh file diurutkan.
Bagaimana Anda tahu bahwa pengurutan luar dengan penggabungan sederhana sudah selesai?
- panjang seri baru (setelah penggabungan) tidak kurang dari jumlah total elemen;
- hanya tersisa satu episode;
- File tambahan f2 dibiarkan kosong.
Kerugian dari penggabungan sederhana adalah: karena panjang proses tetap pada setiap lintasan penggabungan, data yang dipesan sebagian akan memakan waktu lama untuk diproses seperti data yang benar-benar acak.
Fusi alami
Metode ini tidak membatasi panjangnyaseri, tetapi memilih semaksimal mungkin.
Algoritme pengurutan:
- Membaca urutan awal dari file f. Elemen pertama yang diterima ditulis ke file f1.
- Jika entri berikutnya memenuhi kondisi penyortiran, ditulis di sana, jika tidak, maka ke file tambahan kedua f2.
- Dengan cara ini, semua catatan dari file sumber didistribusikan, dan urutan berurutan terbentuk di f1, yang menentukan ukuran seri saat ini.
- File f1 dan f2 digabungkan.
- Siklus berulang.
Karena ukuran deret tidak tetap, akhir deret perlu ditandai dengan karakter khusus. Karena itu, saat menggabungkan, jumlah perbandingan meningkat. Selain itu, ukuran salah satu file tambahan mungkin mendekati ukuran aslinya.
Rata-rata, penggabungan alami lebih efisien daripada penggabungan sederhana dengan pengurutan eksternal.
Fitur algoritma
Saat membandingkan dua nilai identik, metode mempertahankan urutan aslinya, yaitu stabil.
Proses penyortiran dapat berhasil dipecah menjadi beberapa utas.
Video dengan jelas mendemonstrasikan pengoperasian algoritma merge sort.
