V tomto kurzu se dozvíte o sloučení. Najdete také pracovní příklady sloučení řazení C, C ++, Java a Python.
Sloučit řazení je jedním z nejpopulárnějších třídicích algoritmů založených na principu algoritmu Divide and Conquer.
Zde je problém rozdělen do několika dílčích problémů. Každý dílčí problém je řešen samostatně. Nakonec se dílčí problémy spojí a vytvoří konečné řešení.
Příklad sloučení řazení
Strategie Rozděl a panuj
Pomocí techniky Divide and Conquer rozdělíme problém na dílčí problémy. Když je řešení každého dílčího problému připraveno, spojíme výsledky dílčích problémů k vyřešení hlavního problému.
Předpokládejme, že jsme museli seřadit pole A. Podproblémem by bylo seřadit podsekci tohoto pole začínající na indexu p a končící na indexu r, označeném jako A (p… r).
Rozdělit
Pokud je q poloviční bod mezi p a r, pak můžeme rozdělit podpole A (p… r) na dvě pole A (p… q) a A (q + 1, r).
Dobýt
V kroku dobývání se pokusíme setřídit jak subarrays A (p… q), tak A (q + 1, r). Pokud jsme ještě nedosáhli základního případu, znovu rozdělíme obě tyto podskupiny a pokusíme se je seřadit.
Kombinovat
Když krok dobývání dosáhne základního kroku a dostaneme dva seřazené dílčí sady A (p… q) a A (q + 1, r) pro pole A (p… r), spojíme výsledky vytvořením tříděného pole A ( p… r) ze dvou tříděných podskupin A (p… q) a A (q + 1, r).
Algoritmus MergeSort
Funkce MergeSort opakovaně rozděluje pole na dvě poloviny, dokud se nedostaneme do stadia, kdy se pokusíme provést MergeSort na podoblasti velikosti 1, tj. P == r.
Poté vstoupí do hry funkce sloučení a kombinuje seřazená pole do větších polí, dokud nebude sloučeno celé pole.
MergeSort (A, p, r): pokud p> r návrat q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) sloučení (A, p, q, r )
Abychom roztřídili celé pole, musíme zavolat MergeSort(A, 0, length(A)-1).
Jak je znázorněno na obrázku níže, algoritmus sloučení řazení rekurzivně rozděluje pole na poloviny, dokud nedosáhneme základního případu pole s 1 prvkem. Poté funkce sloučení vyzvedne seřazená dílčí pole a sloučí je, aby postupně roztřídila celé pole.
Sloučit řazení v akci
Sloučení Krok merge sort
Každý rekurzivní algoritmus závisí na základním případě a schopnosti kombinovat výsledky základních případů. Sloučení se neliší. Nejdůležitější částí algoritmu třídění sloučení je, uhodli jste, krok sloučení.
Krok sloučení je řešením jednoduchého problému sloučení dvou seřazených seznamů (polí) a vytvoření jednoho velkého seřazeného seznamu (pole).
Algoritmus udržuje tři ukazatele, jeden pro každé ze dvou polí a jeden pro udržování aktuálního indexu konečného seřazeného pole.
Došli jsme na konec některého z polí? Ne: Porovnat aktuální prvky obou polí Zkopírovat menší prvek do seřazeného pole Přesunout ukazatel prvku obsahujícího menší prvek Ano: Zkopírovat všechny zbývající prvky neprázdného pole
Sloučit krok
Psaní kódu pro slučovací algoritmus
Znatelný rozdíl mezi krokem slučování, který jsme popsali výše, a krokem, který používáme pro sloučení, spočívá v tom, že funkci sloučení provádíme pouze na po sobě jdoucích dílčích polích.
Z tohoto důvodu potřebujeme pouze pole, první pozici, poslední index prvního dílčího pole (můžeme vypočítat první index druhého dílčího pole) a poslední index druhého dílčího pole.
Naším úkolem je sloučit dvě podoblasti A (p… q) a A (q + 1… r) a vytvořit tříděné pole A (p… r). Vstupy do funkce jsou tedy A, p, q a r
Funkce sloučení funguje následovně:
- Vytvořte kopie dílčích polí
L ← A(p… q)a M ← A (q + 1… r). - Vytvořte tři ukazatele i, j a k
- i udržuje aktuální index L, počínaje 1
- j udržuje aktuální index M, počínaje 1
- k udržuje aktuální index A (p… q) počínaje p.
- Dokud nedosáhneme konce L nebo M, vyberte větší z prvků z L a M a umístěte je do správné polohy na A (p… q)
- Když nám dojdou prvky v L nebo M, vyzvedneme zbývající prvky a vložíme A (p… q)
V kódu by to vypadalo 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++; ) )
Funkce sloučení () je vysvětlena krok za krokem
V této funkci se toho děje hodně, pojďme si tedy vzít příklad, jak to bude fungovat.
Jako obvykle obrázek promluví tisíc slov.
Sloučení dvou po sobě jdoucích dílčích polí pole
Pole A (0… 5) obsahuje dvě seřazená dílčí pole A (0… 3) a A (4… 5). Podívejme se, jak funkce sloučení sloučí dvě pole.
void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)
Krok 1: Vytvořte duplicitní kopie dílčích polí, které chcete třídit
// 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) 
Vytvářejte kopie dílčích polí ke sloučení
Krok 2: Udržujte aktuální index dílčích polí a hlavního pole
int i, j, k; i = 0; j = 0; k = p; 
Udržujte indexy kopií dílčího pole a hlavního pole
Krok 3: Dokud nedosáhneme konce L nebo M, vyberte větší mezi prvky L a M a umístěte je do správné 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áváme jednotlivé prvky seřazených podskupin, dokud nedojdeme na konec jednoho
Krok 4: Když nám dojdou prvky v L nebo M, vyzvedneme zbývající 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++; ) 
Zkopírujte zbývající prvky z prvního pole do hlavního dílčího pole
// We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) ) 
Zkopírujte zbývající prvky druhého pole do hlavního dílčího pole
Tento krok by byl nutný, pokud by velikost M byla větší než L.
Na konci funkce slučování se třídí podpole A (p… r).
Python, Java a C / C ++ příklady
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; )
Sloučit složitost řazení
Časová složitost
Složitost nejlepšího případu: O (n * log n)
Složitost nejhoršího případu: O (n * log n)
Průměrná složitost případu: O (n * log n)
Složitost vesmíru
Složitost prostoru sloučení je O (n).
Sloučit aplikace řazení
- Problém s počtem inverzí
- Externí třídění
- Aplikace elektronického obchodování
