Une introduction à l'algorithme de tri par fusion

Le tri par fusion est un algorithme de tri basé sur la technique du « diviser pour régner ». C'est l'un des algorithmes de tri les plus efficaces.

Dans cet article, vous découvrirez le fonctionnement de l'algorithme de tri par fusion, l'algorithme du tri par fusion, ses complexité temporelle et spatiale, et sa mise en œuvre dans divers langages de programmation tels que C++, Python et JavaScript.

Comment fonctionne l'algorithme de tri par fusion ?

Le tri par fusion fonctionne sur le principe du diviser pour régner. Le tri par fusion divise à plusieurs reprises un tableau en deux sous-tableaux égaux jusqu'à ce que chaque sous-tableau se compose d'un seul élément. Enfin, tous ces sous-tableaux sont fusionnés de telle sorte que le tableau résultant soit trié.

Ce concept peut être expliqué plus efficacement à l'aide d'un exemple. Considérons un tableau non trié avec les éléments suivants: {16, 12, 15, 13, 19, 17, 11, 18}.

Ici, l'algorithme de tri par fusion divise le tableau en deux moitiés, s'appelle lui-même pour les deux moitiés, puis fusionne les deux moitiés triées.

Algorithme de tri de fusion

Ci-dessous l'algorithme du tri par fusion:

MergeSort (arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
revenir
autre
Trouvez l'indice du milieu qui divise le tableau en deux moitiés: 
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Appelez mergeSort() pour la première moitié: 
Appelez mergeSort (arr, leftIndex, middleIndex)
Appelez mergeSort() pour la seconde moitié :
Appelez mergeSort (arr, middleIndex+1, rightIndex)
Fusionnez les deux moitiés triées aux étapes 2 et 3 :
Fusion d'appels (arr, leftIndex, middleIndex, rightIndex)

En rapport: Qu'est-ce que la récursivité et comment l'utilisez-vous ?

Complexité temporelle et spatiale de l'algorithme de tri par fusion

L'algorithme de tri par fusion peut être exprimé sous la forme de la relation de récurrence suivante:

T(n) = 2T(n/2) + O(n)

Après avoir résolu cette relation de récurrence à l'aide du théorème du maître ou de la méthode de l'arbre de récurrence, vous obtiendrez la solution sous la forme O(n logn). Ainsi, la complexité temporelle de l'algorithme de tri par fusion est O(n connexion).

La complexité temporelle dans le meilleur des cas du tri par fusion : O(n connexion)

La complexité temporelle moyenne du tri par fusion : O(n connexion)

La complexité temporelle dans le pire des cas du tri par fusion : O(n connexion)

En rapport: Qu'est-ce que la notation Big-O ?

La complexité de l'espace auxiliaire de l'algorithme de tri par fusion est Au) comme m un espace auxiliaire est requis dans l'implémentation du tri par fusion.

Implémentation en C++ de l'algorithme de tri par fusion

Vous trouverez ci-dessous l'implémentation C++ de l'algorithme de tri par fusion:

// Implémentation en C++ du
// fusionner l'algorithme de tri
#inclure 
en utilisant l'espace de noms std ;
// Cette fonction fusionne deux sous-tableaux de arr[]
// Sous-tableau gauche: arr[leftIndex..middleIndex]
// Sous-tableau droit: arr[middleIndex+1..rightIndex]
void merge (int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Créer des tableaux temporaires
int L[leftSubarraySize], R[rightSubarraySize] ;
// Copie des données dans les tableaux temporaires L[] et R[]
pour (entier i = 0; i < leftSubarraySize; i++)
L[i] = arr[leftIndex + i] ;
pour (int j = 0; j < rightSubarraySize; j++)
R[j] = arr[Indexmoyen + 1 + j] ;
// Fusionner les tableaux temporaires dans arr[leftIndex..rightIndex]
// Index initial du sous-tableau gauche
entier je = 0;
// Index initial du sous-tableau droit
entier j = 0;
// Index initial du sous-tableau fusionné
int k = leftIndex;
while (i < leftSubarraySize && j < rightSubarraySize)
{
si (L[i] <= R[j])
{
arr[k] = L[i];
je++ ;
}
autre
{
arr[k] = R[j];
j++;
}
k++ ;
}
// S'il reste des éléments dans L[]
// Copier dans arr[]
while (i < leftSubarraySize)
{
arr[k] = L[i];
je++ ;
k++ ;
}
// S'il reste des éléments dans R[]
// Copier dans arr[]
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++ ;
}
}
void mergeSort (int arr[], int leftIndex, int rightIndex)
{
if (leftIndex >= rightIndex)
{
revenir;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2 ;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex+1, rightIndex);
fusionner (arr, leftIndex, middleIndex, rightIndex);
}
// Fonction pour imprimer les éléments
// du tableau
void printArray (int arr[], int size)
{
pour (entier i = 0; je < taille; i++)
{
cout << arr[i] << " " ;
}
cout << endl;
}
// Code du pilote
int main()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 } ;
int size = sizeof (arr) / sizeof (arr[0]);
cout << "Tableau non trié :" << endl ;
printArray (arr, taille);
mergeSort (arr, 0, taille - 1);
cout << "Tableau trié :" << endl ;
printArray (arr, taille);
renvoie 0 ;
}

