Dans ce didacticiel, vous découvrirez le tri par fusion. Vous trouverez également des exemples fonctionnels de tri de fusion C, C ++, Java et Python.
Merge Sort est l'un des algorithmes de tri les plus populaires basé sur le principe de l'algorithme Divide and Conquer.
Ici, un problème est divisé en plusieurs sous-problèmes. Chaque sous-problème est résolu individuellement. Enfin, les sous-problèmes sont combinés pour former la solution finale.
Exemple de tri par fusion
Stratégie Divide and Conquer
En utilisant la technique Divide and Conquer , nous divisons un problème en sous-problèmes. Lorsque la solution à chaque sous-problème est prête, nous «combinons» les résultats des sous-problèmes pour résoudre le problème principal.
Supposons que nous devions trier un tableau A. Un sous-problème serait de trier une sous-section de ce tableau commençant à l'index p et se terminant à l'index r, noté A (p… r).
Diviser
Si q est le point à mi-chemin entre p et r, alors nous pouvons diviser le sous-tableau A (p… r) en deux tableaux A (p… q) et A (q + 1, r).
Conquérir
Dans l'étape de conquête, nous essayons de trier à la fois les sous-tableaux A (p… q) et A (q + 1, r). Si nous n'avons pas encore atteint le cas de base, nous divisons à nouveau ces deux sous-tableaux et essayons de les trier.
Combiner
Lorsque l'étape de conquête atteint l'étape de base et que nous obtenons deux sous-tableaux triés A (p… q) et A (q + 1, r) pour le tableau A (p… r), nous combinons les résultats en créant un tableau trié A ( p… r) à partir de deux sous-tableaux triés A (p… q) et A (q + 1, r).
L'algorithme MergeSort
La fonction MergeSort divise à plusieurs reprises le tableau en deux moitiés jusqu'à ce que nous atteignions un stade où nous essayons d'effectuer MergeSort sur un sous-tableau de taille 1, c'est-à-dire p == r.
Après cela, la fonction de fusion entre en jeu et combine les tableaux triés dans des tableaux plus grands jusqu'à ce que tout le tableau soit fusionné.
MergeSort (A, p, r): si p> r retourne q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) merge (A, p, q, r )
Pour trier un tableau entier, nous devons appeler MergeSort(A, 0, length(A)-1).
Comme le montre l'image ci-dessous, l'algorithme de tri par fusion divise récursivement le tableau en deux jusqu'à ce que nous atteignions le cas de base du tableau avec 1 élément. Après cela, la fonction de fusion récupère les sous-tableaux triés et les fusionne pour trier progressivement l'ensemble du tableau.
Fusionner le tri en action
La fusion étape de tri par fusion
Chaque algorithme récursif dépend d'un cas de base et de la possibilité de combiner les résultats des cas de base. Le tri par fusion n'est pas différent. La partie la plus importante de l'algorithme de tri par fusion est, vous l'avez deviné, l'étape de fusion.
L'étape de fusion est la solution au problème simple de la fusion de deux listes triées (tableaux) pour créer une grande liste triée (tableau).
L'algorithme gère trois pointeurs, un pour chacun des deux tableaux et un pour maintenir l'index actuel du tableau trié final.
Avons-nous atteint la fin de l'un des tableaux? Non: comparer les éléments actuels des deux tableaux Copier le plus petit élément dans le tableau trié Déplacer le pointeur de l'élément contenant le plus petit élément Oui: copier tous les éléments restants du tableau non vide
Étape de fusion
Écriture du code pour l'algorithme de fusion
Une différence notable entre l'étape de fusion décrite ci-dessus et celle que nous utilisons pour le tri par fusion est que nous n'exécutons la fonction de fusion que sur des sous-tableaux consécutifs.
C'est pourquoi nous n'avons besoin que du tableau, de la première position, du dernier index du premier sous-tableau (nous pouvons calculer le premier index du deuxième sous-tableau) et du dernier index du deuxième sous-tableau.
Notre tâche est de fusionner deux sous-tableaux A (p… q) et A (q + 1… r) pour créer un tableau trié A (p… r). Donc les entrées de la fonction sont A, p, q et r
La fonction de fusion fonctionne comme suit:
- Créez des copies des sous-tableaux
L ← A(p… q)et M ← A (q + 1… r). - Créer trois pointeurs i, j et k
- i maintient l'indice actuel de L, à partir de 1
- j maintient l'indice actuel de M, à partir de 1
- k maintient l'indice actuel de A (p… q), commençant à p.
- Jusqu'à ce que nous atteignions la fin de L ou M, choisissez le plus grand parmi les éléments de L et M et placez-les dans la bonne position en A (p… q)
- Lorsque nous manquons d'éléments dans L ou M, ramassez les éléments restants et mettez A (p… q)
Dans le code, cela ressemblerait à:
// 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++; ) )
Fonction Merge () expliquée étape par étape
Beaucoup de choses se passent dans cette fonction, alors prenons un exemple pour voir comment cela fonctionnerait.
Comme d'habitude, une image vaut mille mots.
Fusion de deux sous-tableaux consécutifs de tableau
Le tableau A (0… 5) contient deux sous-tableaux triés A (0… 3) et A (4… 5). Voyons comment la fonction de fusion fusionnera les deux tableaux.
void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)
Étape 1: Créez des copies en double des sous-tableaux à trier
// 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) 
Créer des copies de sous-tableaux pour la fusion
Étape 2: conserver l'index actuel des sous-tableaux et du tableau principal
int i, j, k; i = 0; j = 0; k = p; 
Maintenir les index des copies du sous-tableau et du tableau principal
Étape 3: Jusqu'à ce que nous atteignions la fin de L ou M, choisissez le plus grand parmi les éléments L et M et placez-les dans la bonne position en 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++; ) 
Comparaison d'éléments individuels de sous-tableaux triés jusqu'à ce que nous atteignions la fin d'un
Étape 4: Lorsque nous manquons d'éléments dans L ou M, ramassez les éléments restants et mettez A (p… r)
// We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; ) 
Copiez les éléments restants du premier tableau dans le sous-tableau principal
// We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) ) 
Copier les éléments restants du deuxième tableau dans le sous-tableau principal
Cette étape aurait été nécessaire si la taille de M était supérieure à L.
A la fin de la fonction de fusion, le sous-tableau A (p… r) est trié.
Exemples Python, Java et 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; )
Fusionner la complexité du tri
Complexité temporelle
Meilleure complexité des cas: O (n * log n)
Pire complexité des cas: O (n * log n)
Complexité moyenne des cas: O (n * log n)
Complexité spatiale
La complexité spatiale du tri par fusion est O (n).
Fusionner les applications de tri
- Problème de compte d'inversion
- Tri externe
- Applications de commerce électronique
