Aide sur un tris de tableau

Aide sur un tris de tableau - C - Programmation

Marsh Posté le 25-05-2006 à 16:48:31    

Salut,  :hello:  
 
Voila, jvous explique mon pb. J'ai un tri de tableau a faire pour un projet (1ere année licence info).  
 
Je dois le faire avec des regles précises c'est a dire que je ne dois pas modifier le tableau de départ.  :( Je dois créer un deuxieme tableau dans lequel je dois mettre les valeurs des indices des cases du tableau a trier (ordre croissant).  :heink: (Capiche ???  :na: ) A savoir que la premiere valeur du premier indice du tableau doit etre stockée dans une variable. (Imbitable le mec !!! :sweat:  ) C'est elle qui va lancer letableau des indices lors de l affichage du tableau trier. (C'est y ai, j ai capté, je suis perdou !!!  :pt1cable: ) A savoir que le tableau des indices doit stocker la valeur de l indice suivant dans la case de l indice courant. Pas tres tres clair en fait... ( Trop fort le keum !!! :lol: )
 
Au final moi j sais bien programmer mais la j me perds de trop dans les indices...  :whistle:  
 
J vous fais ounpititeéxemplo ( :p ) En fait ca ressemble a un tableau de pointeur...  :heink:  
 
 
tableau a trier :  
 
    | 5 | 3 | 4 | 1 | 3 | 8 |  
 
 
tableau des indices :  
 
   valeur de départ :  
   [3]  
 
   | 5 | 4 | 0 | 1 | 2 | -1 |  
 
********************************************************
 
le "-1" est une valeur arbitraire pour montrer que le tableau est fini.  :heink:  
 
J'vous envoie mon premier code source. A savoir qu'il n est pas terminé.  :sleep: J'me perd grave dans les indices et tout c'est la cata...  :pt1cable:  
 
Les profs veulent absoluement qu on utilise cette méthode. Fais ch....  :fou:    
 
Si qq un a une idée qu'il n hésite pas. Merci :p  
 
********************************************************
 
int main () {  
 
int i;  
int varEnt;  
int T[5];  
int tabEnt[5];  
 
 
/*La premiere partie du programme c'est pour que l'utilisateur rentre un tableau au hasard...J'ai fixé T a 5 valeur mais on peut faire plus ou moins :p*/  
 
printf("Saisissez 5 valeurs :\n" );  
 
for(i=0;i<5;i++) {  
scanf("%d",&T[i]);  
}  
 
/*Affichage des valeurs saisies plus haut*/  
printf("\n\n\n*** Les 5 valeurs ***\n\n" );  
 
for (i=0;i<5;i++) {  
printf("| %6d |",T[i]);  
}  
 
/*Voila, la on rentre dans la phase de tri.*/  
 
/*varEnt c'est la premiere valeur qui va appeler l indice du tableau (celui ou sont stockés les indices des cases du tableau a trier... pas tres clair... dsl  ) correspondant au deuxieme chiffre croissant*/  
varEnt=0;  
 
/*Ca c'est le tableau ou sont stockés les indices des cases triées*/  
tabEnt[varEnt]=-1;  
 
for (i=1;i<5;i++) {  
if (T[i]<T[varEnt]) {  
tabEnt[varEnt]=i;  
varEnt=i;  
}  
else {  
while (T[varEnt]<T[i]) {  
tabEnt[i]=-1;  
varEnt=i;  
}  
 
}  
}  
 
printf("\n\n *** %d *** \n",varEnt);  
 
for (i=0;i<5;i++) {  
printf("| %d |", tabEnt[i]);  
}  
 
printf("\n\n" );  
system ("pause" );  
return 0;  
}  
 
Il faut en fait qu'a chaque case de tabEnt soit stocké l'indice de la prochaine case de tabEnt ainsi que l'indice de la prochaine case de T.  
 
Merci d'avance !  :jap:


---------------
Les toles ondulées, les vaches aussi.
Reply

Marsh Posté le 25-05-2006 à 16:48:31   

Reply

Marsh Posté le 25-05-2006 à 21:48:38    

UP please !!!
 
Sérieux j'ai trop envie de le faire ce tri de dingue. J'm'en tape du projet en lui mm au final... J'veux apprendre.
 
Please


Message édité par Clemci le 25-05-2006 à 21:49:18
Reply

Marsh Posté le 25-05-2006 à 22:02:50    

tu peux utiliser qsort, ou alors si tu veux l'implementer toi meme, comme tu es obligé d'avoir le resultat trié dans un autre tableau tu peux faire un "bete" tri par insertion
 
http://fr.wikipedia.org/wiki/Tri_par_insertion

Reply

Marsh Posté le 25-05-2006 à 22:17:50    

Putain t'as raison c'est trop ca mais c'est de la folie... :pfff:  
 
J te recopie l extrait du sujet de tp. Si t'arrive a capter... j veux bien de l aide.  :sweat:  
 
***
 
Juste pour info, je dois trier en fait des tuyaux que j'ai préalablement rentré  :jap:  (dans un autre prog deja terminé)
en fait le déroulement du prog est marqué texto dans le sujet. Mais j m y perd de trop la !!!  :cry:  
 
 
Citation :
 
1 - Au début, le tableau des tuyaux est plein, le tableau des entiers et la variables des entiers sont vides.
 
2 - On mais "0" dans varEnt, et "-1" dans l'élément d'indice "0" de tabEnt. On a "classé" provisoirement le tuyau d indice "0", en indiquant que le premier est a l indice "0", et que ce premier est aussi le dernier, puisque son suivant est "-1" (valeur mise par convention pour indiqué qu il n y a pas de suivant).
 
3 - On reprend ensuite pour tous les autres tuyaux (en les prenant un par un dans l ordre ou ils sont dans le tableau des tuyaux) :
 
Le tuyau a traiter est il moins cher que l actuel moins cher ?
 
 -> S'il est moins cher : on le place en premier : son suivant doit etre l ancien permier et lui-meme devient le premier.
 
-> S'il n'est pas moins cher que le premier : on parcours "dans l ordre de leur prix" les tuyaux deja traité, jusqu'a ce qu'on trouve un plus cher ou qu'on ai vu tous les tuyaux deja traités :
         - Si celui a traiter est plus cher que tous les autres deja traité, on le place en dernier, son suivant doit etre l'ancien dernier et lui-meme doit etre dernier.
         - Si celui a traiter est placé entre deux tuyaux deja traité, soit i et j les indices de ces tuayux, j étant le suivant de i : le nouveau doit avoir pour suivant j, et devient lui-meme le suivant de i.
 
***
 
Vos etes encore la ???  :??:  Non pk j crois que j suis deja en train de me rouler par terre.  :pt1cable:


Message édité par Clemci le 25-05-2006 à 22:20:17
Reply

Marsh Posté le 25-05-2006 à 23:47:02    

1) Tu copies chaque élément du tableau entré sur tableau de sortie => tu obtiens un tableau de sortie identique à l'entrant
2) tu fais un tri à bulle du tableau de sortie
 
