Tri dans un tableau et indices

**size_one_1** · 15/05/2006, 14h56

bonjour a vous,
voici mon probleme, je dispose d'un tableau contenant des prix qui sont dans le desordre.
je souhaite les classer.
pour ce faire, je cree un tableau d entiers du meme nombre d elements que le premier dans lequel se trouve l indice du prix suivant.
le premier indice etant donné par une variable appelée "premier" dans mon code.
voici un exemple :
disons que je dispose d un tableau dans lequel sont mes prix dans le desordre :
|3|1|2|
une fois trié le tableau créé sera donc :
|-1|2|0| et "premier"=1
le -1 m indiquant que c etait le dernier prix.
je m explique :
- a l indice 1 (indiqué par "premier"), se trouve le prix le plus bas
- a l indice 1 de mon nouveau tableau ce trouve 2
ce qui m indique que le second prix le moins cher est a l indice 2 du premier tableau
- a l indice 2, toujours de mon nouveau tableau ce trouve 0, m indiquant le suivant, jusqu a trouver -1 pour me dire que c etait le dernier prix, et donc le plus cher.

l interet d une telle methode est que l on ne parcourt qu une seule fois le premier tableau.
Pour un grand nombre d elements, ce tri est tres rapide...

voici mon code :

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
#include <stdio.h>
 
int initabtuyau(int nbrtuyau, int tabtuyau[]); // initialise le tableau
int triprix(int nbrtuyau, int tabtuyau[]); //fonction de tri
int afftab(int nbr, int tab[]); //affiche un tableau
int initabindice(int nbr, int tabindice[]); //initialise le nouveau tableau
 
int main(void){
    int nbrtuyau;
    printf("Entrer le nombre de tuyaux differents :\n");
    scanf("%d", &nbrtuyau);
    int tabtuyau[nbrtuyau];
    initabtuyau(nbrtuyau, tabtuyau);
    system("pause");
    triprix(nbrtuyau, tabtuyau);
    system("pause");
}
 
int initabtuyau(int nbrtuyau, int tabtuyau[]){
    printf("Initialisation du Tableau :\n");
    int x;
    for(x=0; x<nbrtuyau; x++){
    printf("Origine du Tuyau %d :\n", x);
    scanf("%d", &tabtuyau[x]);
    }
     return 1;
}
 
 
int triprix(int nbrtuyau, int tabtuyau[]){
    int tabindice[nbrtuyau];
    initabindice(nbrtuyau, tabindice);
    int tuyencours;
    int premier;
    int ancienpremier;
    int dernier;
    int a;
    int cherche;
    int juste_sup, juste_inf, jj;
    premier=0;
    for(tuyencours=0; tuyencours<nbrtuyau; tuyencours++){
                      if(tuyencours==0){   // au premier, il est forcement le moins cher et le dernier !
                                           tabindice[0]=-1;
                                           dernier=0;
                                           premier=0;
                      }
                      else{
                           printf("else pas le premier\n");
                           if(tabtuyau[tuyencours]<=tabtuyau[premier]){     // le moins cher de tous
                                                    ancienpremier = premier;
                                                    premier = tuyencours;
                                                    tabindice[tuyencours]=ancienpremier;
                           }
                           else{
                                cherche=premier;
                                juste_inf=premier;                  
                                while(((tabtuyau[tuyencours]>tabtuyau[cherche]) || (juste_inf!=-1)) || (cherche!=-1)){
                                                                                jj=juste_inf;                                                                        
                                                                               juste_inf = tabindice[cherche];
                                                                               cherche=tabindice[cherche];     
                                                                               printf("juste_inf = %d\ttabtuyau[juste_inf]=%d\n", juste_inf, tabtuyau[juste_inf]);
                                                                               printf("jj=%d\tcherche= %d\n", jj, cherche);                                                                                                        
                                }
                                if((juste_inf==-1) && (cherche==-1)){ // le plus cher
                                                  tabindice[dernier]=tuyencours;
                                                  tabindice[tuyencours]=-1;
                                                  dernier=tuyencours;
                                                  //printf("le plus cher!\n");
                                }
                                else{       // entre 2 prix deja classes                              
                                     printf("%d<%d<%d\n", tabtuyau[juste_inf], tabtuyau[tuyencours], tabtuyau[cherche]);
                                     tabindice[tuyencours]=cherche;
                                     tabindice[juste_inf]=tuyencours;
                                }
     }
     }
     printf("Le premier prix est : %d\n", premier);
     afftab(nbrtuyau, tabindice);
     system("pause");
}
}
 
