Sorteeralgoritme samenvoegen

In deze zelfstudie leert u over samenvoegsortering. Ook vindt u werkende voorbeelden van samenvoegsortering C, C ++, Java en Python.

Merge Sort is een van de meest populaire sorteeralgoritmen die is gebaseerd op het principe van Divide and Conquer-algoritme.

Hier is een probleem opgedeeld in meerdere deelproblemen. Elk deelprobleem wordt afzonderlijk opgelost. Ten slotte worden deelproblemen gecombineerd om de uiteindelijke oplossing te vormen.

Voorbeeld van samenvoegen sorteren

Verdeel en heers strategie

Met behulp van de Divide and Conquer- techniek verdelen we een probleem in deelproblemen. Als de oplossing voor elk deelprobleem klaar is, 'combineren' we de resultaten van de deelproblemen om het hoofdprobleem op te lossen.

Stel dat we een array A moeten sorteren. Een subprobleem zou zijn om een ​​subsectie van deze array te sorteren, beginnend bij index p en eindigend bij index r, aangeduid als A (p… r).

Delen
Als q halverwege is tussen p en r, dan kunnen we de submatrix A (p… r) splitsen in twee arrays A (p… q) en A (q + 1, r).

Veroveren
In de veroveringsstap proberen we zowel de subarrays A (p… q) als A (q + 1, r) te sorteren. Als we het basisscenario nog niet hebben bereikt, verdelen we beide subarrays opnieuw en proberen ze te sorteren.

Combineren
Wanneer de veroveringsstap de basisstap bereikt en we krijgen twee gesorteerde subarrays A (p… q) en A (q + 1, r) voor array A (p… r), combineren we de resultaten door een gesorteerde array A ( p… r) uit twee gesorteerde subarrays A (p… q) en A (q + 1, r).

Het MergeSort-algoritme

De MergeSort-functie verdeelt de array herhaaldelijk in twee helften totdat we een stadium bereiken waarin we proberen MergeSort uit te voeren op een subarray van grootte 1, dwz p == r.

Daarna komt de samenvoegfunctie in het spel en combineert deze de gesorteerde arrays tot grotere arrays totdat de hele array is samengevoegd.

 MergeSort (A, p, r): als p> r retourneert q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) samenvoegen (A, p, q, r )

Om een ​​hele array te sorteren, moeten we aanroepen MergeSort(A, 0, length(A)-1).

Zoals te zien is in de onderstaande afbeelding, verdeelt het samenvoegsorteeralgoritme recursief de array in twee helften totdat we het basisscenario van de array met 1 element bereiken. Daarna pakt de samenvoegfunctie de gesorteerde sub-arrays op en voegt ze samen om geleidelijk de hele array te sorteren.

Sorteer samenvoegen in actie

De samenvoegstap van samenvoegen Sorteren

Elk recursief algoritme is afhankelijk van een basisscenario en de mogelijkheid om de resultaten van basisscases te combineren. Samenvoegen is niet anders. Het belangrijkste onderdeel van het samenvoegsorteeralgoritme is, je raadt het al, samenvoegstap.

De samenvoegstap is de oplossing voor het simpele probleem van het samenvoegen van twee gesorteerde lijsten (arrays) om één grote gesorteerde lijst (array) samen te stellen.

Het algoritme houdt drie aanwijzers bij, één voor elk van de twee arrays en één voor het behouden van de huidige index van de uiteindelijk gesorteerde array.

Hebben we het einde van een van de arrays bereikt? Nee: vergelijk huidige elementen van beide arrays Kopieer kleiner element naar gesorteerde array Verplaats pointer van element met kleiner element Ja: kopieer alle resterende elementen van niet-lege array
Stap samenvoegen

De code schrijven voor het samenvoegalgoritme

Een merkbaar verschil tussen de samenvoegstap die we hierboven hebben beschreven en degene die we gebruiken voor samenvoegsortering, is dat we de samenvoegfunctie alleen uitvoeren op opeenvolgende sub-arrays.

Daarom hebben we alleen de array nodig, de eerste positie, de laatste index van de eerste subarray (we kunnen de eerste index van de tweede subarray berekenen) en de laatste index van de tweede subarray.

Het is onze taak om twee subarrays A (p… q) en A (q + 1… r) samen te voegen om een ​​gesorteerde array A (p… r) te creëren. De invoer voor de functie is dus A, p, q en r

De samenvoegfunctie werkt als volgt:

  1. Maak kopieën van de subarrays L ← A(p… q)en M ← A (q + 1… r).
  2. Maak drie pointers i, j en k
    1. i handhaaft de huidige index van L, beginnend bij 1
    2. j handhaaft de huidige index van M, beginnend bij 1
    3. k handhaaft de huidige index van A (p… q), beginnend bij p.
  3. Kies tot we het einde van L of M bereiken de grootste van de elementen uit L en M en plaats ze op de juiste positie op A (p … q)
  4. Als we geen elementen meer hebben in L of M, pak dan de resterende elementen op en plaats A (p … q)

In code zou dit er als volgt uitzien:

 // 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 () Functie stap voor stap uitgelegd

Er gebeurt veel in deze functie, dus laten we een voorbeeld nemen om te zien hoe dit zou werken.

Zoals gewoonlijk zegt een foto meer dan duizend woorden.

Samenvoegen van twee opeenvolgende submatrices van een array

De array A (0… 5) bevat twee gesorteerde subarrays A (0… 3) en A (4… 5). Laten we eens kijken hoe de samenvoegfunctie de twee arrays zal samenvoegen.

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

Stap 1: Maak dubbele kopieën van subarrays die moeten worden gesorteerd

  // 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)
Maak kopieën van subarrays om samen te voegen

Stap 2: handhaaf de huidige index van sub-arrays en hoofdarray

  int i, j, k; i = 0; j = 0; k = p;
Behoud indices van kopieën van subarray en hoofdarray

Stap 3: Kies tot we het einde van L of M bereiken de grotere uit de elementen L en M en plaats ze op de juiste positie bij 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++; )
Individuele elementen van gesorteerde submatrices vergelijken totdat we het einde van één bereiken

Stap 4: Als we geen elementen meer hebben in L of M, pak dan de resterende elementen op en plaats A (p … r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Kopieer de overige elementen van de eerste array naar de hoofdsubarray 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Kopieer de resterende elementen van de tweede array naar de hoofdsubarray

Deze stap zou nodig zijn geweest als de maat van M groter was dan L.

Aan het einde van de samenvoegfunctie wordt de submatrix A (p… r) gesorteerd.

Python, Java en C / C ++ voorbeelden

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

Sorteercomplexiteit samenvoegen

Tijdscomplexiteit

Best Case Complexity: O (n * log n)

Worst Case Complexity: O (n * log n)

Gemiddelde casuscomplexiteit: O (n * log n)

Complexiteit van de ruimte

De ruimtecomplexiteit van samenvoegsortering is O (n).

Voeg sorteerapplicaties samen

  • Probleem met het aantal inversies
  • Externe sortering
  • E-commercetoepassingen

Interessante artikelen...