détermination des indices initiaux d'un tableau après tri

**laureat** · 20/08/2009, 11h56

Bonjour,

Le programme en c ci-dessous permet de trier les éléments d'un tableau t par ordre croissant.

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
 
#include <stdio.h>
#include <stdlib.h>
 
void selection(int *t, int n)
{
     int i, min, j , x;
     for(i = 0 ; i < n-1 ; i++)
     {
         min = i;
         for(j = i+1 ; j < n ; j++)
 
                  if(t[j] < t[min])
                  min = j;
 
 
         if(min != i)
         {
             x = t[i];
             t[i] = t[min];
             t[min] = x;
         }
     }
 
}
 
 
int main()
{
   int k, min;
   int t[6]={3,6,9,10,1,2};
   selection(t, 6);
   for(k=0;k<6;k++)
   {
   printf("%d",t[k]);
 
   }
    return 0;
}

Mon souci ce que je voudrais récupérer les indices initiales des nombres du tableau trié.
exemple :
tableau non trié : 3 6 9 10 1 2
tableau trié : 1 2 3 6 9 10
indice : 4 5 0 1 2 3
Je n'arrive pas à le faire. Un coup de pouce pourra m'aider!
Merci

**diogene** · 20/08/2009, 13h05

Tu peux créer un tableau d'indices initialisé par 0, 1, 2, 3,...
A chaque fois que tu effectues une permutation dans ta fonction de tri, tu effectues également la permutation des éléments homologues dans le tableau d'indices.

Code :

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

1
2
3
4
5
.....
             x = t[i];
             t[i] = t[min];
             t[min] = x;
             // permuter les éléments d'indices i et min dans le tableau d'indices

**plxpy** · 20/08/2009, 13h16

En regardant très rapidement ton code, je crois que les indices que tu cherches à conserver sont les valeurs successives de "min" quand tu arrives au test "min == i" (ai-je trouvé une valeur plus petite que la valeur courante ?). Ton algo les calcule donc déjà.

Reste à choisir comment fournir à l'appelant (c'est bien ce que tu veux faire ?) les indices initiaux des valeurs que tu as triées.

Tu peux, par exemple, passer un autre argument dans ta fonction "selection" (tableau d'int de même taille que ton tableau "t"), en pouvant même rafiner : ton argument est de type int * et, si l'appelant ne souhaite pas récupérer les indices, il passe "NULL", une adresse valide sinon).

Tu peux aussi retourner le tableau d'indices (tableau que tu auras obligatoirement alloué, pour le coup, dans la fonction).

Là, c'est à toi de décider.

ps : message rédigé avant d'avoir vu la réponse de diogene - les 2 réponses ne sont pas contradictoires

**laureat** · 20/08/2009, 14h18

Merci pour vos idées.
Je suis encore perplexe

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
#include <stdio.h>
#include <stdlib.h>
 
void selection(int *t, int n, int *tab_indice)
{
     int i, min, j , x, pos;
 
     for(i = 0 ; i < n-1 ; i++)
     {
         min = i;
         for(j = i+1 ; j < n ; j++)
 
                  if(t[j] < t[min])
                  min = j;
 
 
         if(min != i)
         {
             x = t[i];
 
             t[i] = t[min];
             t[min] = x;
             pos=tab_indice[i];
             tab_indice[i]=tab_indice[min];
             tab_indice[min]=pos;
 
 
         }
 
     }
 
}
 
 
int main()
{
   int k;
 
   int t[6]={3,6,9,10,1,2};
   int tab_indice[6]={0; 1, 2, 3, 4, 5};
   selection(t,tab_indice, 6);
   for(k=0;k<6;k++)
   {
   printf("%d",t[k], tab_indice[k]);
 
 
   }
    return 0;
}

Chaque petite aide est la bienvenue

**vitoubien** · 20/08/2009, 14h36

Code :

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

1
2
3
4
5
6
7
8
9
10
void selection(int *t, int *tab_indice, int n) au lieu de void selection(int *t, int n, int *tab_indice)

int tab_indice[6]={0, 1, 2, 3, 4, 5}; au lieu de    int tab_indice[6]={0; 1, 2, 3, 4, 5};

et

printf("%d %d\n",t[k], tab_indice[k]);

pour mieux visualiser ton résultat.

Tu n'avais pas essayé de compiler ?!

**laureat** · 20/08/2009, 14h43

le programme s'exécute mais ce n'est pas ce que je cherche.
comment retourner le tableau d'indices?

**vitoubien** · 20/08/2009, 14h48

C'est exactement ce que fait ton programme maintenant. Mais il semble qu'il y ait un gros quiproquo sur ce que tu appelles "le tableau d'indices" et éventuellement "retourner le tableau d'indices".

**plxpy** · 20/08/2009, 14h58

Je reprends le fil de la discussion.

J'ai dit une grosse anerie dans mon post précédent

Comme tu intervertis la valeur courante et la valeur min, la valeur "min" de ton code n'a rien/plus grand chose à voir avec les indices initiaux.

Donc, l'idée de diogene de permuter, en parallèle, valeurs et indices, est celle qu'il faut suivre.

Le reste, concernant le retour à l'appelant, reste OK

**plxpy** · 20/08/2009, 15h25

