{ Fonction de reorganisation d'un tableau t     }
{ d'entiers des indices indi a indf inclus      }
{ par replaçage à gauche de toutes les valeurs  }
{ plus petites que t[pivot], à droite de toutes }
{ les valeur plus grande que t[pivot]           }
{ et au centre de toutes les valeurs egales     }
{ à t[pivot]                                    }
{ Retourne l'indice de la valeur d'indice       }
{ maximum, apres replaçage, de toutes           }
{ les valeurs égales à t[pivot]                 }

entier fonction pivotage(-> entier [] t ->,
                         -> entier indi,
                         -> entier indf,
                         -> entier pivot)
  entier i
  entier j <- indi
  entier aux <- t[pivot]
  t[pivot] <- t[indf]
  t[indf] <- aux
  pour i de indi à indf-1 faire
    si t[i] <= t[indf] alors
      aux <- t[i]
      t[i] <- t[j]
      t[j] <- aux
      j <- j+1
    fsi
  fait
  aux <- t[indf]
  t[indf] <- t[j]
  t[j] <- aux
  retourner j
fin fonction

{ Action de tri rapide par ordre croissant      }
{ d'un tableau d'entiers des indices indi       }
{ à indf compris                                }
{ Méthode de choix du pivot : Valeur située     }
{ à l'indice moyen de indi et indf              }
{ t    : Le tableau d'entiers à trier           }
{        par ordre croissant                    }
{ indi : L'indice initial des valeurs à trier   }
{ indf : L'indice final des valeurs à trier     }

action triRapide(-> entier [] t ->,
                 -> entier indi,
                 -> entier indf)
  entier iMedian
  entier aux
  entier pivot
  entier nbVal <- indf-indi+1
  si nbVal > 1 alors
    si nbVal == 2 alors
      si t[indf] < t[indi] alors
        aux <- t[indi]
        t[indi] <- t[indf]
        t[indf] <- aux
      fsi
      sinon
      pivot <- (indi+indf)/2
      iMedian <- pivotage(t,indi,indf,pivot)
      triRapide(t,indi,iMedian-1)
      triRapide(t,iMedian+1,indf)
    fsi
  fsi
fin action

{ Action de tri rapide par ordre croissant      }
{ d'un tableau d'entiers                        }
{ Pivot choisi : Valeur médiane du tableau      }
{ t : Le tableau d'entiers à trier              }
{     par ordre croissant                       }

action triRapide(-> entier [] t ->)
  triRapide(t,0,longueur(t)-1)
fin action