Tri rapide ( quick sort)

O(nlogn) en moyenne, mais quadratique au pire cas, en place mais pas stable.

Cette méthode de tri, probablement la plus utilisée actuellement - d'aucuns disent même que c'est l'algorithme le plus utilisé au monde - a été inventée par Sir Charles Antony Richard Hoare en 1960. Elle illustre le principe dit « diviser pour régner », qui consiste à appliquer récursivement une méthode destinée à un problème de taille donnée à des sous-problèmes similaires, mais de taille inférieure. Ce principe général produit des algorithmes qui permettent souvent d'importantes réductions de complexité.

On considère un élément au hasard dans le tableau, le pivot, dont on affecte la valeur à une variable, disons pivot. On procède alors à une partition du tableau en 2 zones : les éléments inférieurs ou égaux à pivot et les éléments supérieurs ou égaux à pivot. Si on parvient à mettre les éléments plus petits en tête du tableau et les éléments plus grands en queue de tableau, alors on peut placer la valeur de pivot à sa place définitive, entre les deux zones. On répète ensuite récursivement la procédure sur chacune des partitions créées jusqu'à ce qu'elle soit réduite à un ensemble à un seul élément. La procédure de tri rapide est la suivante :

fonction partition(entier[] tab, entier debut, entier fin)

retourne un entier

  entier indicePivot;

  entier k <- debut;

  entier tmp;

  entier i;

/* la valeur pivot est le premier élément du tableau */

/* afin d'éviter les mauvaises répartitions pour ce tri */

/* on tire aléatoirement la valeur du pivot avant de commencer */

  indicePivot <- entier aléatoire entre debut et fin;

  tmp <- tab[indicePivot];

  tab[indicePivot] <- tab[debut];

  tab[debut] <- tmp;

  pour (i de debut+1 à fin en incrémentant de 1) faire

     si (tab[i] < tab[debut]) alors

        tmp <- tab[i];

        tab[i] <- tab[k+1];

        tab[k+1] <- tmp;

        k <- k + 1;

    fin si

  fin pour

  tmp <- tab[debut]

  tab[debut] <- tab[k];

  tab[k] <- tmp; 

  retourner k;

fin fonction

procedure triRapideR(entier[] tab, entier debut, entier fin)

  si (fin > debut) alors

     entier indicePivot <- partition(tab, debut, fin);

     triRapideR(tab, debut, indicePivot - 1);

     triRapideR(tab, indicePivot + 1, fin);

  fin si

fin procedure

procedure triRapide(entier[] tab)

  triRapideR(tab, 1, N);

fin procedure

La partie du tri la plus sensible reste le choix du pivot. Dans l'algorithme précédent, il est choisi au hasard parmi les éléments du tableau, mais ce choix peut se révéler catastrophique : si le pivot est à chaque choix le plus petit élément du tableau, alors le tri rapide dégénère en tri par sélection.

On montre que la complexité de ce tri est :

·       dans le meilleur des cas, en O (N log N) 

·       en moyenne, en O (N log N) 

·       dans le pire des cas, en O (N²).

Il existe bon nombre d'astuces pour rendre le cas dégénéré du tri rapide le plus improbable possible, ce qui rend finalement cette méthode la plus rapide en moyenne parmi toutes celles utilisées.