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

Version imprimable

Bonjour,

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

Code:

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

20/08/2009, 12h05
diogene
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:

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
20/08/2009, 12h16
plxpy

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

Merci pour vos idées.
Je suis encore perplexe:cry:

Code:

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

Code:

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 ?!

20/08/2009, 13h43
laureat

le programme s'exécute mais ce n'est pas ce que je cherche.
comment retourner le tableau d'indices?
20/08/2009, 13h48
vitoubien

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".
20/08/2009, 13h58
plxpy

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

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:

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;
             }
         }
     }
}

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

Code:

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;
}

20/08/2009, 15h29
plxpy

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.

Code:

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

Citation:

20/08/2009, 15h59
plxpy

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.
20/08/2009, 16h07
laureat

voici le message affiché sur la console

http://i85.servimg.com/u/f85/14/25/90/60/consol13.jpg

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!
20/08/2009, 16h16
plxpy
Regarde ton ordre d'affichage : le programme fait ce que tu lui as demandé.
Code:

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:

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")
20/08/2009, 16h28
laureat

Parfait plxpy:ccool:
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,