Slå ihop sorteringsalgoritm

I den här guiden lär du dig merge merge sort. Du hittar också arbetsexempel på sammanslagningssortering C, C ++, Java och Python.

Merge Sort är en av de mest populära sorteringsalgoritmerna som bygger på principen Divide and Conquer Algorithm.

Här är ett problem uppdelat i flera delproblem. Varje delproblem löses individuellt. Slutligen kombineras delproblem för att bilda den slutliga lösningen.

Exempel på Merge Sort

Dela och erövra strategi

Med hjälp av Divide and Conquer- tekniken delar vi upp ett problem i delproblem. När lösningen på varje delproblem är klar ”kombinerar” vi resultaten från delproblemen för att lösa huvudproblemet.

Antag att vi var tvungna att sortera en matris A. Ett underproblem skulle vara att sortera en delavsnitt av denna matris med början vid index p och slutade på index r, betecknad A (p… r).

Dela
Om q är halvvägspunkten mellan p och r, så kan vi dela underarray A (p… r) i två matriser A (p… q) och A (q + 1, r).

Conquer
I erövringssteget försöker vi sortera både underarrangemang A (p… q) och A (q + 1, r). Om vi ​​ännu inte har nått basfallet delar vi igen båda dessa underarrangemang och försöker sortera dem.

Kombinera
När erövringssteget når bassteget och vi får två sorterade underarrayer A (p… q) och A (q + 1, r) för array A (p… r), kombinerar vi resultaten genom att skapa en sorterad array A ( p… r) från två sorterade underarrangemang A (p… q) och A (q + 1, r).

MergeSort-algoritmen

MergeSort-funktionen delar upp matrisen upprepade gånger i två halvor tills vi når ett stadium där vi försöker utföra MergeSort på en undergrupp av storlek 1, dvs p == r.

Efter det kommer sammanslagningsfunktionen att spela och kombinerar de sorterade matriserna i större matriser tills hela matrisen slås samman.

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

För att sortera en hel grupp måste vi ringa MergeSort(A, 0, length(A)-1).

Som visas i bilden nedan delar algoritmen för sammanslagningssortering rekursivt arrayen i halvor tills vi når basfallet för array med 1 element. Efter det plockar samlingsfunktionen upp de sorterade undermatriserna och slår ihop dem för att gradvis sortera hela matrisen.

Slå samman sortering i aktion

Den sammanslagning Steg Merge Sort

Varje rekursiv algoritm är beroende av ett basfall och förmågan att kombinera resultaten från basfall. Sammanfoga sortering är inte annorlunda. Den viktigaste delen av algoritmen för sammanslagningssortering är, antar du, sammanslagningssteg.

Sammanfogningssteget är lösningen på det enkla problemet att slå samman två sorterade listor (arrays) för att bygga en stor sorterad lista (array).

Algoritmen upprätthåller tre pekare, en för var och en av de två matriserna och en för att bibehålla det aktuella indexet för den slutliga sorterade matrisen.

Har vi nått slutet på någon av matriserna? Nej: Jämför aktuella element i båda matriserna Kopiera mindre element till sorterad matris Flytta pekaren på element som innehåller mindre element Ja: Kopiera alla återstående element i icke-tom matris
Sammanfoga steg

Skriva koden för sammanslagningsalgoritm

En märkbar skillnad mellan det sammanslagningssteg som vi har beskrivit ovan och det vi använder för sammanslagningssortering är att vi bara utför sammanslagningsfunktionen i på varandra följande underarrayer.

Det är därför vi bara behöver matrisen, den första positionen, det sista indexet för den första undergruppen (vi kan beräkna det första indexet för den andra undergruppen) och det sista indexet för den andra undergruppen.

Vår uppgift är att slå samman två underarrangemang A (p… q) och A (q + 1… r) för att skapa en sorterad matris A (p… r). Så ingångarna till funktionen är A, p, q och r

Sammanfogningsfunktionen fungerar enligt följande:

  1. Skapa kopior av undergrupperna L ← A(p… q)och M ← A (q + 1 … r).
  2. Skapa tre pekare i, j och k
    1. Jag håller nuvarande index på L, med början 1
    2. j upprätthåller aktuellt index på M, med början 1
    3. k bibehåller det aktuella indexet för A (p… q), med början på p.
  3. Tills vi når slutet av antingen L eller M, välj det större bland elementen från L och M och placera dem i rätt läge vid A (p … q)
  4. När vi har slut på element i antingen L eller M, plocka upp de återstående elementen och lägg i A (p … q)

I kod ser det ut så här:

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

Sammanfoga () Funktion förklaras steg för steg

Mycket händer i den här funktionen, så låt oss ta ett exempel för att se hur detta skulle fungera.

Som vanligt talar en bild tusen ord.

Sammanfogar två på varandra följande underarrangemang av matrisen

Matrisen A (0… 5) innehåller två sorterade underarrangemang A (0… 3) och A (4… 5). Låt oss se hur sammanslagningsfunktionen kommer att slå samman de två matriserna.

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

Steg 1: Skapa dubbla kopior av undermatriser som ska sorteras

  // 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)
Skapa kopior av underarrayer för sammanslagning

Steg 2: Underhåll aktuellt index för undermatriser och huvudmatris

  int i, j, k; i = 0; j = 0; k = p;
Underhåll index för kopior av undermatris och huvudmatris

Steg 3: Tills vi når slutet av antingen L eller M, välj större bland elementen L och M och placera dem i rätt läge vid 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++; )
Jämföra enskilda element i sorterade subarrays tills vi når slutet på en

Steg 4: När vi har slut på element i antingen L eller M, plocka upp de återstående elementen och lägg i A (p … r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Kopiera de återstående elementen från den första matrisen till huvudundersamlingen 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Kopiera återstående element i den andra matrisen till huvudundersamlingen

Detta steg hade varit nödvändigt om storleken på M var större än L.

I slutet av sammanslagningsfunktionen sorteras underarrangemanget A (p… r).

Python, Java och C / C ++ exempel

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

Sammanfoga sorteringskomplexitet

Tidskomplexitet

Bästa fallkomplexitet: O (n * log n)

Värsta fallets komplexitet: O (n * log n)

Genomsnittlig fallkomplexitet: O (n * log n)

Rymdkomplexitet

Rymdkomplexiteten för sammanslagningssortering är O (n).

Slå ihop sorteringsapplikationer

  • Problem med inversionen
  • Extern sortering
  • E-handelsapplikationer

Intressanta artiklar...