Production:

Tableau non trié :
16 12 15 13 19 17 11 18 
Tableau trié :
11 12 13 15 16 17 18 19

Implémentation JavaScript de l'algorithme de tri par fusion

Vous trouverez ci-dessous l'implémentation JavaScript de l'algorithme de tri par fusion:

// Implémentation JavaScript du
// fusionner l'algorithme de tri
// Cette fonction fusionne deux sous-tableaux de arr[]
// Sous-tableau gauche: arr[leftIndex..middleIndex]
// Sous-tableau droit: arr[middleIndex+1..rightIndex]
fusion de fonction (arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Créer des tableaux temporaires
var L = new Array (leftSubarraySize);
var R = nouveau tableau (rightSubarraySize);
// Copie des données dans les tableaux temporaires L[] et R[]
pour (soit i = 0; jeL[i] = arr[leftIndex + i] ;
}
pour (soit j = 0; jR[j] = arr[Indexmoyen + 1 + j] ;
}
// Fusionner les tableaux temporaires dans arr[leftIndex..rightIndex]
// Index initial du sous-tableau gauche
var i = 0 ;
// Index initial du sous-tableau droit
varj = 0 ;
// Index initial du sous-tableau fusionné
var k = indexgauche;
while (i < leftSubarraySize && j < rightSubarraySize)
{
si (L[i] <= R[j])
{
arr[k] = L[i];
je++ ;
}
autre
{
arr[k] = R[j];
j++;
}
k++ ;
}
// S'il reste des éléments dans L[]
// Copier dans arr[]
while (i < leftSubarraySize)
{
arr[k] = L[i];
je++ ;
k++ ;
}
// S'il reste des éléments dans R[]
// Copier dans arr[]
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++ ;
}
}
function mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex >= rightIndex) {
revenir
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex+1, rightIndex);
fusionner (arr, leftIndex, middleIndex, rightIndex);
}
// Fonction pour imprimer les éléments
// du tableau
function tableau_impression (tableau, taille) {
pour (soit i = 0; jedocument.write (arr[i] + " ");
}
document.write("
");
}
// Code du pilote :
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var taille = arr.longueur;
document.write("Tableau non trié :
");
printArray (arr, taille);
mergeSort (arr, 0, taille - 1);
document.write("Tableau trié :
");
printArray (arr, taille);

Production:

Tableau non trié :
16 12 15 13 19 17 11 18
Tableau trié :
11 12 13 15 16 17 18 19

En rapport: Programmation dynamique: exemples, problèmes courants et solutions

Implémentation Python de l'algorithme de tri par fusion

Vous trouverez ci-dessous l'implémentation Python de l'algorithme de tri par fusion:

# Implémentation Python du
# algorithme de tri par fusion
def mergeSort (arr):
si longueur (arr) > 1 :
# Trouver l'index du milieu du tableau
middleIndex = len (arr)//2
# Moitié gauche du tableau
L = arr[:middleIndex]
# Moitié droite du tableau
R = arr[Indexmoyen:]
# Tri de la première moitié du tableau
mergeTrier (L)
# Tri de la seconde moitié du tableau
mergeTrier (R)
# Index initial du sous-tableau gauche
je = 0
# Index initial du sous-tableau droit
j = 0
# Index initial du sous-tableau fusionné
k = 0
# Copier les données dans les tableaux temporaires L[] et R[]
tandis que i < len (L) et j < len (R) :
si L[i] < R[j] :
arr[k] = L[i]
je = je + 1
autre:
arr[k] = R[j]
j = j + 1
k = k + 1
# Vérifier s'il reste des éléments
tandis que i < len (L):
arr[k] = L[i]
je = je + 1
k = k + 1
tandis que j < len (R):
arr[k] = R[j]
j = j + 1
k = k + 1
# Fonction pour imprimer les éléments
# du tableau
def printArray (arr, taille):
pour i dans la plage (taille):
print (arr[i], end=" ")
imprimer()
# Code du pilote
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
taille = len (arr)
print("Tableau non trié :")
printArray (arr, taille)
mergeSort (arr)
print("Tableau trié :")
printArray (arr, taille)

Production:

Tableau non trié :
16 12 15 13 19 17 11 18
Tableau trié :
11 12 13 15 16 17 18 19

Comprendre d'autres algorithmes de tri

Le tri est l'un des algorithmes les plus utilisés en programmation. Vous pouvez trier des éléments dans différents langages de programmation à l'aide de divers algorithmes de tri tels que le tri rapide, le tri à bulles, le tri par fusion, le tri par insertion, etc.

Le tri à bulles est le meilleur choix si vous souhaitez en savoir plus sur l'algorithme de tri le plus simple.

Une introduction à l'algorithme de tri à bulles

L'algorithme Bubble Sort: une excellente introduction au tri des tableaux.

Lire la suite

A propos de l'auteur