Édition pédagogique en français

Tri rapide en C

Comprenez le pivot, le partitionnement et les cas défavorables du tri rapide.

Quicksort choisit un pivot et sépare les valeurs plus petites des plus grandes, puis trie récursivement chaque partie. Dans le partitionnement de Lomuto de cet exemple, le dernier élément sert de pivot et un indice marque la région déjà traitée.

La récursion s’arrête lorsqu’un intervalle contient moins de deux éléments. Le temps moyen est O(N log N), mais des partitions très déséquilibrées peuvent conduire à O(N²). Comptez aussi la pile des appels, même sans second tableau.

Testez doublons, tableau déjà trié et ordre inverse. Vérifiez les bornes de chaque appel. Cette version ne garantit pas le maintien de l’ordre initial des éléments égaux.

Code source

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array:\n");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Ouvrir dans le compilateur

Résultat attendu

Sorted array:
10 30 40 50 70 80 90

Questions fréquentes

Pourquoi le code et certains résultats restent-ils en anglais ?

Les mots-clés C, les identifiants, les commentaires du programme et les sorties attendues restent ceux de la version originale pour conserver un code exécutable et des tests cohérents. Les explications et les consignes sont traduites.