Le tri fusion (merge sort) en C et C++
Dans cette leçon, vous allez implémenter le tri fusion selon la stratégie diviser pour régner, qui s'exécute toujours en O(n log n).
Introduction
Le tri fusion coupe le tableau en deux moitiés, trie chacune par un appel récursif, puis fusionne les deux moitiés triées en une suite ordonnée. Son grand avantage est un temps d'exécution toujours stable en O(n log n), quel que soit l'état des données d'entrée.
Points importants
- Testez avec une entrée vide, un seul élément, des doublons et des données déjà triées.
- Rendez d'abord le code correct, optimisez ensuite.
- Dans du vrai code, préférez les fonctions toutes prêtes de la bibliothèque standard.
Visualisation de Le tri fusion (merge sort) en C et C++
O(n)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Exemples de code C et C++
#include <stdio.h>
#include <stdlib.h>
void merge_sort(int *values, int *temporary, int left, int right) {
if (right - left < 2) return;
int middle = (left + right) / 2;
merge_sort(values, temporary, left, middle);
merge_sort(values, temporary, middle, right);
int first = left;
int second = middle;
int output = left;
while (first < middle && second < right) {
temporary[output++] = values[first] < values[second]
? values[first++] : values[second++];
}
while (first < middle) temporary[output++] = values[first++];
while (second < right) temporary[output++] = values[second++];
for (int index = left; index < right; ++index) {
values[index] = temporary[index];
}
}
int main(void) {
int values[] = {8, 3, 6, 2, 7};
int temporary[5];
merge_sort(values, temporary, 0, 5);
for (int index = 0; index < 5; ++index) {
printf("%d ", values[index]);
}
}
2 3 6 7 8#include <algorithm>
#include <iostream>
#include <vector>
void merge_sort(std::vector<int>& values) {
if (values.size() < 2) return;
auto middle = values.begin() + values.size() / 2;
std::vector<int> left(values.begin(), middle);
std::vector<int> right(middle, values.end());
merge_sort(left);
merge_sort(right);
std::merge(left.begin(), left.end(), right.begin(), right.end(),
values.begin());
}
int main() {
std::vector values{8, 3, 6, 2, 7};
merge_sort(values);
for (int value : values) {
std::cout << value << ' ';
}
}
2 3 6 7 8Comparaison entre C et C++
La fonction merge_sort en C s'arrête quand la portion contient moins de 2 éléments. Après le tri des deux moitiés, la boucle while choisit à chaque fois le plus petit des deux éléments de tête et le copie dans le tableau temporaire temporary, puis copie ce qui reste. Les deux versions ont besoin de O(n) mémoire supplémentaire. La version C gère elle-même le tableau temporaire, la version C++ utilise vector et les algorithmes standard pour un code plus clair.
Les boucles, les pointeurs, les longueurs et les tampons temporaires sont écrits explicitement.
Les itérateurs et les algorithmes standard séparent le traitement de la façon dont les données sont stockées.
Exercices d'approfondissement
Exécutez les deux versions, puis modifiez le code pour observer la différence de sécurité qu'apporte chaque langage.
- Déroulez chaque comparaison sur papier.
- Testez avec des doublons et des valeurs très grandes et très petites.
- Mesurez le temps d'exécution de votre code et comparez-le à la bibliothèque standard.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
Tous les défis