Algo du tri à bulle
 
flag=1
TQ flag != 0
FAIRE
     flag=0
     POUR chaque élément "i" allant du 2° jusqu'au dernier
     FAIRE
          SI (tab[i - 1] > tab[i])
          ALORS
                permuter tab[i] et tab[i - 1]
                flag=1
          FIN SI
     FIN FAIRE
FIN FAIRE        


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 26-05-2006 à 13:13:04    

OUaip ca j ai deja fait... Mais j ai pas le droit de faire de cette facon !!! C'est ouf.
 
J'ai rendu un truc de ce type au prof et il m a renvoyé ma copie en me disant qu il n en voulait pas...
 
Ca me gave de pas réussir a rentrer dans la logique de leur algo elle meme. J'adere pas du tout a l heure facon de trier et j me perds grave la :p
 
Merci de ta reponse

Reply

Marsh Posté le 26-05-2006 à 13:13:42    

Au fait c'est quoi qui tu appelles "flag" ???  :??:  
 
C'est une étiquette ???  :heink:

Message cité 2 fois
Message édité par Clemci le 26-05-2006 à 13:14:52
Reply

Marsh Posté le 26-05-2006 à 13:18:36    

Clemci a écrit :

Au fait c'est quoi qui tu appelles "flag" ? C'est une étiquette ?

Non. C'est une variable d'état qui vaut 0 ou 1.


---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le 26-05-2006 à 13:21:03    

Si tab contient tes valeurs,
 
Tu initialise un tableau de 5 éléments avec les valeurs 0-1-2-3-4
 
Ensuite pour trier tu fais  
 

Code :
  1. for ( int i = 0 ; i < 4 ; i++ )
  2. {
  3. for ( int j = i + 1 ; j < 5 ; j++ )
  4. {
  5.   if ( tab[tab_indice[i]] < tab[tab_indice[j]] )
  6.   {
  7.    int temp = tab_indice[i] ;
  8.    tab_indice[i] = tab_indice[j] ;
  9.    tab_indice[j] = temp ;
  10.   }
  11. }
  12. }


ensuite pour afficher
 
for (int i = 0 ; i < 5 ; i++ )
 printf("Nombre : %d\n",tab[tab_indice[i]]) ;


Message édité par LePhasme le 26-05-2006 à 13:22:33
Reply

Marsh Posté le 26-05-2006 à 13:28:09    

En fait la tu fais un tri direct ???
J'l'ai deja fait ce tri aussi...
 