int afftab(int nbr, int tab[]){
    int x;
    for(x=0;x<nbr;x++){
                       printf("%d\t ", tab[x]);
    }
    printf("\n\n");
}
 
int initabindice(int nbr, int tabindice[]){
    int x;
    for(x=0; x<nbr; x++){
             tabindice[x]=0;
    }
}

mon probleme est que ma fonction ne fait pas la difference entre un prix plus cher que tous ceux deja tries, et un prix ce situant entre 2 deja traités...
rien a faire, je ne trouve pas la solution ...

je debute, et je suis sur que la solution est sous mes yeux, mais je ne la trouve pas...

HELP ME

plz

j espere avoir ete clair, ca n est pas facile a expliquer...
bonne journee a vous

**theshark85** · 15/05/2006, 15h18

Moi je dirais juste, fait un dessin!!! Et je trouve assez bizzare ta méthode de tri.

Car tu dis vouloir les classer, mais est ce que ton exemple fonctionne si on prend 1|6|10|5|4|8, qu'est ce qu'il y uar dans le deuxieme tableau?

**size_one_1** · 15/05/2006, 16h00

si en entré tu as :

entré:------ indice: ----- tabeau trié: -- et en "premier" l indice 0
--1 ---------- 0 ------------ 4
--6 ---------- 1 ------------ 5
--10 --------- 2 ------------ -1
--5 ---------- 3 ------------ 1
--4 --------- 4 ------------ 3
--8 ---------- 5 ------------ 2

c est vrai que c est pas simple a comprendre.
dans le tableau trié, ca te donne l indice du prix suivant le moins elevé du tableau d origine.
mais ca te donne aussi dans le tableau trié a cet indice le suivant, ect jusqu a tomber sur -1.

**theshark85** · 15/05/2006, 16h34

Indentation dans le code. Merci pour la lisibilité!!!!!

Moi si j'ai compris ton probleme, tu veux trier du plus petit au pus grand ton tableau d'entier.
Si tu n'as pas besoin de garder ton premier tableau, pas besoin de creer un deuxieme tableau.

**theshark85** · 15/05/2006, 16h45

Voici un code de tri du plus petit au plus grand, il n'utilise qu'un tableau celui du départ. Par contre le tableau de départ est mort dans le sens ou on a trié dedans.
Voilà et pas besoin de relire tout le tableau.

Bon voilà, si tu le comprend à adapter dans ton code, sinon pose des questions et un algo de bases pour moi.

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
 
  int i,j,tempory;
  int nb; //nombre de poste du tableaua initialiser
  int tab[20]; //a initialiser
 
  for(i=0;i<nb;i++)
  {
    for(j=i;j<nb;j++)
     {
       if(tab[i]>tab[j])
       {
           tempory=tab[j];
           tab[j]=tab[i];
           tab[i]=tempory;
       }
     }
  }
  for(i=0;i<nb;i++)
      printf("%d\n",tab[i]);

**size_one_1** · 15/05/2006, 18h25

merci de vos reponse,
oui, bien sur que tu tries le tableau, mais d une, je dois absolument garder mon tableau tel quel, mais en plus si tu as, exagerons, 10 000 données, ca va mettre super longtemps, le temps de parcourir tes boucles for...
alors que moi je ne parcours le tableau qu une seule fois ...

j ai trouvé la solution finalement a force de m acharner :

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
 
void triprix(int nbrtuyau, int tabtuyau[]){
    int tabindice[nbrtuyau];
    initabindice(nbrtuyau, tabindice);
    int tuyencours;
    int premier;
    int ancienpremier;
    int dernier;
    int cherche;
    int juste_inf, jj;
    premier=0;
    for(tuyencours=0; tuyencours<nbrtuyau; tuyencours++){
                      if(tuyencours==0){   // au premier, il est forcement le moins cher et le dernier !
                                           tabindice[0]=-1;
                                           dernier=0;
                                           premier=0;
                      }
                      else{
                           if(tabtuyau[tuyencours]<=tabtuyau[premier]){     // le moins cher de tous
                                                    ancienpremier = premier;
                                                    premier = tuyencours;
                                                    tabindice[tuyencours]=ancienpremier;
                           }
                           else{
                                cherche=premier;
                                juste_inf=premier;                  
                                while(tabtuyau[cherche]<tabtuyau[tuyencours]){
                                                                                jj=juste_inf;                                                                        
                                                                               juste_inf = tabindice[cherche];
                                                                               cherche=tabindice[cherche];                                                                                                            
                                                                               if(cherche==-1)goto a;
                                }
                                if((juste_inf==-1) && (cherche==-1)){ // il est le plus cher
                                                  tabindice[dernier]=tuyencours;
                                                  tabindice[tuyencours]=-1;
                                                  dernier=tuyencours;
                                }
                                else{ // il est entre jj et cherche =>     jj < tuyencours < cherche
                                     a:                                     
                                     tabindice[tuyencours]=cherche;
                                     tabindice[jj]=tuyencours;
                                }
     }
     }
     printf("Le premier prix est : %d\n", premier);
     afftab(nbrtuyau, tabindice);
     system("pause");
}
}

