IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

matser

tri par segmentation

Noter ce billet
par , 05/06/2020 à 09h14 (254 Affichages)
la segmentation d'un sous-tableau dont les indices varient de p à n
ceci est un remaniement d'un sous-tableau tel que si x est inférieur ou égal à un pivot, il se trouvera à gauche de celui-ci, et se trouvera à droite du pivot si il lui est supérieur.
soit T[p] le pivot, le premier élément du sous-tableau
l'invariante de boucle est "si p<x<=i-1 alors T[x]<=T[p] et si j+1<=x<=n alors T[x]>T[p]
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
* i= j+1
   l'invariant "si p<x<=i-1 alors T[x]<=T[p] et j+1<=x<=n alors T[x]>T[p]" devient "si p<x<=i-1 alors T[x]<=T[p] et si i<=x<=n alors T[x]>T[p]
   comme T[j]<=T[p], on permute T[j] et t[p] et le sous-tableau est segmenté, on retourne j, algo fini
* i<j+1
   **T[i]<=T[p]
      ***T[j]>T[p]
         on a alors "si p<x<i alors T[x]<=T[p] et si j<=x<=n alors T[x]>T[p]"
         on fait i:=i+1 et j:=j-1 pour retrouver l'invariante de boucle
      ***T[j]<=T[p]
         comme T[i]<=T[p], on a "si p<x<=i alors T[x]<=T[p]
         on fait i:=i+1 pour retrouver l'invariant de boucle
   **T[i]>T[p]
      ***T[j]<=T[p]
         on permute T[i] et T[j]
         on a alors "si p<x<i alors T[x]<=T[p] et j<=x<=n alors T[x]>T[p]"
         on fait i:=i+1 et j:=j-1 pour retrouver l'invariante de boucle
      ***T[j]>T[p]
         on a "si j<=x<=n alors T[x]>T[p]"
         on fait j:=j-1 pour retrouver "si j+1<=x<=n alors T[x]>T[p]"
une fois le sous-tableau segmenté, on utilise j, qui est retourné par la segmentation, pour segmenter le sous-tableau d'indices variant de p à j, et le sous-tableau d'indices variant j+1 à n
le raisonnement récursif est:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
* p=n
   T n'a que un élément, le tableau est trié. algo fini
* p<n
   j=segmenter(T,p,n)
   triSeg(T,p,j)
   triSeg(T,j+1,n)
le programme en C++
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
#include <iostream>
#include <vector>
void triSeg(std::vector<int> &T,int const &p,int const &n);
int segmenter(std::vector<int> &T,int const &p,int const &n);

int main(){
  int n,e;
  std::vector<int>T;
  std::cout<<"combien d'éléments?"<<std::endl;
  std::cin>>n;
  for(int i=0;i<n;i++){
    std::cout<<"élément "<<i+1<<std::endl;
    std::cin>>e;
    T.push_back(e);
  }
  triSeg(T,0,n-1);
  for(int i:T)
    std::cout<<i<<" ";
  std::cout<<std::endl;
}


void triSeg(std::vector<int> &T,int const &p,int const &n){
  int j;
  if(p<n){
    j=segmenter(T,p,n);
    triSeg(T,p,j);
    triSeg(T,j+1,n);
  }
}

int segmenter(std::vector<int> &T,int const &pivot,int const &n){
  int t;
  int i=pivot+1;
  int j=n;
  while(i<j+1){
    if(T[i]<=T[pivot])
      if(T[j]>T[pivot]){
	i++;
	j--;
      }
      else
	i++;
    else
      if(T[j]<=T[pivot]){
	t=T[i];
	T[i]=T[j];
	T[j]=t;
	i++;
	j--;
      }
      else
	j--;
  }
  t=T[pivot];
  T[pivot]=T[j];
  T[j]=t;
  return j;
}

Envoyer le billet « tri par segmentation » dans le blog Viadeo Envoyer le billet « tri par segmentation » dans le blog Twitter Envoyer le billet « tri par segmentation » dans le blog Google Envoyer le billet « tri par segmentation » dans le blog Facebook Envoyer le billet « tri par segmentation » dans le blog Digg Envoyer le billet « tri par segmentation » dans le blog Delicious Envoyer le billet « tri par segmentation » dans le blog MySpace Envoyer le billet « tri par segmentation » dans le blog Yahoo

Catégories
Sans catégorie

Commentaires