Algorithmes C/C++

Tri fusion

Le tri fusion trie récursivement les moitiés puis les rassemble.

Qu’est-ce que Tri fusion ?

Le tri fusion trie récursivement les moitiés puis les rassemble.

Utilisez diviser pour régner pour garantir O(n log n).

Points importants

Testez les entrées vides, uniques, dupliquées et déjà triées.
Séparez correction et optimisation.
Préférez la bibliothèque standard en production.

Visualisation de Tri fusion

O(n)

Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.

Exemples de code C et C++

Exécuter →

main.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]);
    }
}

Résultat attendu

2 3 6 7 8

C++

Exécuter →

main.cpp

#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 << ' ';
    }
}

Résultat attendu

2 3 6 7 8

Comparaison entre C et C++

Les deux versions utilisent O(n) de stockage auxiliaire ; C gère un buffer, C++ utilise vector et les algorithmes standards.

Boucles, pointeurs, tailles et buffers sont explicites.

C++

Itérateurs et algorithmes séparent opération et stockage.

Exercices pratiques

Exécutez les deux versions puis modifiez-les pour observer leurs garanties.

Tracez chaque comparaison.
Testez doublons et valeurs extrêmes.
Comparez aux algorithmes standards.