CodeUtility
Faciliter la vie des développeurs !
Algorithmes C/C++

Le tri rapide (quick sort) en C et C++

Dans cette leçon, vous allez implémenter le tri rapide en partitionnant le tableau autour d'un élément pivot.

Introduction

Le tri rapide choisit un élément comme pivot, puis réorganise le tableau pour que les éléments plus petits que le pivot soient à sa gauche et les autres à sa droite. Le pivot se trouve alors à sa place définitive, et l'algorithme trie ensuite les deux côtés par récursivité.

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 rapide (quick sort) en C et C++

O(n log n)

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

Exemples de code C et C++

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 de l’exécution
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 de l’exécution
3 4 5 7 9 10

Comparaison entre C et C++

La fonction partition en C choisit le dernier élément comme pivot et utilise la variable boundary pour marquer la limite de la zone des éléments plus petits. À la fin, le pivot est échangé à la position boundary. La version C++ utilise std::partition pour exprimer le partitionnement plus brièvement. La complexité moyenne est O(n log n), mais un pivot mal choisi peut la faire monter à O(n²).

C

Les boucles, les pointeurs, les longueurs et les tampons temporaires sont écrits explicitement.

C++

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