Slå sammen sorteringsalgoritme

I denne opplæringen vil du lære om sammenslåingssortering. Du vil også finne arbeidseksempler på sammenslåing av sortering C, C ++, Java og Python.

Merge Sort er en av de mest populære sorteringsalgoritmene som er basert på prinsippet om Divide and Conquer Algorithm.

Her er et problem delt inn i flere delproblemer. Hvert delproblem løses individuelt. Til slutt kombineres delproblemer for å danne den endelige løsningen.

Eksempel på Merge Sort

Del og erobre strategi

Ved hjelp av Divide and Conquer- teknikken deler vi et problem i delproblemer. Når løsningen på hvert delproblem er klar, 'kombinerer' vi resultatene fra delproblemene for å løse hovedproblemet.

Anta at vi måtte sortere en matrise A. Et underproblem ville være å sortere en underseksjon av denne matrisen fra indeks p og slutter med indeks r, betegnet som A (p… r).

Del
Hvis q er halvveis mellom p og r, så kan vi dele undergruppen A (p… r) i to matriser A (p… q) og A (q + 1, r).

Conquer
I erobringstrinnet prøver vi å sortere både underarrangementene A (p… q) og A (q + 1, r). Hvis vi ennå ikke har nådd basissaken, deler vi begge disse underarrayene igjen og prøver å sortere dem.

Kombiner
Når erobringstrinnet når grunntrinnet og vi får to sorterte underarrays A (p… q) og A (q + 1, r) for matrise A (p… r), kombinerer vi resultatene ved å lage en sortert matrise A ( p… r) fra to sorterte underarrays A (p… q) og A (q + 1, r).

MergeSort-algoritmen

MergeSort-funksjonen deler arrayet gjentatte ganger i to halvdeler til vi når et stadium der vi prøver å utføre MergeSort på en undergruppe av størrelse 1, dvs. p == r.

Etter det kommer flettefunksjonen til spill og kombinerer de sorterte matriser i større matriser til hele matrisen er slått sammen.

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

For å sortere en hel matrise må vi ringe MergeSort(A, 0, length(A)-1).

Som vist på bildet nedenfor, deler sorteringsalgoritmen rekursivt arrayet i halvdeler til vi når basissaken til array med 1 element. Etter det plukker funksjonen opp de sorterte underarrayene og fletter dem sammen for å gradvis sortere hele matrisen.

Slå sammen sortering i aksjon

Den flettingen trinn av flettesortering

Hver rekursiv algoritme er avhengig av en basissak og evnen til å kombinere resultatene fra basissaker. Slå sammen sortering er ikke annerledes. Den viktigste delen av sammenslåingssorteringsalgoritmen er, gjettet du det, sammenslåingstrinn.

Sammenslåingstrinnet er løsningen på det enkle problemet med å slå sammen to sorterte lister (matriser) for å bygge en stor sortert liste (matrise).

Algoritmen opprettholder tre pekere, en for hver av de to matriser og en for å opprettholde den nåværende indeksen til den endelige sorterte matrisen.

Har vi nådd slutten av noen av arrangementene? Nei: Sammenlign gjeldende elementer i begge matriser Kopier mindre element i sortert array Flytt pekeren til element som inneholder mindre element Ja: Kopier alle gjenværende elementer i ikke-tom matrise
Slå sammen trinn

Skrive koden for sammenslåingsalgoritme

En merkbar forskjell mellom sammenslåingstrinnet vi beskrev ovenfor og det vi bruker for flettesortering, er at vi bare utfører flettefunksjonen på påfølgende underarrayer.

Dette er grunnen til at vi bare trenger matrisen, den første posisjonen, den siste indeksen til den første undergruppen (vi kan beregne den første indeksen til den andre undergruppen) og den siste indeksen til den andre undergruppen.

Vår oppgave er å slå sammen to undergrupper A (p… q) og A (q + 1… r) for å lage en sortert matrise A (p… r). Så inngangene til funksjonen er A, p, q og r

Sammenslåingsfunksjonen fungerer som følger:

  1. Lag kopier av underarrayene L ← A(p… q)og M ← A (q + 1… r).
  2. Lag tre pekere i, j og k
    1. jeg opprettholder nåværende indeks på L, fra 1
    2. j opprettholder gjeldende indeks på M, fra 1
    3. k opprettholder den nåværende indeksen på A (p… q), og begynner på p.
  3. Inntil vi når slutten av enten L eller M, velg det større blant elementene fra L og M og plasser dem i riktig posisjon ved A (p … q)
  4. Når vi går tom for elementer i enten L eller M, plukk opp de gjenværende elementene og legg inn A (p… q)

I kode vil dette se ut som:

 // 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 () Funksjon forklart trinnvis

Det skjer mye i denne funksjonen, så la oss ta et eksempel for å se hvordan dette vil fungere.

Som vanlig snakker et bilde tusen ord.

Slår sammen to sammenhengende underarrayer av matrisen

Matrisen A (0… 5) inneholder to sorterte underarrays A (0… 3) og A (4… 5). La oss se hvordan flettefunksjonen vil slå sammen de to matriser.

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

Trinn 1: Lag duplikatkopier av underarrayer som skal sorteres

  // 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)
Lag kopier av underarrays for sammenslåing

Trinn 2: Vedlikehold gjeldende indeks for underarrayer og hovedmatrise

  int i, j, k; i = 0; j = 0; k = p;
Opprettholde indekser for kopier av underarray og hovedarray

Trinn 3: Inntil vi når slutten av enten L eller M, velg større blant elementene L og M og plasser dem i riktig posisjon ved 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++; )
Sammenligning av individuelle elementer av sorterte underarrays til vi når slutten av en

Trinn 4: Når vi går tom for elementer i enten L eller M, plukk opp de gjenværende elementene og legg inn A (p… r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Kopier de gjenværende elementene fra den første matrisen til hovedundermatrisen 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Kopier gjenværende elementer i andre matrise til hovedundermat

Dette trinnet hadde vært nødvendig hvis størrelsen på M var større enn L.

På slutten av sammenslåingsfunksjonen sorteres underarray A (p… r).

Python, Java og C / C ++ eksempler

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

Merge Sort Complexity

Tidskompleksitet

Beste sakskompleksitet: O (n * log n)

Kompleksitet i verste tilfelle: O (n * log n)

Gjennomsnittlig sakskompleksitet: O (n * log n)

Romkompleksitet

Romkompleksiteten til sammenslåingssortering er O (n).

Slå sammen sorteringsapplikasjoner

  • Problem med inversjonstall
  • Ekstern sortering
  • E-handelsapplikasjoner

Interessante artikler...