Gabungkan Algoritma Susun

Dalam tutorial ini, anda akan belajar mengenai penggabungan jenis. Anda juga akan dapati contoh penggabungan jenis C, C ++, Java dan Python.

Merge Sort adalah salah satu algoritma penyortiran yang paling popular berdasarkan prinsip Algoritma Divide and Conquer.

Di sini, masalah terbahagi kepada beberapa sub-masalah. Setiap sub-masalah diselesaikan secara individu. Akhirnya, sub-masalah digabungkan untuk membentuk penyelesaian terakhir.

Contoh Gabungan Susun

Strategi Membahagi dan Menakluki

Dengan menggunakan teknik Divide and Conquer , kami membahagikan masalah kepada sub-masalah. Apabila penyelesaian untuk setiap sub-masalah sudah siap, kita 'menggabungkan' hasil dari sub-masalah untuk menyelesaikan masalah utama.

Katakan kita harus menyusun array A. Subproblem adalah untuk menyusun sub-bahagian array ini bermula pada indeks p dan berakhir pada indeks r, dilambangkan sebagai A (p … r).

Bagilah
Jika q adalah titik separuh jalan antara p dan r, maka kita boleh membahagikan subarray A (p… r) menjadi dua tatasusunan A (p… q) dan A (q + 1, r).

Menaklukkan
Pada langkah penaklukan, kami cuba menyusun kedua subarrays A (p … q) dan A (q + 1, r). Sekiranya kita belum mencapai asasnya, kita sekali lagi membahagikan kedua-dua subaraf ini dan cuba menyusunnya.

Gabungkan
Ketika langkah penakluk mencapai langkah dasar dan kita mendapat dua subarrays disusun A (p… q) dan A (q + 1, r) untuk array A (p… r), kita menggabungkan hasilnya dengan membuat susunan A yang disusun ( p… r) dari dua subaraf disusun A (p… q) dan A (q + 1, r).

Algoritma MergeSort

Fungsi MergeSort berulang kali membahagi susunan menjadi dua bahagian sehingga kita mencapai tahap di mana kita cuba melakukan MergeSort pada subarray berukuran 1 iaitu p == r.

Selepas itu, fungsi penggabungan dimainkan dan menggabungkan susunan yang disusun menjadi tatasusunan yang lebih besar sehingga keseluruhan susunan digabungkan.

 MergeSort (A, p, r): if p> r return q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) menggabungkan (A, p, q, r) )

Untuk menyusun keseluruhan susunan, kita perlu memanggil MergeSort(A, 0, length(A)-1).

Seperti yang ditunjukkan dalam gambar di bawah, algoritma penggabungan jenis secara berkala membagi susunan menjadi dua hingga kita mencapai kes asas array dengan 1 elemen. Selepas itu, fungsi penggabungan mengambil sub-array yang disusun dan menggabungkannya untuk menyusun keseluruhan array secara beransur-ansur.

Gabungkan tindakan

The merge Step of Merge Jenis

Setiap algoritma rekursif bergantung pada kes asas dan kemampuan untuk menggabungkan hasil dari kes asas. Penggabungan jenis tidak berbeza. Bahagian terpenting dari algoritma penggabungan jenis adalah, anda dapat meneka, langkah bergabung.

Langkah penggabungan adalah penyelesaian untuk masalah sederhana penggabungan dua senarai yang disusun (array) untuk membina satu senarai yang disusun besar (array).

Algoritma mengekalkan tiga titik, satu untuk setiap dua tatasusunan dan satu untuk mengekalkan indeks semasa dari susunan akhir yang disusun.

Adakah kita telah sampai ke penghujung array? Tidak: Bandingkan elemen semasa kedua-dua array Salin elemen yang lebih kecil ke dalam susunan yang disusun Pindahkan penunjuk elemen yang mengandungi unsur yang lebih kecil Ya: Salin semua unsur yang tersisa daripada array yang tidak kosong
Gabungkan langkah

Menulis Kod untuk Algoritma Gabungan

Perbezaan yang ketara antara langkah penggabungan yang kami jelaskan di atas dan yang kami gunakan untuk penggabungan adalah bahawa kami hanya menjalankan fungsi penggabungan pada sub-array berturut-turut.

Inilah sebabnya mengapa kita hanya memerlukan array, kedudukan pertama, indeks terakhir subarray pertama (kita dapat mengira indeks pertama subarray kedua) dan indeks terakhir subarray kedua.

