Merge Sort Algorithm

În acest tutorial, veți afla despre sortarea îmbinării. De asemenea, veți găsi exemple de lucru de tip sortare C, C ++, Java și Python.

Merge Sort este unul dintre cei mai populari algoritmi de sortare care se bazează pe principiul algoritmului Divide and Conquer.

Aici, o problemă este împărțită în mai multe subprobleme. Fiecare sub-problemă este rezolvată individual. În cele din urmă, subproblemele sunt combinate pentru a forma soluția finală.

Exemplu Merge Sort

Împărțiți și cuceriți strategia

Folosind tehnica Divide and Conquer , împărțim o problemă în subprobleme. Când soluția pentru fiecare subproblemă este gata, „combinăm” rezultatele din subprobleme pentru a rezolva problema principală.

Să presupunem că ar trebui să sortăm o matrice A. O subproblemă ar fi să sortăm o subsecțiune a acestei matrice începând de la indexul p și terminând cu indicele r, notat ca A (p … r).

Împărțiți
Dacă q este punctul la jumătatea distanței dintre p și r, atunci putem împărți subarrayul A (p … r) în două matrice A (p … q) și A (q + 1, r).

Cuceriți
În etapa de cucerire, încercăm să sortăm atât matricele A (p … q), cât și A (q + 1, r). Dacă nu am ajuns încă la cazul de bază, împărțim din nou aceste două matrice și încercăm să le sortăm.

Combinați
Când pasul de cucerire ajunge la pasul de bază și obținem două subarrayuri sortate A (p … q) și A (q + 1, r) pentru matricea A (p … r), combinăm rezultatele creând o matrice sortată A ( p … r) din două submatricii sortate A (p … q) și A (q + 1, r).

Algoritmul MergeSort

Funcția MergeSort împarte în mod repetat matricea în două jumătăți până când ajungem la un stadiu în care încercăm să efectuăm MergeSort pe un subarray de dimensiunea 1, adică p == r.

După aceea, funcția de îmbinare intră în joc și combină matricele sortate în matrice mai mari până când întreaga matrice este îmbinată.

 MergeSort (A, p, r): dacă p> r returnează q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) merge (A, p, q, r )

Pentru a sorta o întreagă matrice, trebuie să apelăm MergeSort(A, 0, length(A)-1).

Așa cum se arată în imaginea de mai jos, algoritmul de sortare a îmbinării împarte recursiv matricea în jumătăți până când ajungem la cazul de bază al matricei cu 1 element. După aceea, funcția de îmbinare preia sub-tablourile sortate și le îmbină pentru a sorta treptat întreaga matrice.

Îmbinați sortarea în acțiune

Îmbinare Pasul de sortare Îmbinare

Fiecare algoritm recursiv depinde de un caz de bază și de capacitatea de a combina rezultatele din cazurile de bază. Sortarea Merge nu este diferită. Cea mai importantă parte a algoritmului de sortare a îmbinării este, ați ghicit, pasul de îmbinare.

Pasul de îmbinare este soluția la problema simplă a fuzionării a două liste sortate (matrici) pentru a construi o listă mare sortată (matrice).

Algoritmul menține trei indicatori, unul pentru fiecare dintre cele două matrice și unul pentru menținerea indicelui curent al matricei sortate finale.

Am ajuns la sfârșitul vreunei matrice? Nu: Comparați elementele actuale ale ambelor matrice Copiați elementul mai mic în matricea sortată Mutați indicatorul elementului care conține element mai mic Da: Copiați toate elementele rămase ale matricei ne-goale
Pas de îmbinare

Scrierea codului pentru algoritmul Merge

O diferență vizibilă între pasul de fuzionare pe care l-am descris mai sus și cel pe care îl folosim pentru sortarea fuzionării este că executăm funcția de fuzionare numai pe sub-tablouri consecutive.

Acesta este motivul pentru care avem nevoie doar de matrice, prima poziție, ultimul index al primului subarray (putem calcula primul index al celui de-al doilea subarray) și ultimul index al celui de-al doilea subarray.

Sarcina noastră este să fuzionăm două submatricii A (p … q) și A (q + 1 … r) pentru a crea o matrice sortată A (p … r). Deci intrările pentru funcție sunt A, p, q și r

Funcția de îmbinare funcționează după cum urmează:

  1. Creați copii ale sub-matricelor L ← A(p… q)și M ← A (q + 1 … r).
  2. Creați trei indicatori i, j și k
    1. Păstrez indicele curent al lui L, începând de la 1
    2. j menține indicele curent al lui M, începând de la 1
    3. k menține indicele curent al lui A (p … q), începând cu p.
  3. Până când ajungem la sfârșitul lui L sau M, alegeți cel mai mare dintre elementele din L și M și plasați-le în poziția corectă la A (p … q)
  4. Când rămânem fără elemente în L sau M, ridicați elementele rămase și introduceți A (p … q)

În cod, ar arăta astfel:

 // 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++; ) )

Funcția Merge () explicată pas cu pas

Se întâmplă multe în această funcție, deci să luăm un exemplu pentru a vedea cum ar funcționa acest lucru.

Ca de obicei, o imagine spune o mie de cuvinte.

Fuzionarea a două submatricii consecutive de matrice

Matricea A (0 … 5) conține două submatricii sortate A (0 … 3) și A (4 … 5). Să vedem cum funcția de îmbinare va îmbina cele două matrice.

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

Pasul 1: Creați copii duplicate ale sub-tablourilor pentru a fi sortate

  // 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)
Creați copii ale subarrays-urilor pentru îmbinare

Pasul 2: Mențineți indicele curent al sub-tablourilor și al matricei principale

  int i, j, k; i = 0; j = 0; k = p;
Mențineți indicii copiilor sub-matricei și matricei principale

Pasul 3: Până când ajungem la capătul lui L sau M, alegeți mai mare dintre elementele L și M și plasați-le în poziția corectă la 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++; )
Comparând elemente individuale ale subarrays-urilor sortate până ajungem la sfârșitul unuia

Pasul 4: Când rămânem fără elemente în L sau M, ridicați elementele rămase și introduceți A (p … r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Copiați elementele rămase din prima matrice în subarrayul principal 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Copiați elementele rămase ale celei de-a doua matrice în subarrayul principal

Acest pas ar fi fost necesar dacă dimensiunea lui M ar fi mai mare decât L.

La sfârșitul funcției de îmbinare, subarray-ul A (p … r) este sortat.

Exemple Python, Java și 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; )

Combinați complexitatea sortării

Complexitatea timpului

Complexitatea celui mai bun caz: O (n * log n)

Cel mai prost caz de complexitate: O (n * log n)

Complexitatea medie a cazurilor: O (n * log n)

Complexitatea spațială

Complexitatea spațială a sortării de îmbinare este O (n).

Îmbinați aplicațiile de sortare

  • Problema numărării inversiunilor
  • Sortare externă
  • Aplicații de comerț electronic

Articole interesante...