V tej vadnici boste izvedeli več o razvrščanju med spajanjem. Prav tako boste našli delovne primere združevanja sort C, C ++, Java in Python.
Merge Sort je eden najbolj priljubljenih algoritmov za razvrščanje, ki temelji na principu Divide and Conquer Algorithm.
Tu je problem razdeljen na več podproblemov. Vsak pod-problem se reši posebej. Končno se podproblemi kombinirajo in tvorijo končno rešitev.
Primer spajanja razvrščanja
Strategija razdeli in osvoji
Z uporabo tehnike Divide and Conquer problem razdelimo na podprobleme. Ko je rešitev za vsak podproblem pripravljena, rezultate podproblemov 'združimo', da rešimo glavni problem.
Recimo, da bi morali razvrstiti matriko A. Podproblem bi bil razvrščanje pododdelka te matrike, ki se začne pri indeksu p in konča pri indeksu r, označenem z A (p … r).
Razdeli
Če je q polovična točka med p in r, potem lahko podmrežo A (p… r) razdelimo na dva polja A (p… q) in A (q + 1, r).
Conquer
V koraku conquer poskušamo razvrstiti tako podniz A (p… q) in A (q + 1, r). Če še nismo dosegli osnovnega primera, spet razdelimo obe podniz in jih poskušamo razvrstiti.
Združi
Ko korak osvajanja doseže osnovni korak in dobimo dva razvrščena podrebra A (p… q) in A (q + 1, r) za matriko A (p… r), rezultate združimo z ustvarjanjem razvrščenega polja A ( p… r) iz dveh razvrščenih podnizov A (p… q) in A (q + 1, r).
Algoritem MergeSort
Funkcija MergeSort večkrat deli matriko na dve polovici, dokler ne dosežemo stopnje, ko poskušamo MergeSort izvesti na podnizu velikosti 1, tj. P == r.
Po tem začne delovati funkcija spajanja in združuje razvrščene nize v večje nize, dokler se celotna matrika ne združi.
MergeSort (A, p, r): če je p> r vrne q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) združi (A, p, q, r )
Če želite razvrstiti celotno matriko, moramo poklicati MergeSort(A, 0, length(A)-1).
Kot je prikazano na spodnji sliki, algoritem za združevanje razvrsti matriko na polovice, dokler ne dosežemo osnovnega primera matrike z 1 elementom. Po tem funkcija spajanja pobere razvrščene podniz in jih združi, da postopoma razvrsti celotno matriko.
Združi razvrščanje v akciji
Spajanje korak z zlivanjem
Vsak rekurzivni algoritem je odvisen od osnovnega primera in sposobnosti kombiniranja rezultatov osnovnih primerov. Razvrščanje združevanja ni nič drugače. Najpomembnejši del algoritma za združevanje je, uganili ste, korak spajanja.
Korak združevanja je rešitev preprostega problema združevanja dveh razvrščenih seznamov (nizov) za izdelavo enega velikega razvrščenega seznama (polja).
Algoritem vzdržuje tri kazalce, po enega za vsakega od obeh nizov in enega za vzdrževanje trenutnega indeksa končnega razvrščenega polja.
Smo prišli do konca katerega koli polja? Ne: Primerjaj trenutne elemente obeh nizov Kopiraj manjši element v razvrščeno polje Premakni kazalec elementa, ki vsebuje manjši element Da: Kopiraj vse preostale elemente neprazne matrike
Korak spajanja
Pisanje kode za algoritem spajanja
Opazna razlika med korakom združevanja, ki smo ga opisali zgoraj, in tistim, ki ga uporabljamo za sortiranje združevanja, je, da funkcijo združevanja izvajamo samo na zaporednih podnizh.
Zato potrebujemo samo matriko, prvi položaj, zadnji indeks prve podreze (lahko izračunamo prvi indeks druge podreze) in zadnji indeks druge podreze.
Naša naloga je združiti dve podniz A (p… q) in A (q + 1… r), da dobimo razvrščeno matriko A (p… r). Vhodi v funkcijo so torej A, p, q in r
Funkcija spajanja deluje na naslednji način:
- Ustvarite kopije podnizov
L ← A(p… q)in M ← A (q + 1… r). - Ustvari tri kazalce i, j in k
- i ohranja trenutni indeks L, začenši pri 1
- j ohranja trenutni indeks M, ki se začne pri 1
- k ohranja trenutni indeks A (p… q), začenši pri p.
- Dokler ne pridemo do konca L ali M, med elementi iz L in M izberite večjega in jih postavite v pravi položaj v A (p… q)
- Ko nam zmanjka elementov v L ali M, poberemo preostale elemente in vstavimo A (p… q)
V kodi bi to izgledalo takole:
// 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++; ) )
Funkcija Merge (), razložena po korakih
V tej funkciji se veliko dogaja, zato si vzemimo primer, da vidimo, kako bi to delovalo.
Kot ponavadi slika govori tisoč besed.
Združevanje dveh zaporednih podnizov matrike
Polje A (0… 5) vsebuje dva razvrščena podniz A (0… 3) in A (4… 5). Poglejmo, kako bo funkcija spajanja združila obe nizi.
void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)
1. korak: Ustvarite podvojene kopije podnizov, ki jih želite razvrstiti
// 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) 
Ustvarite kopije podniz za spajanje
2. korak: Ohranite trenutni indeks podniz in glavnega polja
int i, j, k; i = 0; j = 0; k = p; 
Vzdrževanje indeksov kopij pod matrike in glavne matrike
3. korak: Dokler ne pridemo do konca L ali M, med elementi L in M izberite večje in jih postavite v pravi položaj v 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++; ) 
Primerjava posameznih elementov razvrščenih podnizov, dokler ne pridemo do konca enega
4. korak: Ko nam zmanjka elementov bodisi v L bodisi v M, poberi preostale elemente in vstavi A (p… r)
// We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; ) 
Kopirajte preostale elemente iz prve matrike v glavno matriko
// We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) ) 
Kopirajte preostale elemente druge matrike v glavno podniz
Ta korak bi bil potreben, če bi bila velikost M večja od L.
Na koncu funkcije spajanja je podniz A (p… r) razvrščen.
Primeri Python, Java in 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; )
Kompleksnost razvrstitve spajanja
Zapletenost časa
Najboljša zapletenost: O (n * log n)
Najslabša zapletenost: O (n * log n)
Povprečna zahtevnost primera: O (n * log n)
Zapletenost prostora
Prostorska zapletenost vrst združevanja je O (n).
Združi razvrstitvene aplikacije
- Problem štetja inverzije
- Zunanje sortiranje
- Aplikacije za e-poslovanje
