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

matser

[Actualité] tri par segmentation

Noter ce billet
par , 02/01/2022 à 18h15 (1948 Affichages)
on segmente le sous-tableau T en trois parties, place étant un indice:
* 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
** T[i] <= pivot
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] > pivot
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 }
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:
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
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;
}

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

Mis à jour 12/01/2022 à 01h50 par matser

Tags: segmentation, tri
Catégories
Sans catégorie

Commentaires