Gabungkan Algoritma Sortir

Dalam tutorial ini, Anda akan belajar tentang merge sort. Selain itu, Anda akan menemukan contoh kerja dari merge sort C, C ++, Java dan Python.

Merge Sort adalah salah satu algoritma pengurutan paling populer yang didasarkan pada prinsip Algoritma Divide and Conquer.

Di sini, masalah dibagi menjadi beberapa sub-masalah. Setiap sub-masalah diselesaikan secara individual. Akhirnya, sub-masalah digabungkan untuk membentuk solusi akhir.

Contoh Merge Sort

Strategi Bagilah dan Taklukkan

Dengan menggunakan teknik Divide and Conquer , kami membagi masalah menjadi beberapa subproblem. Ketika solusi untuk setiap subproblem sudah siap, kami 'menggabungkan' hasil dari subproblem untuk menyelesaikan masalah utama.

Misalkan kita harus mengurutkan sebuah array A. Sebuah subproblem akan mengurutkan sub-bagian dari array ini dimulai dari indeks p dan berakhir pada indeks r, dilambangkan sebagai A (p… r).

Bagi
Jika q adalah titik tengah antara p dan r, maka kita dapat membagi subarray A (p… r) menjadi dua larik A (p… q) dan A (q + 1, r).

Penaklukan
Pada langkah penaklukan, kami mencoba untuk mengurutkan subarrays A (p… q) dan A (q + 1, r). Jika kami belum mencapai kasus dasarnya, kami membagi lagi kedua subarray ini dan mencoba mengurutkannya.

Menggabungkan
Ketika langkah penaklukan mencapai langkah dasar dan kita mendapatkan dua sub-array yang diurutkan A (p… q) dan A (q + 1, r) untuk array A (p… r), kita menggabungkan hasilnya dengan membuat array yang diurutkan A ( p… r) dari dua subarray yang diurutkan A (p… q) dan A (q + 1, r).

Algoritma MergeSort

Fungsi MergeSort berulang kali membagi array menjadi dua bagian sampai kita mencapai tahap di mana kita mencoba melakukan MergeSort pada subarray berukuran 1 yaitu p == r.

Setelah itu, fungsi penggabungan mulai dijalankan dan menggabungkan array yang diurutkan menjadi array yang lebih besar sampai seluruh array digabungkan.

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

Untuk mengurutkan seluruh array, kita perlu memanggil MergeSort(A, 0, length(A)-1).

Seperti yang ditunjukkan pada gambar di bawah ini, algoritma pengurutan gabungan secara rekursif membagi array menjadi dua sampai kita mencapai kasus dasar array dengan 1 elemen. Setelah itu, fungsi merge mengambil sub-array yang diurutkan dan menggabungkannya untuk mengurutkan seluruh array secara bertahap.

Gabungkan pengurutan dalam tindakan

The merge Langkah Merge Sort

Setiap algoritma rekursif bergantung pada kasus dasar dan kemampuan untuk menggabungkan hasil dari kasus dasar. Gabungkan jenis tidak berbeda. Bagian terpenting dari algoritme pengurutan penggabungan adalah, Anda dapat menebaknya, langkah penggabungan.

Langkah penggabungan adalah solusi untuk masalah sederhana menggabungkan dua daftar terurut (larik) untuk membangun satu daftar terurut besar (larik).

Algoritme mempertahankan tiga penunjuk, satu untuk masing-masing dari dua larik dan satu untuk mempertahankan indeks saat ini dari larik terurut terakhir.

Sudahkah kita mencapai akhir dari salah satu array? Tidak: Bandingkan elemen saat ini dari kedua larik Salin elemen yang lebih kecil ke dalam larik yang diurutkan Pindahkan penunjuk elemen yang berisi elemen yang lebih kecil Ya: Salin semua elemen yang tersisa dari larik yang tidak kosong
Gabungkan langkah

Penulisan Code for Merge Algorithm

Perbedaan mencolok antara langkah penggabungan yang kami jelaskan di atas dan yang kami gunakan untuk merge sort adalah kami hanya melakukan fungsi penggabungan pada sub-larik yang berurutan.

Inilah mengapa kita hanya membutuhkan larik, posisi pertama, indeks terakhir dari sub larik pertama (kita bisa menghitung indeks pertama dari sub larik kedua) dan indeks terakhir dari sub larik kedua.

Tugas kita adalah menggabungkan dua subarray A (p… q) dan A (q + 1… r) untuk membuat array yang diurutkan A (p… r). Jadi input ke fungsinya adalah A, p, q dan r

Fungsi penggabungan berfungsi sebagai berikut:

  1. Buat salinan subarray L ← A(p… q)dan M ← A (q + 1… r).
  2. Buat tiga petunjuk i, j dan k
    1. i mempertahankan indeks L saat ini, mulai dari 1
    2. j mempertahankan indeks M saat ini, mulai dari 1
    3. k mempertahankan indeks saat ini dari A (p… q), dimulai dari p.
  3. Sampai kita mencapai akhir dari L atau M, pilih yang lebih besar di antara elemen-elemen dari L dan M dan letakkan di posisi yang benar di A (p… q)
  4. Ketika kita kehabisan elemen baik di L atau M, ambil elemen yang tersisa dan masukkan ke A (p… q)

Dalam kode, ini akan terlihat 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++; ) )

Merge () Fungsi Dijelaskan Langkah Demi Langkah

Banyak yang terjadi dalam fungsi ini, jadi mari kita ambil contoh untuk melihat cara kerjanya.

Seperti biasa, sebuah gambar berbicara ribuan kata.

Menggabungkan dua subarray yang berurutan

Array A (0… 5) berisi dua subarrays A (0… 3) dan A (4… 5) yang diurutkan. Mari kita lihat bagaimana fungsi penggabungan akan menggabungkan dua array.

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

Langkah 1: Buat salinan duplikat sub-array untuk disortir

  // 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 subarray untuk digabungkan

Langkah 2: Pertahankan indeks sub-array dan array utama saat ini

  int i, j, k; i = 0; j = 0; k = p;
Menjaga indeks salinan sub larik dan larik utama

Langkah 3: Sampai kita mencapai akhir dari L atau M, pilih yang lebih besar di antara elemen L dan M dan letakkan di posisi yang benar 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 dari subarray yang diurutkan hingga kami mencapai akhir salah satu

Langkah 4: Ketika kita kehabisan elemen baik di L atau M, ambil elemen yang tersisa dan masukkan ke 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 tersisa dari larik pertama ke sub larik 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 larik kedua ke sub larik utama

Langkah ini diperlukan jika ukuran M lebih besar dari L.

Di akhir fungsi penggabungan, subarray A (p… r) diurutkan.

Contoh Python, Java dan C / C ++

Python Java 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; )

Gabungkan Kompleksitas Sortir

Kompleksitas Waktu

Kompleksitas Kasus Terbaik: O (n * log n)

Kompleksitas Kasus Terburuk: O (n * log n)

Kompleksitas Kasus Rata-rata: O (n * log n)

Kompleksitas Ruang

Kompleksitas ruang dari jenis gabungan adalah O (n).

Gabungkan Aplikasi Sortir

  • Masalah hitungan pembalikan
  • Penyortiran eksternal
  • Aplikasi e-commerce

Artikel yang menarik...