voila, ca fonctionne

merci a tous,
si vous voulez des commentaires supplementaires, n hesitez pas

**miron** · 15/05/2006, 19h04

Envoyé par size_one_1

merci de vos reponse,
oui, bien sur que tu tries le tableau, mais d une, je dois absolument garder mon tableau tel quel, mais en plus si tu as, exagerons, 10 000 données, ca va mettre super longtemps, le temps de parcourir tes boucles for...
alors que moi je ne parcours le tableau qu une seule fois ...

j ai trouvé la solution finalement a force de m acharner :

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
 
void triprix(int nbrtuyau, int tabtuyau[]){
    int tabindice[nbrtuyau];
    initabindice(nbrtuyau, tabindice);
    int tuyencours;
    int premier;
    int ancienpremier;
    int dernier;
    int cherche;
    int juste_inf, jj;
    premier=0;
    for(tuyencours=0; tuyencours<nbrtuyau; tuyencours++){
                      if(tuyencours==0){   // au premier, il est forcement le moins cher et le dernier !
                                           tabindice[0]=-1;
                                           dernier=0;
                                           premier=0;
                      }
                      else{
                           if(tabtuyau[tuyencours]<=tabtuyau[premier]){     // le moins cher de tous
                                                    ancienpremier = premier;
                                                    premier = tuyencours;
                                                    tabindice[tuyencours]=ancienpremier;
                           }
                           else{
                                cherche=premier;
                                juste_inf=premier;                  
                                while(tabtuyau[cherche]<tabtuyau[tuyencours]){
                                                                                jj=juste_inf;                                                                        
                                                                               juste_inf = tabindice[cherche];
                                                                               cherche=tabindice[cherche];                                                                                                            
                                                                               if(cherche==-1)goto a;
                                }
                                if((juste_inf==-1) && (cherche==-1)){ // il est le plus cher
                                                  tabindice[dernier]=tuyencours;
                                                  tabindice[tuyencours]=-1;
                                                  dernier=tuyencours;
                                }
                                else{ // il est entre jj et cherche =>     jj < tuyencours < cherche
                                     a:                                     
                                     tabindice[tuyencours]=cherche;
                                     tabindice[jj]=tuyencours;
                                }
     }
     }
     printf("Le premier prix est : %d\n", premier);
     afftab(nbrtuyau, tabindice);
     system("pause");
}
}

voila, ca fonctionne

merci a tous,
si vous voulez des commentaires supplementaires, n hesitez pas

ne pas oublier

**size_one_1** · 15/05/2006, 20h55

exact

merci miron

**Trap D** · 15/05/2006, 21h25

Es-tu sûr de ne parcourir le tableau qu'une seule fois ???
Première boucle

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

    for(tuyencours=0; tuyencours<nbrtuyau; tuyencours++){

deuxième boucle (même si elle ne parcours pas le tableau en entier

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
while(tabtuyau[cherche]<tabtuyau[tuyencours])
{
   jj=juste_inf;
   juste_inf = tabindice[cherche];
   cherche=tabindice[cherche]; 
   if(cherche==-1)goto a;
}

Il faudrait étudier la complexité plus en détails.
D'autre part, ton goto est du plus mauvais effet.

**size_one_1** · 15/05/2006, 23h31

oui, pas reellement une seule fois, mais c est ce que j ai trouvé de plus economique...

pour le GOTO, je te l accorde, mais je n arrivais pas a distinguer de la boucle while si il est le plus cher, ou entre les deux, j obtenais des valeurs absurde ...

**theshark85** · 16/05/2006, 00h17

Chacun son école comme qui dirais.

Mais bon tu fais beaucoup de test ,de plus tu as un goto, et un while imbriqué. Moi je demande à voir si ton code est maintenable à long terme. Et si il suffit de rajouter une ligne dans ma boucle pour garder le tableau original.

Voilà et bon courage.

Tri dans un tableau et indices

C

Discussions similaires

Partager

Partager