1. Pengenalan
Dalam tutorial ini, kita akan melihat algoritma Merge Sort dan pelaksanaannya di Java .
Penggabungan penggabungan adalah salah satu teknik penyisihan yang paling berkesan dan ia berdasarkan paradigma "bahagi dan menaklukkan".
2. Algoritma
Penggabungan penggabungan adalah algoritma "membahagi dan menaklukkan" di mana kami mula-mula membahagikan masalah itu kepada subproblem. Apabila penyelesaian untuk masalah kecil siap, kami menggabungkannya bersama-sama untuk mendapatkan penyelesaian terakhir untuk masalah ini.
Ini adalah salah satu algoritma yang dapat dilaksanakan dengan mudah menggunakan rekursi kerana kita menangani masalah kecil daripada masalah utama.
Algoritma dapat digambarkan sebagai proses 2 langkah berikut:
- Bahagikan: Pada langkah ini, kita membahagikan array input menjadi 2 bahagian , pivot menjadi titik tengah array. Langkah ini dilakukan secara rekursif untuk semua separuh susunan sehingga tidak ada lagi setengah tatasusunan untuk dibahagi.
- Conquer: Pada langkah ini, kita menyusun dan menggabungkan tatasusunan terbahagi dari bawah ke atas dan mendapatkan susunan yang disusun.
Gambar rajah berikut menunjukkan proses penyatuan gabungan untuk susunan contoh {10, 6, 8, 5, 7, 3, 4}.
Sekiranya kita melihat rajah ini dengan lebih dekat, kita dapat melihat bahawa susunan dibahagikan secara rekursif kepada dua bahagian sehingga ukuran menjadi 1. Setelah ukuran menjadi 1, proses penggabungan akan beraksi dan mula menggabungkan tatasusunan kembali sambil menyusun:
3. Pelaksanaan
Untuk pelaksanaannya, kami akan menulis fungsi mergeSort yang mengambil array input dan panjangnya sebagai parameter. Ini akan menjadi fungsi rekursif jadi kita memerlukan asas dan keadaan rekursif.
Keadaan asas memeriksa sama ada panjang array 1 dan ia akan kembali. Untuk kes yang selebihnya, panggilan rekursif akan dilaksanakan.
Untuk kes rekursif, kita mendapat indeks tengah dan membuat dua tatasusunan sementara l [] dan r [] . The mergeSort fungsi kemudiannya dipanggil secara rekursif untuk kedua-dua sub-tatasusunan:
public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }Kami kemudian memanggil fungsi penggabungan yang mengambil input dan kedua sub-array dan indeks permulaan dan akhir kedua-dua sub array .
The merge fungsi membandingkan unsur-unsur kedua-dua sub-tatasusunan satu demi satu dan meletakkan unsur yang lebih kecil ke dalam pelbagai input.
Apabila kita mencapai akhir salah satu sub-susunan, unsur-unsur selebihnya dari susunan yang lain disalin ke dalam array input sehingga memberikan kita susunan yang disusun terakhir:
public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } Ujian unit untuk program:
@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }4. Kerumitan
Oleh kerana penggabungan jenis adalah algoritma rekursif, kerumitan masa dapat dinyatakan sebagai hubungan rekursif berikut:
T(n) = 2T(n/2) + O(n)2T (n / 2) sesuai dengan masa yang diperlukan untuk menyusun sub-array dan waktu O (n) untuk menggabungkan keseluruhan array.
Apabila diselesaikan, kerumitan masa akan datang ke O (nLogn).
Ini berlaku untuk kes terburuk, rata-rata dan terbaik kerana ia akan selalu membahagi susunan menjadi dua dan kemudian bergabung.
Kerumitan ruang algoritma adalah O (n) kerana kami membuat susunan sementara dalam setiap panggilan berulang.
5. Kesimpulan
Dalam tutorial ringkas ini, kami melihat cara kerja algoritma penggabungan jenis dan bagaimana kami dapat menerapkannya di Java.
Keseluruhan kod kerja boleh didapati di GitHub.