Algorithmes C/C++

Tri rapide

Quick sort place le pivot définitivement puis trie les deux partitions.

Qu’est-ce que Tri rapide ?

Quick sort place le pivot définitivement puis trie les deux partitions.

Partitionnez les valeurs autour d’un pivot.

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 rapide

O(n log 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>

void swap(int *left, int *right) {
    int temporary = *left;
    *left = *right;
    *right = temporary;
}

int partition(int *values, int low, int high) {
    int pivot = values[high];
    int boundary = low;
    for (int scan = low; scan < high; ++scan) {
        if (values[scan] < pivot) {
            swap(&values[boundary++], &values[scan]);
        }
    }
    swap(&values[boundary], &values[high]);
    return boundary;
}

void quick_sort(int *values, int low, int high) {
    if (low >= high) return;
    int pivot = partition(values, low, high);
    quick_sort(values, low, pivot - 1);
    quick_sort(values, pivot + 1, high);
}

int main(void) {
    int values[] = {9, 4, 7, 3, 10, 5};
    quick_sort(values, 0, 5);
    for (int index = 0; index < 6; ++index) {
        printf("%d ", values[index]);
    }
}

Résultat attendu

3 4 5 7 9 10

C++

Exécuter →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
    if (last - first < 2) return;
    auto pivot = *(last - 1);
    auto middle = std::partition(first, last - 1,
        [pivot](int value) { return value < pivot; });
    std::iter_swap(middle, last - 1);
    quick_sort(first, middle);
    quick_sort(middle + 1, last);
}

int main() {
    std::vector values{9, 4, 7, 3, 10, 5};
    quick_sort(values.begin(), values.end());
    for (int value : values) {
        std::cout << value << ' ';
    }
}

Résultat attendu

3 4 5 7 9 10

Comparaison entre C et C++

O(n log n) en moyenne, O(n²) avec de mauvais pivots. C++ exprime la partition avec std::partition.

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.