Tri rapide en C

Tri rapide est un algorithme qui repose sur le principe Diviser pour Régner. Les étapes sont les suivantes:

1. Choisissez un élément du tableau, cet élément est appelé l’élément pivot.
2. Divisez le tableau non trié d’éléments en deux tableaux dont la valeur est inférieure au pivot et qui figurent dans le premier sous-tableau. Tous les éléments dont la valeur est supérieure au pivot figurent dans le deuxième sous-tableau (des valeurs égales peuvent aller dans les deux sens). Cette étape s’appelle l’opération de partition.
3. Répétez de manière récursive l’étape 2 (jusqu’à ce que les sous-tableaux soient triés).

 
La même logique que nous avons implémentée dans le programme C suivant.

#include <stdio.h>

void permuter(int *a, int *b) {
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void triRapid(int tab[], int first, int last) {
    int pivot, i, j;
    if(first < last) {
        pivot = first;
        i = first;
        j = last;
        while (i < j) {
            while(tab[i] <= tab[pivot] && i < last)
                i++;
            while(tab[j] > tab[pivot])
                j--;
            if(i < j) {
                permuter(&tab[i], &tab[j]);
            }
        }
        permuter(&tab[pivot], &tab[j]);
        triRapid(tab, first, j - 1);
        triRapid(tab, j + 1, last);
    }
}

int main() {
    int tab[100], nbr, i;
	
    printf("\n Entrer le nombre total d'éléments :  ");
    scanf("%d", &nbr);
    
    printf("\n Entrer les éléments du tableau  :  ");
    for(i = 0; i < nbr; i++)
        scanf("%d", &tab[i]);
    
    triRapid(tab, 0, nbr - 1);
    
    printf("\n Tableau trié : ");
    for(i = 0; i < nbr; i++)  {
        printf(" %4d", tab[i]);
    }
    printf("\n");
    return 0;
}

La sortie :