Petit algo de tri...

Commenter

Contenu du snippet

Ah oui... c'est juste un petit algo qui permet de trier un tableau à l'aide d'un autre tableau intermediaire.Par exple j'ai le tab [12,-54,5,62,8,10,-25] à trier, alors je m'arrange à creer un tableau intermediare ( tab_inter ) de telle sorte que:
Je prend chaque element du tableau initial,je le compare aux autres elements du tab,puis je compte le nombre d'éléments qui est inferieur ou egal à ce nombre dans le tableau et ce nombre trouvé est stocké à la même position du tableau intermediaire que celle l'élément du tableau de départ. Bon je sais pas si je me fais comprendre...Pour ce qui est de mon tab d'en haut:
qd je prend 12,il y'a 6 nbres qui sont <= 12 dc tab_inter[0]=6, ainsi de suite,on aura donc:
tab_inter[ ] ={6,1,3,7,4,5,2}
Ainsi on a un tableau qui contient des chiffres de 1 à tab.size()-1,il suffit mnt de trouver la petite formule pour classer le tab initial en utilisant le tab_inter ( ça,je vous laisse faire )
En fait ce petit algo s'adresse aus débutants en c++ qui travaille sur le tableaux et les boucles,c'est pour cette raison que je ne parle même pas de la complexité, car bcp de methodes plus interessantes existent (insertion,quicksort,...)

Source / Exemple : 


#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<vector>
using namespace std;

 void affiche(vector<int>tab) {
    for(int a=0;a<tab.size();a++){
    cout<<tab[a]<<" ";
	} 
 }   
 void Treat_Array(vector<int>& Tab_In,int n)  // Tab_In pour tab initial
{
  vector<int>Tab_Cpt(n);    // Tab_Cpt pour tab intermediaire
  int compteur=0,j=0;
  while(j<n)
   {  
      for(int q=0;q<n;q++){
  if(Tab_In[ j ]>=Tab_In[ q ]) // ici j est statiq,c'est q qui varie
  {                               
    compteur++;
  }    
 } 
       Tab_Cpt[ j ]=compteur;
  compteur=0;  // remet le compteur à 0 pr chaque nvelle valeur de j
            j++;
  }            
cout<<"\n Tableau intermediaire : ";
affiche(Tab_Cpt);cout<<"\n\n";
  } 

int main()
{
  srand(clock());
  int n;
  cout<<endl<<"Entrer la taille du tableau initial : ";cin>>n;cout<<"\n";
  vector<int>Tab_Test(n); 
   for(int i=0;i<n;i++)
 {
Tab_Test[i]=(rand()%50)-10; // nbres aléatoires pr avoir des tab[i]< 0
 }
  cout<<"Tableau initial avant tri : ";affiche(Tab_Test);cout<<endl; 
  Treat_Array(Tab_Test,n);
    return 0;
}

Conclusion :


Rien à dire en particulier,sauf que les boucles utilisées pour remplir le tab_inter peuvent être optimisées,c'est justement ça le but du truc puisque c'est pas du tt cuit,ameliorez ce programme et trouver lui des applications...
Oui aussi un truc,pour des tableaux un peu grands,le min de tab_inter peut etre # de 1,mais ça ne change rien à l'algo,puisque ce sera tjrs le min,on peut corriger ce petit bug,mais je suis certain que vs allez le faire en un clin d'oeil... Merci à tous!

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (pmbala)