Tugas kami adalah untuk menggabungkan dua subarrays A (p… q) dan A (q + 1… r) untuk membuat susunan A (p… r) yang disusun. Jadi input untuk fungsi tersebut adalah A, p, q dan r

Fungsi penggabungan berfungsi seperti berikut:

  1. Buat salinan subarrays L ← A(p… q)dan M ← A (q + 1… r).
  2. Buat tiga petunjuk i, j dan k
    1. saya mengekalkan indeks L semasa, bermula pada 1
    2. j mengekalkan indeks M semasa, bermula pada 1
    3. k mengekalkan indeks A (p… q) semasa, bermula dari p.
  3. Sehingga kita mencapai hujung L atau M, pilih yang lebih besar di antara unsur-unsur dari L dan M dan letakkan di kedudukan yang betul di A (p … q)
  4. Apabila kita kehabisan unsur sama ada L atau M, ambil elemen yang tinggal dan masukkan A (p… q)

Dalam kod, ini akan kelihatan seperti:

 // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) )

Gabungan () Fungsi yang dijelaskan Langkah-demi-Langkah

Banyak yang berlaku dalam fungsi ini, jadi mari kita ambil contoh untuk melihat bagaimana ini berfungsi.

Seperti biasa, gambar mengucapkan seribu perkataan.

Menggabungkan dua subaraf susunan berturut-turut

Susunan A (0… 5) mengandungi dua subarrays yang disusun A (0… 3) dan A (4… 5). Mari kita lihat bagaimana fungsi penggabungan akan menggabungkan dua tatasusunan.

 void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)

Langkah 1: Buat salinan pendua sub-array untuk disusun

  // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L(4), M(2); for (int i = 0; i < 4; i++) L(i) = arr(p + i); // L(0,1,2,3) = A(0,1,2,3) = (1,5,10,12) for (int j = 0; j < 2; j++) M(j) = arr(q + 1 + j); // M(0,1,2,3) = A(4,5) = (6,9)
Buat salinan subarrays untuk penggabungan

Langkah 2: Kekalkan indeks sub-array dan array utama semasa

  int i, j, k; i = 0; j = 0; k = p;
Simpan indeks salinan sub array dan array utama

Langkah 3: Sehingga kita mencapai akhir sama ada L atau M, pilih yang lebih besar di antara elemen L dan M dan letakkan di kedudukan yang betul di A (p… r)

  while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; )
Membandingkan elemen individu subarray yang disusun sehingga kita mencapai akhir

Langkah 4: Apabila kita kehabisan unsur sama ada L atau M, ambil elemen yang tinggal dan masukkan A (p… r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Salin elemen yang tinggal dari array pertama ke subarray utama 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Salin elemen yang tersisa dari array kedua ke subarray utama

Langkah ini akan diperlukan sekiranya ukuran M lebih besar daripada L.

Pada akhir fungsi penggabungan, subarray A (p… r) disusun.

Contoh Python, Java dan C / C ++

Python Java C C ++ 
 # MergeSort in Python def mergeSort(array): if len(array)> 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array(:r) M = array(r:) # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A(p… r) while i < len(L) and j < len(M): if L(i) < M(j): array(k) = L(i) i += 1 else: array(k) = M(j) j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A(p… r) while i < len(L): array(k) = L(i) i += 1 k += 1 while j < len(M): array(k) = M(j) j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array(i), end=" ") print() # Driver program if __name__ == '__main__': array = (6, 5, 12, 10, 9, 1) mergeSort(array) print("Sorted array is: ") printList(array) 
 // Merge sort in Java class MergeSort ( // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L() = new int(n1); int M() = new int(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver program public static void main(String args()) ( int arr() = ( 6, 5, 12, 10, 9, 1 ); MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); ) )
 // Merge sort in C #include // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) printf("%d ", arr(i)); printf(""); ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); )
 // Merge sort in C++ #include using namespace std; // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) cout << arr(i) << " "; cout << endl; ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); cout << "Sorted array: "; printArray(arr, size); return 0; )

Merumuskan Kerumitan Susun

Kerumitan Masa

Kerumitan Kes Terbaik: O (n * log n)

Kerumitan Kes Terburuk: O (n * log n)

Kerumitan Kes Purata: O (n * log n)

Kerumitan Ruang

Kerumitan ruang bagi jenis gabungan adalah O (n).

Gabungan Aplikasi Susun

  • Masalah kiraan penyongsangan
  • Pengisihan luaran
  • Aplikasi e-dagang

Artikel menarik...