Algorithme de tri par fusion - Implémentation en Java, C et Python
Le tri par fusion est l'un des algorithmes de tri les plus efficaces. Il fonctionne sur le principe de la Répartition et Conquête, basé sur l'idée de décomposer une liste en plusieurs sous-listes jusqu'à ce que chaque sous-liste ne contienne qu'un seul élément, puis de fusionner ces sous-listes de manière à obtenir une liste triée.
Règle de fonctionnement du tri par fusion
Le concept de Diviser pour régner comprend trois étapes :
- Divisez le problème en plusieurs sous-problèmes.
- Résoudre les sous-problèmes. L'idée est de décomposer le problème en sous-problèmes atomiques, où ils sont réellement résolus.
- Combinez les solutions des sous-problèmes pour trouver la solution du problème réel.
Ainsi, la règle de fonctionnement du tri par fusion implique les étapes suivantes :
- Divisez le tableau non trié en sous-tableaux, chacun contenant un seul élément.
- Prenez des paires adjacentes de deux tableaux à un seul élément et fusionnez-les pour former un tableau de 2 éléments.
- Répétez le processus jusqu'à ce qu'un seul tableau trié soit obtenu.
Un tableau de taille 'N' est divisé en deux parties de taille 'N/2'. Ensuite, ces tableaux sont encore divisés jusqu'à ce que nous atteignions un seul élément. Le cas de base ici est d'atteindre un unique élément. Lorsque le cas de base est atteint, nous commençons à fusionner la partie gauche et la partie droite pour obtenir un tableau trié à la fin. Le tri par fusion divise de manière répétée un tableau en plusieurs sous-tableaux jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément, puis fusionne ces sous-tableaux de manière à obtenir un tableau trié.
Flux de l'algorithme de tri par fusion
Tableau={70,50,30,10,20,40,60}
Nous décomposons à plusieurs reprises le tableau en deux parties, la partie gauche et la partie droite. La division se fait à partir de l'élément du milieu. Nous divisons jusqu'à atteindre un seul élément, puis nous commençons à les combiner pour former un tableau trié.
Implémentations du tri par fusion
Nous allons implémenter l'algorithme de tri par fusion en Java, C et Python.
1. Implémentation Java
package com.journaldev.ds;
public class MergeSort {
public static void main(String[] args) {
int[] arr = { 70, 50, 30, 10, 20, 40, 60 };
int[] merged = mergeSort(arr, 0, arr.length - 1);
for (int val : merged) {
System.out.print(val + " ");
}
}
public static int[] mergeTwoSortedArrays(int[] one, int[] two) {
int[] sorted = new int[one.length + two.length];
int i = 0;
int j = 0;
int k = 0;
while (i < one.length && j < two.length) {
if (one[i] < two[j]) {
sorted[k] = one[i];
k++;
i++;
} else {
sorted[k] = two[j];
k++;
j++;
}
}
if (i == one.length) {
while (j < two.length) {
sorted[k] = two[j];
k++;
j++;
}
}
if (j == two.length) {
while (i < one.length) {
sorted[k] = one[i];
k++;
i++;
}
}
return sorted;
}
public static int[] mergeSort(int[] arr, int lo, int hi) {
if (lo == hi) {
int[] br = new int[1];
br[0] = arr[lo];
return br;
}
int mid = (lo + hi) / 2;
int[] fh = mergeSort(arr, lo, mid);
int[] sh = mergeSort(arr, mid + 1, hi);
int[] merged = mergeTwoSortedArrays(fh, sh);
return merged;
}
}
SORTIE
2. Mise en œuvre en C
#include <stdio.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is the right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
/* Driver program to test above functions */
int main()
{
int arr[] = {70, 50, 30, 10, 20, 40,60};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
SORTIE
3. Mise en œuvre de Python
def merge_sort(unsorted_array):
if len(unsorted_array) > 1:
mid = len(unsorted_array) // 2 # Finding the mid of the array
left = unsorted_array[:mid] # Dividing the array elements
right = unsorted_array[mid:] # into 2 halves
merge_sort(left)
merge_sort(right)
i = j = k = 0
# data to temp arrays L[] and R[]
while i < len(left) and j < len(right):
if left[i] < right[j]:
unsorted_array[k] = left[i]
i += 1
else:
unsorted_array[k] = right[j]
j += 1
k += 1
# Checking if any element was left
while i < len(left):
unsorted_array[k] = left[i]
i += 1
k += 1
while j < len(right):
unsorted_array[k] = right[j]
j += 1
k += 1
Code to print the list
def print_list(array1):
for i in range(len(array1)):
print(array1[i], end=" ")
print()
driver code to test the above code
if __name__ == '__main__':
array = [12, 11, 13, 5, 6, 7]
print("Given array is", end="\n")
print_list(array)
merge_sort(array)
print("Sorted array is: ", end="\n")
print_list(array)
SORTIE
Complexité temporelle et spatiale du tri par fusion
1. Complexité spatiale
Espace auxiliaire : O(n) Tri sur place : Pas d'algorithme : Diviser et Conquérir
2. Complexité Temporelle
Le tri par fusion est un algorithme récursif et la complexité temporelle peut être exprimée par la relation de récurrence suivante. T(n)=2T(n/2) + O(n) La solution de la récurrence ci-dessus est O(nLogn). La liste de taille N est divisée en un maximum de Logn parties, et la fusion de toutes les sous-listes en une seule liste prend un temps O(N), le temps d'exécution dans le pire des cas de cet algorithme est O(nLogn) Complexité temporelle dans le meilleur des cas : O(n*log n) Complexité temporelle dans le pire des cas : O(n*log n) Complexité temporelle moyenne : O(n*log n) La complexité temporelle de MergeSort est O(n*Log n) dans les 3 cas (pire, moyenne et meilleur) car le tri par fusion divise toujours le tableau en deux moitiés et prend un temps linéaire pour fusionner deux moitiés. Lectures complémentaires :
- Page Wikipédia sur le tri par fusion
- Tri à bulles en Java
- Tri par insertion en Java