#include <iostream.h>
#include <stdio.h> //pour rand
#define LNOM 20
typedef char tnom[LNOM];

class element
 {
  tnom nom;
  float val;
 public:
  float get_val(void) {return val;}
  void set_val(float n) {val=n;}
  
  void saisie(void);
  void affiche(void);
  void aleatoire(void);
 }; //point virgule !
 
void element::saisie(void)
 {
  cout<<"nom ? ";
  cin>>nom;
  cout<<"valeur ?";
  cin>>val;
 }
void element::affiche(void)
 {cout<<nom<<" : valeur : "<<get_val();}
void element::aleatoire(void)
 {
  int i,nb;
  nb=rand()%2+5;
  for(i=0;i<nb;i++)nom[i]=rand()%26+'a';
  nom[nb]='\0';
  val=(rand()%2000)*0.01;
 }
 
#define DIMTAB 100 
class tableau
 {
  int nb;
  element t[DIMTAB];
 public:
  void saisie(void);
  void aleatoire(void);
  void affiche(void);
  void affiche(int);
  int recherche(float val); //retourne -1 si introuvable
  int dichotomie(float val); //retourne -1 si introuvable, le tableau doit etre trie
  void insere_fin(element e);
  void insere(element e,int pos); //celui en pos sera placéeacute; en pos+1
  void insere_debut(element);
  void supprime_fin(void);
  void supprime(int pos);
  void supprime_debut(void);
  void echange(int,int);
  int indice_du_plus_petit(int a_partir_de); 
  void tri_selection(void);
  void tri_bulle(void);
  int indice_du_premier_plus_grand(element);
  void tri_insertion(void);
  void retourne(void);
 };
 
void tableau::saisie(void)
 {
  int i;
  float n;
  cout<<"combien d'elements ? ";
  cin>>nb;
  if(nb>DIMTAB){cout<<"trop gros\n";exit(0);}
  for(i=0;i<nb;i++)
   {
    cout<<"element "<<i+1<<" : ";
    t[i].saisie();
   }
 }
 
void tableau::aleatoire(void)
 {
  int i;
  cout<<"combien d'elements ? ";
  srand(time(NULL));
  cin>>nb;
  for(i=0;i<nb;i++)
    t[i].aleatoire();
 }

void tableau::affiche(int i) //affichage iièegrave;me
 {
  t[i].affiche();
 }
 
void tableau::affiche(void) //affichage tous
 {
  int i;
  float n;
  cout<<"affichage des "<<nb<<" elements :\n";
  for(i=0;i<nb;i++)
   {
    cout<<i+1<<" : ";
    affiche(i);
    cout<<"\n";
   }
 }
 
int tableau::recherche(float val) //retourne -1 si introuvable
 {
  int i;
  for(i=0;i<nb;i++) if(t[i].get_val()==val)return i;
  return -1;
 } 
 
int tableau::dichotomie(float val) //retourne -1 si introuvable
//attention, ne chercher par dichotomie QUE SI LE TABLEAU EST TRIE !!!
 {
  int inf,sup,milieu;
  inf=0;
  sup=nb;
  do
   {
    milieu=(inf+sup)/2;
    if(t[milieu].get_val()==val)return milieu;
    else if(t[milieu].get_val()<val)inf=milieu+1;
    else sup=milieu-1;
   }
  while(sup>inf);
  if(t[milieu].get_val()==val)return milieu; 
  else if(t[sup].get_val()==val)return sup; 
  else if(t[inf].get_val()==val)return inf; 
  else return -1;
 } 
 
void tableau::insere_fin(element e)
 {
  if(nb==DIMTAB)cout<<"impossible\n";
  else
   {
    t[nb]=e;
    nb++;
   }
 }
void tableau::insere(element e,int pos) //celui en pos sera placéeacute; en pos+1
 {
  int i;
  if(pos<0||pos>nb||nb==DIMTAB)cout<<"impossible\n";
  else
   {
    for(i=nb;i>pos;i--)t[i]=t[i-1];
    t[pos]=e;
    nb++;
   }
 }
 void tableau::insere_debut(element e)
 {
  insere(e,0);
 }

void tableau::supprime_fin(void)
 {if(nb>0)nb--;}
void tableau::supprime(int pos)
 {
  int i;
  if(nb==0||pos>=nb||pos<0)cout<<"impossible\n";
  else
   {
    nb--;
    for(i=pos;i<nb;i++)t[i]=t[i+1];
   }
 }
void tableau::supprime_debut(void)
 {supprime(0);}
 
void tableau::echange(int i,int j)
 {
  element tmp;
  if(i<0||i>=nb||j<0||j>=nb)cout<<"impossible\n";
  else
   {
    tmp=t[i];
    t[i]=t[j];
    t[j]=tmp;
   }
 }
   
int tableau::indice_du_plus_petit(int a_partir_de)
 {
  int pp,i;
  pp=a_partir_de;
  for(i=a_partir_de+1;i<nb;i++) 
    if(t[i].get_val()<t[pp].get_val())pp=i;
  return pp;
 }

int tableau::indice_du_premier_plus_grand(element e)
 {
  int i=0;
  while(i<nb && t[i].get_val()<e.get_val())i++;
  return i;
 } 

void tableau::tri_bulle(void)
 {
   int i;
   int encore=1;
   while(encore)
    {
     encore=0;
     for(i=1;i<nb;i++)
       if(t[i-1].get_val()>t[i].get_val())
        {
	 echange(i,i-1);
	 encore=1;
	}
     }
  }
  
void tableau::tri_selection(void)
 {
   int i,pp;
   for(i=0;i<nb-1;i++)
    {
     pp=indice_du_plus_petit(i);
     if(i!=pp)echange(i,pp);
    }
  }

void tableau::tri_insertion(void)
 {
   int i,bonneplace;
   element tmp;
   for(i=1;i<nb;i++)
    {
     bonneplace=indice_du_premier_plus_grand(t[i]);
     if(bonneplace>i)cout<<"impossible\n"<<endl;
     if(bonneplace<i)
      {
       tmp=t[i];
       supprime(i);
       insere(tmp,bonneplace);
      }
    }
  }
  
void tableau::retourne(void)
 {
  int i,milieu;
  milieu=nb/2;
  for(i=0;i<milieu;i++)echange(i,(nb-1)-i);
 }

int main(void)
 {
  float v;
  tableau x;
  x.aleatoire();
  x.affiche();
  x.tri_selection();
  x.affiche();
  do 
   {
    cout<<"valeur a chercher (-1 pour finir) ?";
    cin>>v;
    cout<<"trouve en position "<<x.recherche(v)<<" et "<<x.dichotomie(v)<<"\n";  x.affiche();
   }
  while(v>=0);
  x.retourne();
  x.affiche();
  x.tri_bulle();
  x.affiche();
  x.retourne();
  x.tri_insertion();
  x.affiche(); 
 }