Prog-Info > C++ > Tri et Recherche > Tri rapide.

---

Le tri rapide

Le principe de cet algorithme est de diviser un ensemble d'éléments en deux parties. Pour faire cette séparation, une valeur pivot est choisie. Les valeurs sont séparées par le pivot suivant qu'elles lui soit supérieures ou inférieures. Ensuite, on fait la même chose pour les deux sous ensembles. Cet algorithme est donc récursif.
Le choix du pivot est un problème majeur, le mieux serait de pouvoir séparer les ensembles en deux parties égales. Toutefois une recherche s'avererait trop coûteuse. C'est pour cela qu'on choisit le premier élément ou le dernier élément.

int partition(int tableau[], const int debut, const int fin) {    int compteur = debut;    int pivot = tableau[debut];    int i;    for(i=debut+1; i<=fin; i++)    {       if(tableau[i]<pivot) // si élément inférieur au pivot       {          compteur++; // incrémente compteur cad la place finale du pivot          echanger(tableau, compteur, i); // élément positionné       }    echanger(tableau, compteur, debut); // le pivot est placé    return compteur; // et sa position est retournée } void triRapideAux(int tableau[], const int debut, const int fin) {    if(debut<fin) // cas d'arrêt pour la récursivité    {       int pivot = partition(tableau, debut, fin); // division du tableau       triRapideAux(tableau, debut, pivot-1); // trie partie1       triRapideAux(tableau, pivot+1, fin); // trie partie2    } } void triRapide(int tableau[], const int longueur) {    triRapideAux(tableau, 0, longueur-1); }

Exemple :
Les grandes étapes de l'algorithme :

53	31	10	87	13	59	62	26	47	38
38	31	10	13	26	47	53	87	59	62
26	31	10	13	38	47	53	87	59	62
13	10	26	31	38	47	53	87	59	62
10	13	26	31	38	47	53	87	59	62
10	13	26	31	38	47	53	87	59	62
10	13	26	31	38	47	53	62	59	87
10	13	26	31	38	47	53	59	62	87

Complexité :
Le nombre d'opérations effectuées dans cet algorithme est très variable.
Dans le meilleur des cas, il de de l'ordre de n*ln(n).
Dans le pire des cas (ordre décroissant), il est de n*n.
En ce qui concerne la mémoire, c'est un algorithme récursif donc un peu de mémoire. Cela dépend de la taille du tableau en partie.