Désolé pour "le bruit" (la chaleur, l'âge, les vacances tant attendues qui tardent, ...)

Par rapport à ton code initial, en gras, les ajouts pour récupérer, au niveau de l'appelant, les indices initiaux :

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
void selection(int *t, int n, int *tab_indices)
{
     int i, min, j , x;

     if (tab_indices)
          for (i=0;i<n;i++)
               tab_indices[i] = i;

     for(i = 0 ; i < n-1 ; i++)
     {
         min = i;
         for(j = i+1 ; j < n ; j++)
             
                  if(t[j] < t[min])
                  min = j;
                
             
         if(min != i)
         {
             x = t[i];
             t[i] = t[min];
             t[min] = x;

             if (tab_indices)
             {
                 int indice = tab_indices[i];
                 tab_indices[i] = tab_indices[min];
                 tab_indices[min] = indice;
             }
         }
     }
}

**laureat** · 20/08/2009, 16h10

merci pour votre réponse.
Mon compilateur me signale des bugs (en gras)!?

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
void selection(int *t, int n, int *tab_indices)
{
     int i, min, j , x;

     if (tab_indices)
          for (i=0;i<n;i++)
               tab_indices[i] = i;

     for(i = 0 ; i < n-1 ; i++)
     {
         min = i;
         for(j = i+1 ; j < n ; j++)
             
                  if(t[j] < t[min])
                  min = j;
                
             
         if(min != i)
         {
             x = t[i];
             t[i] = t[min];
             t[min] = x;

             if (tab_indices)
             {
                 int indice = tab_indices[i];
                 tab_indices[i] = tab_indices[min];
                 tab_indices[min] = indice;
             }
         }
     }
int main()
{
   int k;

   int t[6]={3,6,9,10,1,2};
   int tab_indice[6]={0, 1, 2, 3, 4, 5};
  [B] selection(t,tab_indice, 6);[\B]
   for(k=0;k<6;k++)
   {
   printf("%d%d",t[k], tab_indice[k]);


   }
    return 0;
}

**plxpy** · 20/08/2009, 16h29

Attention à l'odre des arguments.
La fonction que je te proposais avait le prototype suivant :

void selection (int *t, int n, int *tab_indices);

et tu l'appelles comme cela :

selection(t,tab_indice,6) au lieu de selection(t,6,tab_indice)

De plus, pas besoin d'initialiser tab_indice avec 0, 1, ... 5 : c'est fait, et c'est logique, dans le fonction selection.

**laureat** · 20/08/2009, 16h43

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
#include <stdio.h>
#include <stdlib.h>

void selection(int *t,  int *tab_indices, int n)
{
     int i, min, j , x;

     if (tab_indices)
          for (i=0;i<n;i++)
               tab_indices[i] = i;

     for(i = 0 ; i < n-1 ; i++)
     {
         min = i;
         for(j = i+1 ; j < n ; j++)

                  if(t[j] < t[min])
                  min = j;


         if(min != i)
         {
             x = t[i];
             t[i] = t[min];
             t[min] = x;

             if (tab_indices)
             {
                 int indice = tab_indices[i];
                 tab_indices[i] = tab_indices[min];
                 tab_indices[min] = indice;
             }
         }
     }
}

int main()
{
   int k;

   int t[6]={3,6,9,10,1,2};
   int tab_indice;
   selection(t,tab_indice, 6);
   for(k=0;k<6;k++)
   {
   printf("%d%d",t[k], tab_indice[k]);


   }
    return 0;
}

voici les erreurs

**plxpy** · 20/08/2009, 16h59

Attention : ne pas initialiser tab_indice au départ ne veut pas dire que tu ne dois par réserver/allouer la place pour 6 éléments (c'est ce qui est néessaire pour stocker les (6) indices initiaux des valeurs triées). Ca veut simplement dire que tu n'es pas obligé de dire, explicitement que, au départ, c'est supposé valoir 0, 1, ..., 5.

Donc, dans ta fonction main, il faut bien déclarer :

int tab_indice[6]

A ce moment là, les 6 éléments valent ... ce qu'ils valent, on s'en moque : tu les passes a "selection" qui les mettra à jour comme il faut.

Ensuite, les deux erreurs relevées par le compilo sont dûes au fait que tab_indice est déclaré en int.

1ere erreur : tu passes un int alors qu'un int * est attendue
2nde erreur : l'élément d'indice 'k' d'un ... int n'a pas de sens

Si tu corriges la définition de tab_indice comme indiquée plus haut, ça passe.

**laureat** · 20/08/2009, 17h07

voici le message affiché sur la console

Normalement je dois avoir

1 2 3 6 9 10 (tableau trié) (4 5 0 1 2 3) tableau indice mais il les mélange!

**plxpy** · 20/08/2009, 17h16

Regarde ton ordre d'affichage : le programme fait ce que tu lui as demandé.

Code :

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

1
2
for (k=0;k<6;k++)
   printf("%d%d",t[k],tab_indice[k]);

t'affiche, sans espace, sans passage à la ligne, pour chaque indice, la valeur puis l'indice initial.

Ce que tu attends correspond plutôt au code suivant

Code :

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

1
2
3
4
5
6
for(k=0;k<6;k++)
   printf("%d ",t[k]);
printf("\n")
for (k=0;k<6;k++)
   printf("%d ",tab_indice[k]);
printf("\n")

**laureat** · 20/08/2009, 17h28

Parfait plxpy

C'est exactement ce que je cherche.

Je vous remercie pour ce coup d'aide "plxpy".
Merci beaucoup pour les explications!
Bon fin d'après-midi,
A la prochaine,

détermination des indices initiaux d'un tableau après tri

C

Discussions similaires

Partager

Partager