Le Tri Rapide (Quicksort)

Le tri rapide (ou quicksort) est un algorithme de tri efficace qui suit également la stratégie du "diviser pour régner". Son principe de base repose sur le choix d'un pivot et la partition des éléments du tableau autour de ce pivot. Le tri rapide est souvent utilisé en raison de sa rapidité, avec une complexité moyenne de O(n \log n).

Étapes du tri rapide :

• Choisir un pivot : On sélectionne un élément du tableau comme pivot. Ce pivot peut être le premier élément, le dernier, ou un élément au milieu.
• Partitionner : Réorganiser les éléments du tableau pour que tous les éléments plus petits que le pivot se retrouvent à gauche et ceux plus grands se retrouvent à droite.
• Récurse : Répéter l'opération sur les deux sous-tableaux (à gauche et à droite du pivot) jusqu'à ce que les sous-tableaux soient réduits à un seul élément.

#include <stdio.h>

// Fonction pour échanger deux éléments
void echanger(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Fonction de partition avec pivot au début
int partition_debut(int tab[], int deb, int fin) {
    int pivot = tab[deb];  // Le pivot est le premier élément
    int i = deb + 1;       // Indice de début des éléments > pivot
    int j = fin;           // Indice de fin des éléments < pivot

    while (i <= j) {
        while (i <= fin && tab[i] <= pivot) {
            i++;
        }
        while (j >= deb && tab[j] > pivot) {
            j--;
        }
        if (i < j) {
            echanger(&tab[i], &tab[j]);
        }
    }
    echanger(&tab[deb], &tab[j]);  // Placer le pivot à sa position correcte
    return j;  // Retourner l'indice du pivot
}

// Fonction récursive de tri rapide
void tri_rapide_debut(int tab[], int deb, int fin) {
    if (deb < fin) {
        int pivot = partition_debut(tab, deb, fin);
        tri_rapide_debut(tab, deb, pivot - 1);
        tri_rapide_debut(tab, pivot + 1, fin);
    }
}

// Fonction principale
int main() {
    int tab[] = {38, 27, 43, 3, 9, 82, 10};
    int taille = sizeof(tab) / sizeof(tab[0]);

    printf("Tableau avant tri :\n");
    for (int i = 0; i < taille; i++) {
        printf("%d ", tab[i]);
    }
    printf("\n");

    tri_rapide_debut(tab, 0, taille - 1);

    printf("Tableau après tri :\n");
    for (int i = 0; i < taille; i++) {
        printf("%d ", tab[i]);
    }
    printf("\n");

    return 0;
}
            

#include <stdio.h>

// Fonction pour échanger deux éléments
void echanger(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Fonction de partition avec pivot au milieu
int partition_milieu(int tab[], int deb, int fin) {
    int mil = deb + (fin - deb) / 2;
    int pivot = tab[mil];  // Le pivot est au milieu
    echanger(&tab[mil], &tab[deb]);  // Mettre le pivot au début

    int i = deb + 1;
    int j = fin;

    while (i <= j) {
        while (i <= fin && tab[i] <= pivot) {
            i++;
        }
        while (j >= deb && tab[j] > pivot) {
            j--;
        }
        if (i < j) {
            echanger(&tab[i], &tab[j]);
        }
    }
    echanger(&tab[deb], &tab[j]);  // Placer le pivot correctement
    return j;
}

void tri_rapide_milieu(int tab[], int deb, int fin) {
    if (deb < fin) {
        int pivot = partition_milieu(tab, deb, fin);
        tri_rapide_milieu(tab, deb, pivot - 1);
        tri_rapide_milieu(tab, pivot + 1, fin);
    }
}
            

#include <stdio.h>

void echanger(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Fonction de partition avec pivot à la fin
int partition_fin(int tab[], int deb, int fin) {
    int pivot = tab[fin];
    int i = deb - 1;

    for (int j = deb; j < fin; j++) {
        if (tab[j] <= pivot) {
            i++;
            echanger(&tab[i], &tab[j]);
        }
    }
    echanger(&tab[i + 1], &tab[fin]);
    return i + 1;
}

void tri_rapide_fin(int tab[], int deb, int fin) {
    if (deb < fin) {
        int pivot = partition_fin(tab, deb, fin);
        tri_rapide_fin(tab, deb, pivot - 1);
        tri_rapide_fin(tab, pivot + 1, fin);
    }
}
            

Comparaison des Pivots

• Pivot au début : Le tri peut être déséquilibré si les éléments du tableau sont déjà partiellement triés.
• Pivot au milieu : C’est un bon compromis pour équilibrer les sous-tableaux.
• Pivot à la fin : Similaire au pivot au début, mais peut être efficace dans certains contextes comme les tableaux triés à l'envers.

Conclusion

Le tri rapide est un algorithme très performant avec une complexité moyenne de O(n \log n), mais dans le pire des cas (tableaux déjà triés dans un certain ordre), il peut avoir une complexité de O(n^2).