Quick Select

Pseudo code

Entrée

On considère qu'on a en entrée un tableau T de valeurs.

Partition

On utilise la même fonction de partitionnement que pour un tri rapide :

Partition(p, gauche, droite)
    Soit m = gauche
    Pour i allant de gauche à droite
        Si T[i] <= T[p]
            Echanger les cases i et m dans T
            Incrémenter m
    Retourner (m - 1)

Algorithme

QuickSelect(rang, gauche, droite)
    Si gauche = droite
        Retourner gauche
 
    Soit p un pivot choisi au hasard entre gauche et droite
    nbInf = Partition(p, gauche, droite)
 
    Si nbInf >= rang
        Retourner QuickSelect(rang, gauche, gauche + nbInf - 1)
    Sinon
        Retourner QuickSelect(rang - nbInf, gauche + nbInf, droite)