Flet sorteringsalgoritme

I denne vejledning lærer du om flettsortering. Du finder også arbejdseksempler på flettsortering C, C ++, Java og Python.

Merge Sort er en af ​​de mest populære sorteringsalgoritmer, der er baseret på princippet om Divide and Conquer Algorithm.

Her er et problem opdelt i flere underproblemer. Hvert delproblem løses individuelt. Endelig kombineres delproblemer til den endelige løsning.

Eksempel på flet sortering

Opdel og erobre strategi

Ved hjælp af Divide and Conquer- teknikken opdeler vi et problem i delproblemer. Når løsningen på hvert delproblem er klar, 'kombinerer' vi resultaterne fra delproblemerne for at løse hovedproblemet.

Antag, at vi var nødt til at sortere en matrix A. Et underproblem ville være at sortere en underafsnit af denne matrix startende ved indeks p og ender ved indeks r, betegnet som A (p… r).

Opdel
Hvis q er halvvejs mellem p og r, så kan vi opdele underarray A (p… r) i to arrays A (p… q) og A (q + 1, r).

Erobre
I erobringstrinet forsøger vi at sortere både underarrangementer A (p… q) og A (q + 1, r). Hvis vi endnu ikke har nået basissagen, deler vi begge disse underarrays igen og prøver at sortere dem.

Kombiner
Når erobringstrinet når basistrinet, og vi får to sorterede underarrays A (p… q) og A (q + 1, r) for array A (p… r), kombinerer vi resultaterne ved at oprette en sorteret array A ( p… r) fra to sorterede underarrays A (p… q) og A (q + 1, r).

MergeSort-algoritmen

MergeSort-funktionen opdeler arrayet gentagne gange i to halvdele, indtil vi når et stadium, hvor vi forsøger at udføre MergeSort på et underarray af størrelse 1 dvs. p == r.

Derefter kommer fletningsfunktionen i spil og kombinerer de sorterede arrays i større arrays, indtil hele arrayet er flettet.

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

For at sortere et helt array skal vi ringe MergeSort(A, 0, length(A)-1).

Som vist på billedet nedenfor deler flettsorteringsalgoritmen arrayet rekursivt i halvdele, indtil vi når basissagen til array med 1 element. Derefter opfanger flettefunktionen de sorterede underarrays og fletter dem for gradvist at sortere hele arrayet.

Flet sortering i aktion

Den sammenfletning Trin af mergesort

Hver rekursiv algoritme er afhængig af en basissag og evnen til at kombinere resultaterne fra basissager. Flet sortering er ikke anderledes. Den vigtigste del af flette sorteringsalgoritmen er, gættede du det, flette trin.

Fletrin er løsningen på det enkle problem at flette to sorterede lister (arrays) for at opbygge en stor sorteret liste (array).

Algoritmen opretholder tre markører, en til hver af de to arrays og en til at opretholde det aktuelle indeks for det endelige sorterede array.

Er vi nået til slutningen af ​​nogen af ​​arrays? Nej: Sammenlign aktuelle elementer i begge arrays Kopier mindre element i sorteret array Flyt markør for element, der indeholder mindre element Ja: Kopier alle resterende elementer i ikke-tom array
Flet trin

Skrivning af koden til fletningsalgoritme

En mærkbar forskel mellem det sammenfletningstrin, vi beskrev ovenfor, og det, vi bruger til flettsortering, er, at vi kun udfører fletningsfunktionen på fortløbende underarrays.

Dette er grunden til, at vi kun har brug for arrayet, den første position, det sidste indeks for det første subarray (vi kan beregne det første indeks for det andet subarray) og det sidste indeks for det andet subarray.

Vores opgave er at flette to underarrays A (p… q) og A (q + 1… r) for at oprette et sorteret array A (p… r). Så indgangene til funktionen er A, p, q og r

Fletningsfunktionen fungerer som følger:

  1. Opret kopier af underarrangementer L ← A(p… q)og M ← A (q + 1… r).
  2. Opret tre markører i, j og k
    1. jeg opretholder det aktuelle indeks på L, der starter ved 1
    2. j opretholder det aktuelle indeks på M, der starter ved 1
    3. k opretholder det aktuelle indeks på A (p… q), startende ved p.
  3. Indtil vi når slutningen af ​​enten L eller M, skal du vælge det større blandt elementerne fra L og M og placere dem i den rigtige position ved A (p … q)
  4. Når vi løber tør for elementer i enten L eller M, skal du samle de resterende elementer op og sætte A (p… q)

I kode ser det ud 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++; ) )

Flet () -funktion forklaret trin for trin

Der sker meget i denne funktion, så lad os tage et eksempel for at se, hvordan dette ville fungere.

Som sædvanligt taler et billede tusind ord.

Fletning af to på hinanden følgende underarrays af array

Arrayet A (0… 5) indeholder to sorterede underarrays A (0… 3) og A (4… 5). Lad os se, hvordan fletningsfunktionen fletter de to arrays.

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

Trin 1: Opret duplikatkopier af underarrays, der 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)
Opret kopier af underarrays til fletning

Trin 2: Oprethold det aktuelle indeks for underarrays og hovedarray

  int i, j, k; i = 0; j = 0; k = p;
Oprethold indekser for kopier af underarray og hovedarray

Trin 3: Indtil vi når slutningen af ​​enten L eller M, skal du vælge større blandt elementerne L og M og placere dem i den rigtige position 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 af individuelle elementer i sorterede underarrays, indtil vi når slutningen af ​​en

Trin 4: Når vi løber tør for elementer i enten L eller M, skal du samle de resterende elementer op og lægge 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 resterende elementer fra den første matrix til hovedundersamlingen 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Kopier de resterende elementer i det andet array til hovedundersamlingen

Dette trin ville have været nødvendigt, hvis størrelsen på M var større end L.

I slutningen af ​​flettefunktionen 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; )

Flet sorteringskompleksitet

Tidskompleksitet

Bedste sagskompleksitet: O (n * log n)

Kompleksitet i værste tilfælde: O (n * log n)

Gennemsnitlig sagskompleksitet: O (n * log n)

Rumkompleksitet

Rumkompleksiteten af ​​flettsortering er O (n).

Flet sorteringsapplikationer

  • Problem med inversionstælling
  • Ekstern sortering
  • E-handelsapplikationer

Interessante artikler...