A defaut de pouvoir avancer dans mon sujet de projet j'ai essayé de m amélioré un peut.
 
Il est super ton tri. J'comprends mm pas pkoi il n utilise pas cette méthode la. C'est n importe quoi...

Reply

Marsh Posté le 26-05-2006 à 13:28:09   

Reply

Marsh Posté le 26-05-2006 à 13:30:07    

Le truc en fait c'est que j ai une srtucture de tableau et que les profs nous demandes de trier la structure sans en renconstruire une triée mais en appelant les indices de la structure de sorte a avoir un tri beaucoup moins lourd (en place occupé.)


Message édité par Clemci le 26-05-2006 à 13:31:36
Reply

Marsh Posté le 26-05-2006 à 13:42:38    

C'est pas plutot un tableau de structure que tu as ?
 
Je trie uniquement les indices contenus dans tab_indice, ton tableau initial n'est pas modifié.
Le seul espace supplémentaire que j'occupe est celui pour stocker les indices, c'est un peu dur de faire moins si on peut pas toucher au tableau initial je pense...

Reply

Marsh Posté le 26-05-2006 à 13:46:40    

Ouaiii c est exactement ca... mdr j suis un grand drogué !!!
 
Bon j vais mon plonger dans ton prog alors :p
 
Merci

Reply

Marsh Posté le 26-05-2006 à 14:13:10    

Clemci a écrit :

Au fait c'est quoi qui tu appelles "flag" ???  :??:  
 
C'est une étiquette ???  :heink:


Emmanuel a parfaitement répondu. Je vais juste compléter...
flag = drapeau => variable à  2 état (levé/baissé) permettant de mémoriser pour plus tard si un truc s'est passé ou pas.
 
Grace aux opérateurs "bit à bit", il est possible de grouper plusieurs drapeaux sur une seule variable (chaque drapeau étant représenté par un bit différent de la variable) => 8 drapeaux par char, 16 par short, 32 par long


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 26-05-2006 à 14:14:57    

purée mais c est super important ca... Je cherchais la solution pour un truc l autre jour !!! wouinnnnnn
 
merci les amis c est nikel ca....

Reply

Marsh Posté le 26-05-2006 à 14:19:27    

Clemci a écrit :

purée mais c est super important ca... Je cherchais la solution pour un truc l autre jour !!! wouinnnnnn
 
merci les amis c est nikel ca....


Bienheureux les simples en esprit...   :sol:  


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 26-05-2006 à 14:32:47    

hihihiiiiii
 
Pour le tri c'est pas encore ce que demande exactement le prof mais bon j vais amélioré ca
de tute facon c est trop tard je devait le rentre mardi
donc la c est que du benef
 
mdr...
 
heureux le mec blazé qui va foiré son année pour une connerie :p

Reply

Marsh Posté le 26-05-2006 à 16:41:39    

Salut
Il est "amusant" ce tri, il doit être à la mode car c'est la deuxième fois cette année que je le vois passer.
 
Pour le faire, il faut que tu utilises le principe de l'insertion dans une liste triée
 
Donc au départ tu mets 0 dans la case départ et -1 dans la case 0 du tableau indice.
 
Ensuite, tu insères les éléments du tableau dans ta liste triée.
 
Tu as intêrèt à distinguer le cas simple où l'élément à insérer est le plus petit, et sinon, tu travailles avec un coup d'avance, donc avec tab[ind[j]].
 
Bon courage.

Reply

Marsh Posté le 26-05-2006 à 16:45:43    

Merci Trap D c'est exactement ca... J m'y remets ce soir...
 
la folie ce tri j'm'embrouille grave dans leur indices la !!!

Reply

Marsh Posté le 26-05-2006 à 16:49:37    

Fais le à la main pour bien comprendre le système, l'exemple est très bien choisi car il accumule les difficultés.

Reply

Marsh Posté le 26-05-2006 à 16:52:21    

L'exemple c'est moi qui l'ai pondu mdr. :heink:  
 
J'me fourre dans le caca tout seul. :cry:  
 
C'est quand mm dingue ca : quand j travail sur papier j capte exactement ce que je dois faire
mais apres quand faut faire le code source... y'a plus personne...
 
Tous mes neurones se barrent dans tous les sens... huhu  :pt1cable:

Message cité 1 fois
Message édité par Clemci le 26-05-2006 à 18:54:52
Reply

Marsh Posté le 26-05-2006 à 16:57:33    

Clemci a écrit :

L exemplke c moi qui m ai pondu mdr. J me fourre dans le caca tout seul.
 
C'est quand mm dingue ca : quand j travail sur papier j capte exactement ce que je dois faire
mais apres quand faut faire le code source... y'a plus personne... tous mes neurones se barrent dans tous les sens... huhu


Ecris l'algo, ça colle les neurones...
 


---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed