Petit algo de tri...

Soyez le premier à donner votre avis sur cette source.

Snippet vu 10 541 fois - Téléchargée 35 fois

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!
Ajouter un commentaire Commentaires
Messages postés
230
Date d'inscription
mardi 21 janvier 2003
Statut
Membre
Dernière intervention
15 mai 2008

Voilà pour le Merge Sort :
http://www.cppfrance.com/code.aspx?ID=29675
Messages postés
230
Date d'inscription
mardi 21 janvier 2003
Statut
Membre
Dernière intervention
15 mai 2008

Tu peux aussi mettre un compteur de temps, mais c'est très bourrin : l'utilisation des autres proggs fausse le calcul et ca change très fort pour les longs algo (j'ai déjà eu 1 seconde d'écart pour un algo de 30 sec exécuté 2 fois !!!)
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

C'est exacte pmbala, la comparaison de deux programmes est un problème incalculable (ce qui se traduit par l'impossibilité absolue d'écrire un programme qui teste l'équivalence entre deux programmes donnés). Mais ce que je te propose, c'est de, à la main, analyser ton propre code pour en retirer une idée de l'évolution de la quantité de ressources (temps / mémoire) qui seront nécessaire à ton algo à mesure qu'on lui demandera de traîter un problème plus gros. Ça te permet (mais ce n'est pas le but premier) d'estimer combien de temps ton algo mettra à trier une liste de 1 000 000 d'éléments si tu sais en combien de temps il trie une liste de 10 000 éléments. Mais comme je te disais, ça sert plus à comparer les algos entre eux qu'à faire des prévisions, parce que le calcul de complexité est très grossier et imprécis.
Messages postés
230
Date d'inscription
mardi 21 janvier 2003
Statut
Membre
Dernière intervention
15 mai 2008

En fait, tu peux calculer la complexité en ragardant combien de fois ton code effectuera le contenu des boucles. Dans ton cas n², si j'ai bien lu...
Si tu veux en savoir plus, je ne peux que trop te conseiller l'excellent article de Kirua justement (que je remercie) :
http://www.coder-studio.com/?page=tutoriaux_aff&code=autre_3

Je viends d'écrire un algo de type Merge Sort (de complexité O(n logn/log2)) en pseudo code... Le temps de l'écrire en C++ et je l'envoie sur le site.
Messages postés
30
Date d'inscription
samedi 4 décembre 2004
Statut
Membre
Dernière intervention
2 avril 2008

Oui dominion, je sais que mon truc sur le tri est tres tres lent,et c'est pr cela que j'ai tenu à preciser que c'etait pour les debutants de chez debutants,ravi de savoir que tu pourras l'utiliser à de meilleures fins...(fais nous savoir la suite)

Kirua , je me suis aussi demandé comment faire pr comparer des algos,mais j'avais un prof qui m'avait dit qu'il n'existait pas d'algo capable de faire la comparaison de deux algos...bon je crois avoir mal lu ce que tu voulais dire,je vais aller voir ces tutos pour en savoir plus... merci à tous
Afficher les 7 commentaires

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.