* indices de inf à place-1
dans cette partie, les valeurs sont inférieures à T[place]
* indice valant place* indices de place+1 à sup
dans cette partie, les valeurs sont supérieures à T[place]
on initialise pivot à T[inf]
l'assertion de boucle pour la segmentation est:
{ si inf+1<=x<=i-1 alors T[x]<=pivot } et { si j+1<=x<=sup alors T[x]>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[x]<=pivot } et { si j+1<=x<=sup alors T[x]>pivot }
Comme pivot=T[inf], on permute T[inf] et T[j] et on obtient :
{ si inf<=x<=j alors T[x]<=pivot } et { si j+1<=x<=sup alors T[x]>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[j]=pivot. On retourne donc cette valeur
* i <= j{si inf+1<=x<=j alors T[x]<=pivot } et { si j+1<=x<=sup alors T[x]>pivot }
Comme pivot=T[inf], on permute T[inf] et T[j] et on obtient :
{ si inf<=x<=j alors T[x]<=pivot } et { si j+1<=x<=sup alors T[x]>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[j]=pivot. On retourne donc cette valeur
** T[i] <= pivot
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.On a si inf+1<=x<=i alors T[x]<=inf
On incrémente i pour retrouver { si inf+1<=x<=i-1 alors T[x]<=pivot } et { si j+1<=x<=sup alors T[x]>pivot } et { les éléments, du sous-tableau d'indices i à j ne sont pas triés }
** T[i] > pivotOn incrémente i pour retrouver { si inf+1<=x<=i-1 alors T[x]<=pivot } et { si j+1<=x<=sup alors T[x]>pivot } et { les éléments, du sous-tableau d'indices i à j ne sont pas triés }
On permute T[i] et T[j]. On a alors :
{ si inf+1<=x<=i-1 } et { si j<=x<=sup alors T[x]>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[x]<=pivot } et { si j+1<=x<=sup alors T[x]>pivot} et { les éléments, du sous-tableau, d'indices i à j, ne sont pas triés }
{ si inf+1<=x<=i-1 } et { si j<=x<=sup alors T[x]>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[x]<=pivot } et { si j+1<=x<=sup alors T[x]>pivot} et { les éléments, du sous-tableau, d'indices i à j, ne sont pas triés }
implémentation:
| Code : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | #include <iostream>
#include <vector>
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::vector<int>T;
};
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<n;i++){
std::cout<<"élément n°"<<i+1<<"?";
std::cin>>x;
ajouter(x);
}
}
int tableau::taille(){
return T.size();
}
void tableau::triseg(int const &inf,int const &sup){
int place;
if(inf<sup){
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<<i<<" ";
std::cout<<std::endl;
}
void tableau::permuter(int const &i,int const &j){
int t;
t=T[i];
T[i]=T[j];
T[j]=t;
}
int tableau::segmentation(int const &inf,int const &sup){
int i=inf+1,j=sup,pivot=T[inf];
while(i<=j)
if(T[i]<=pivot)
i++;
else{
permuter(i,j);
j--;
}
permuter(inf,j);
return j;
} |