Le tri par segmentation ou tri rapide

Un billet de blog de matser

on segmente le sous-tableau T en trois parties, place étant un indice:
* indices de inf à place-1dans cette partie, les valeurs sont inférieures à T
* indice valant place
* indices de place+1 à supdans cette partie, les valeurs sont supérieures à T

on initialise pivot à T

l'assertion de boucle pour la segmentation est:
{ si inf+1<=x<=i-1 alors T<=pivot } et { si j+1<=x<=sup alors T>pivot } et { les éléments, du sous-tableau d'indices i à j ne sont pas triés }
* i = j+1
on a :
{si inf+1<=x<=j alors T<=pivot } et { si j+1<=x<=sup alors T>pivot }
Comme pivot=T, on permute T et T et on obtient :
{ si inf<=x<=j alors T<=pivot } et { si j+1<=x<=sup alors T>pivot }
Dans ce cas, la segmentation de cette partie de ce sous-tableau est terminée. L'indice du pivot est la valeur de j car T=pivot. On retourne donc cette valeur

* i <= j
** T <= pivot
On a si inf+1<=x<=i alors T<=inf
On incrémente i pour retrouver { si inf+1<=x<=i-1 alors T<=pivot } et { si j+1<=x<=sup alors T>pivot } et { les éléments, du sous-tableau d'indices i à j ne sont pas triés }
** T > pivot
On permute T et T. On a alors :
{ si inf+1<=x<=i-1 } et { si j<=x<=sup alors T>pivot } et { les éléments, du sous-tableau, d'indices i à j - 1, ne sont pas triés }
On décrémente j pour retrouver { si inf+1<=x<=i-1 alors T<=pivot } et { si j+1<=x<=sup alors T>pivot} et { les éléments, du sous-tableau, d'indices i à j, ne sont pas triés }


puis, le retour de la segmentation étant dans la variable "place", on trie le sous-tableau d'indices inf à place-1 et celui d'indices place+1 à sup.
implémentation:
#include
#include

class tableau{
public:
tableau();
void triseg(int const &inf,int const &sup);
void ajouter(int const &i);
void permuter(int const &i,int const &j);
void ecrire();
int taille();
private:
int segmentation(int const &inf,int const &sup);
std::vectorT;
};

int main(){
tableau tab;
tab.triseg(0,tab.taille()-1);
//tab.taille()-1 est l'indice du dernier élément du tableau
tab.ecrire();
}

tableau::tableau(){
int n,x;
std::cout<<"Combien d'éléments?";
std::cin>>n;
for(int i=0;i std::cout<<"élément n°"< std::cin>>x;
ajouter(x);
}
}

int tableau::taille(){
return T.size();
}

void tableau::triseg(int const &inf,int const &sup){
int place;
if(inf place=segmentation(inf,sup);
triseg(inf,place-1);
triseg(place+1,sup);
}
}

void tableau::ajouter(int const &i){
T.push_back(i);
}

void tableau::ecrire(){
for(auto i:T)
std::cout< std::cout< }

void tableau::permuter(int const &i,int const &j){
int t;
t=T;
T=T;
T=t;
}

int tableau::segmentation(int const &inf,int const &sup){
int i=inf+1,j=sup,pivot=T;
while(i<=j)
if(T<=pivot)
i++;
else{
permuter(i,j);
j--;
}
permuter(inf,j);
return j;
}