Zlúčiť algoritmus zoradenia

V tomto tutoriáli sa dozviete o zlúčení. Nájdete tiež pracovné príklady zlúčenia, triedenia C, C ++, Java a Python.

Zlúčiť zoradenie je jedným z najpopulárnejších triediacich algoritmov, ktorý je založený na princípe algoritmu Divide and Conquer.

Tu je problém rozdelený na niekoľko čiastkových problémov. Každý čiastkový problém je riešený individuálne. Nakoniec sa čiastkové problémy spoja a vytvoria konečné riešenie.

Zlúčiť príklad zoradenia

Stratégia Rozdeľuj a panuj

Pomocou techniky Divide and Conquer rozdelíme problém na podproblémy. Keď je riešenie každého čiastkového problému pripravené, spojením výsledkov z čiastkových problémov vyriešime hlavný problém.

Predpokladajme, že sme museli zoradiť pole A. Podproblémom by bolo triediť podsekciu tohto poľa začínajúcu na indexe p a končiac na indexe r, označenom ako A (p … r).

Rozdeliť
Ak je q polovičný bod medzi p a r, potom môžeme rozdeliť podskupinu A (p … r) na dve polia A (p … q) a A (q + 1, r).

Dobyť
V kroku Dobyť sa pokúsime zoradiť obidva podoblasti A (p… q) a A (q + 1, r). Ak sme sa ešte nedostali k základnému prípadu, znova rozdelíme obidva tieto podskupiny a pokúsime sa ich zoradiť.

Kombinovať
Keď krok dobyvania dosiahne základný krok a dostaneme dve zoradené podradené polia A (p… q) a A (q + 1, r) pre pole A (p… r), spojíme výsledky vytvorením zoradeného poľa A ( p… r) z dvoch triedených podskupín A (p… q) a A (q + 1, r).

Algoritmus MergeSort

Funkcia MergeSort opakovane rozdeľuje pole na dve polovice, až kým sa nedostaneme do fázy, keď sa pokúsime vykonať MergeSort na podskupine veľkosti 1, tj. P == r.

Potom vstúpi do hry funkcia zlúčenia a kombinuje zoradené polia do väčších polí, až kým sa celé pole nespojí.

 MergeSort (A, p, r): ak p> r návrat q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) zlúčenie (A, p, q, r )

Aby sme zoradili celé pole, musíme zavolať MergeSort(A, 0, length(A)-1).

Ako je znázornené na obrázku nižšie, algoritmus triedenia zlúčenia rekurzívne rozdelí pole na polovice, kým nedosiahneme základný prípad poľa s 1 prvkom. Potom funkcia zlúčenia vyzdvihne zoradené podradené polia a zlúči ich, aby postupne zoradila celé pole.

Zlúčiť zoradenie v akcii

Zlúčenie Krok triedenie zlučovaním

Každý rekurzívny algoritmus závisí od základného prípadu a schopnosti kombinovať výsledky základných prípadov. Zlučovanie sa nelíši. Najdôležitejšou časťou algoritmu zlučovania je krok zlúčenia, uhádli ste.

Krok zlúčenia je riešením jednoduchého problému spojenia dvoch zoradených zoznamov (polí) a vytvorenia jedného veľkého triedeného zoznamu (poľa).

Algoritmus udržiava tri ukazovatele, jeden pre každé z dvoch polí a jeden pre udržiavanie aktuálneho indexu konečného zoradeného poľa.

Dostali sme sa na koniec niektorého z polí? Nie: Porovnať súčasné prvky oboch polí Kopírovať menší prvok do zoradeného poľa Presunúť ukazovateľ prvku obsahujúceho menší prvok Áno: Skopírovať všetky zostávajúce prvky neprázdneho poľa
Zlúčiť krok

Písanie kódu pre zlučovací algoritmus

Znateľný rozdiel medzi krokom zlúčenia, ktorý sme opísali vyššie, a tým, ktorý používame na triedenie zlúčenia, spočíva v tom, že funkciu zlúčenia vykonávame iba na po sebe idúcich čiastkových poliach.

Preto potrebujeme iba pole, prvú pozíciu, posledný index prvého podradeného poľa (môžeme vypočítať prvý index druhého podradeného poľa) a posledný index druhého podradeného poľa.

Našou úlohou je zlúčiť dve podradené polia A (p… q) a A (q + 1… r) a vytvoriť zoradené pole A (p… r). Takže vstupy do funkcie sú A, p, q a r

Funkcia zlúčenia funguje nasledovne:

  1. Vytvorte kópie podradených polí L ← A(p… q)a M ← A (q + 1 … r).
  2. Vytvorte tri ukazovatele i, j a k
    1. udržiavam aktuálny index L začínajúci na 1
    2. j udržuje aktuálny index M začínajúci na 1
    3. k udržuje aktuálny index A (p… q), počnúc p.
  3. Kým nedosiahneme koniec buď L, alebo M, vyberte ten väčší z prvkov z L a M a umiestnite ich do správnej polohy na A (p… q)
  4. Keď nám dôjdu prvky v L alebo M, zoberieme zvyšné prvky a vložíme A (p … q)

V kóde by to vyzeralo takto:

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

Funkcia zlúčenia () je vysvetlená krok za krokom

V tejto funkcii sa toho deje veľa, takže si zoberme príklad, ako by to fungovalo.

Ako obvykle, obrázok povie tisíc slov.

Zlúčenie dvoch po sebe idúcich podskupín poľa

Pole A (0… 5) obsahuje dva zoradené podskupiny A (0… 3) a A (4… 5). Pozrime sa, ako funkcia zlúčenia zlúči dve polia.

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

Krok 1: Vytvorte duplicitné kópie podradených polí, ktoré chcete zoradiť

  // 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)
Vytvorte kópie podradených polí na zlúčenie

Krok 2: Udržujte aktuálny index podradených polí a hlavného poľa

  int i, j, k; i = 0; j = 0; k = p;
Udržiavajte indexy kópií čiastkového poľa a hlavného poľa

Krok 3: Kým nedosiahneme koniec buď L alebo M, vyberte väčší medzi prvkami L a M a umiestnite ich do správnej polohy na 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++; )
Porovnávanie jednotlivých prvkov zoradených podskupín, kým sa nedostaneme na koniec jedného

Krok 4: Keď nám dôjdu prvky v buď L alebo M, zoberieme zvyšné prvky a vložíme A (p … r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Skopírujte zostávajúce prvky z prvého poľa do hlavného podradeného poľa 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Skopírujte zostávajúce prvky druhého poľa do hlavného podradeného poľa

Tento krok by bol potrebný, ak by veľkosť M bola väčšia ako L.

Na konci funkcie zlúčenia sa čiastkové pole A (p … r) zoradí.

Príklady jazyka Python, Java a 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; )

Zlúčiť zložitosť zoradenia

Časová zložitosť

Najlepšia zložitosť prípadu: O (n * log n)

Najhoršia zložitosť prípadu: O (n * log n)

Priemerná zložitosť prípadu: O (n * log n)

Zložitosť vesmíru

Priestorová zložitosť zlúčenia je O (n).

Zlúčiť aplikácie na zoradenie

  • Problém s počtom inverzií
  • Externé triedenie
  • Aplikácie elektronického obchodu

Zaujímavé články...