Discussion :

[lcoulon]

Bonjour,

Je cherche à classer par ordre chronologique des évenements representés dans le temps en secondes depuis 1970.

Pour cela, je voudrai créer un tableau 2D pour y stocker 12 evenements à venir associés à une action à réaliser ( 1 dimension pour le temps en seconde et 1 dimension pour l'action à réaliser )

Les evenements seront insérés sans ordre chronologique, je voudrais donc classer mon tableau de la date la plus proche à la date la plus lointaine.

Le temps actuel ou un évenement à venir est representable sur 10 entiers.
( http://www.epochconverter.com )

Je pensai donc créer une dimension d'unsigned long int de longueur 12 ( valeur max = 4 294 967 295) pour y stocker 12 evenements.

et une seconde dimension de longueur 1 pour y stocker le type d'action à réaliser ( le contenu sera 1 caractère pouvant prendre une valeur de A à Z )

Code :

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

unsigned long int tableau[12][1];

Je pensai utiliser un tri "shell" comme présenté ici, pour réaliser le classement par ordre chronologique mais je ne sais pas comment faire "suivre" la 2eme dimension de mon tableau qui ne doit pas être dissociée de son heure d'evenement .

Je ne sais pas comment adapter ce type de tri à un tableau 2D, de plus est il judicieux de procéder ainsi du faire que mon tableau soit assez grand en taille ( u long int ) ?

http://www.prog-info.org/cpp/trietre...e/trishell.php

Au départ on aurait :
1298459900 , Z
1298459450 , H
1298459600 , B
1298459420 , A
...

après classement on aurait ceci :

1298459420 , A
1298459450 , H
1298459600 , B
1298459900 , Z
...

Je vous remercie de votre aide et avis,
Cordialement,

[souviron34]

D'une part, en C, time_t est directement un type permettant de rentrer ette représentation du temps (en général en 32 bits c'est un entier)

Ensuite ce serait plus simple de faire une structure :

Code :

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

1
2
3
4
5
6
typedef struct pEve {
 
    char     Type ;
    time_t  Epoch ;  
 
} Evenement ;

Et tu utilises la fonction qsort, en lui passant ton tableau de structures, et dans la fonction de tri tu compares les epochs..

[lcoulon]

Je ne voulais pas immédialtement utiliser time_c qui génère en effet une structure de int.

Si je transforme le temps en structure, la mise en ordre chronologique sera plus complexe car il faudra classer chaque entier : année, jour, mois , heure, min , sec ...

et je n'ai pas la fonction qsort car je programme en C embarqué.


Comme je débute, je pensai partir sur quelquechose de simple, d'ou mon idée de tableau 2D et de classer les 'timestamps' epoch.

Est il possible d'adapter le tri shell sur un tableau 2D ?
Si oui, pourriez vous me montrer comment faire svp ?

[souviron34]

Si je transforme le temps en structure, la mise en ordre chronologique sera plus complexe car il faudra classer chaque entier : année, jour, mois , heure, min , sec ...

Sauf que cela te prend 6 entiers min au lieu de 1...

et je n'ai pas la fonction qsort car je programme en C embarqué.

Le code source est dispo partout...

Est il possible d'adapter le tri shell sur un tableau 2D ?

Tout tri est facilement adaptable en N dimensions...

Tout est basé sur le critère de tri...

Le critère de tri est dépendant de l'application.
C'est donc à toi de le coder comme bon te semble...

[lcoulon]

je ne vous suis pas :

Sauf que cela te prend 6 entiers min au lieu de 1...

Si je garde et classe le temps sous forme d'un entier représentant les secondes depuis epoch, c'est mieux n'est ce pas ?

Quel est l'interret de le transformer avant le tri en structure ?


Pour transformer le tri 'shell' avec 1 dimension de plus, je ne vois pas trop comment faire, pourriez vous me montrer svp ?

[souviron34]

je ne vous suis pas :
...
Si je garde et classe le temps sous forme d'un entier représentant les secondes depuis epoch, c'est mieux n'est ce pas ?

Quel est l'interret de le transformer avant le tri en structure ?

Tu ne m'as pas compris..

Aucun intérêt à le transformer effectivement..

Je répondais à ceci :

Le temps actuel ou un évenement à venir est representable sur 10 entiers.

Pour transformer le tri 'shell' avec 1 dimension de plus, je ne vois pas trop comment faire, pourriez vous me montrer svp ?

Tu ne tries que sur un indice du tableau (celui représentant le temps)...

[lcoulon]

Ok on est d'accord : il vaut d'abord mieux tri les timestamps, et ensuite si besoin pour afficher les evenements de façon plus lisible on peut les transformer en structure de temps.

Tu ne tries que sur un indice du tableau (celui représentant le temps)...

Par contre, je ne vois pas comment on ajouter la 2eme dimension sans y toucher lors du tri ...

Faut il que je rajoute la definition d'un nouveau int , disons "k" dans la fonction de tri pour la 2D ?

Comme ceci ?

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
void triShell(int tableau[], const int longueur)
{
   int pas, i, j, k, memoire;
   pas = 0;

   // Calcul du pas
   while(pas<longueur)
   {
      pas = 3*pas+1;
   }

   while(n!=0) // tant que le pas est > 0
   {
      pas = pas/3;
      for(i=n; i<longueur; i++)
      {
         memoire = tableau[i][k]; // valeur à décaler éventuellement
         j = i;

         while((j>(pas-1)) && (tableau[j-pas][k];
>memoire))
         { // échange des valeurs
            tableau[j][k];  = tableau[j-pas][k];
            j = j-pas;
         }
         tableau[j][k];  = memoire;
      }
   }
}

[souviron34]

je répète que c'est beaucoup plus facile avec une structure....


Au lieu de int tableau[], tu auras struct tableau[], et dans la fonction tu auras par exemple :

Code :

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

1
2
3
4
      for(i=n; i<longueur; i++)
      {
         memoire = tableau[i].Epoch ; // valeur à décaler éventuellement
         j = i;

Pour trier un tableau 2D ça ne se fait pas comme tu mentionnes, car il faudrait boucler sur la 2ième dimension, ou alors fonctionner par adresses...

[lcoulon]

... car il faudrait boucler sur la 2ième dimension

Pourriez vous me montrer comment procéder en 2D avec un tableau je ne suis pas très à l'aise avec les structures.

[diogene]

Si tu tiens à utiliser un tableau de tableau (mais un tableau de structures serait plus clair et le traitement identique), celui-ci devra être

Code :

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

unsigned long int tableau[12][2];

Tu as ainsi un tableau de 12 cellules. Chaque cellule est un int[2] et est composée de deux éléments, un pour stocker le temps et un pour stocker l'évènement.

Pour trier le tableau :

- le critère de tri doit porter sur l'élément temps de chaque cellule : tableau[i][0] ?>? tableau[j][0]

- si l'ordre est incorrect, l'échange doit s'opérer sur deux cellules, donc échanger le contenu des tableaux tableau[i] et tableau[j]. Ou si on préfère tableau[i][0] <-> tableau[j][0] et tableau[i][1] <-> tableau[j][1]

Sinon l'algo de tri est le même que pour un tableau simple.

[lcoulon]

Est ce que ceci serait correct ?

Le paramètrage des arguments de la fonction doit également changer pour accueillir un tableau initial en 2D

A chaque déplacement on bouge également la 2ème dimension comme ceci ?
modifs pour la 2D en bleu

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
void triShell(int tableau[][], const int longueur)
{
   int pas, i, j, memoire;
   pas = 0;

   // Calcul du pas
   while(pas<longueur)
   {
      pas = 3*pas+1;
   }

   while(n!=0) // tant que le pas est > 0
   {
      pas = pas/3;
      for(i=n; i<longueur; i++)
      {
         memoire = tableau[i][0]; // valeur à décaler éventuellement
         j = i;

         while((j>(pas-1)) && (tableau[j-pas][0];
>memoire))
         { // échange des valeurs
            tableau[j][0];  = tableau[j-pas][0];
            j = j-pas;
         }
         tableau[j][0];  = memoire;
      }
   }
}

[souviron34]

c'est pas compliqué..

C'est dans tes mouvements en mémoire..

Code :

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

1
2
3
4
5
6
7
8
9
10
         memoire = tableau[i][0]; // valeur à décaler éventuellement
         j = i;
 
         while((j>(pas-1)) && (tableau[j-pas][0];
>memoire))
         { // échange des valeurs
            tableau[j][0];  = tableau[j-pas][0];
            j = j-pas;
         }
         tableau[j][0];  = memoire;

à :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
         memoire = tableau[i][0]; // valeur à décaler éventuellement
         mem1 = tableau[i][1];
         j = i;

         while((j>(pas-1)) && (tableau[j-pas][0];
>memoire))
         { // échange des valeurs
            tableau[j][0];  = tableau[j-pas][0];
            tableau[j][1];  = tableau[j-pas][1];
            j = j-pas;
         }
         tableau[j][0];  = memoire;
         tableau[j][1];  = mem1;

Mais aussi (mais je connais pas tri comme ceci donc je ne sais pas si c'est ça qu'il faut ou pas) :

quand tu fais :

Code :

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

            tableau[j][0];  = tableau[j-pas][0];

tu n'échanges pas, tu écrases...


Pour échanger il faudrait faire :

Code :

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

1
2
3
4
 
            i = tableau[j][0] ;
            tableau[j][0]  = tableau[j-pas][0];
            tableau[j][j-pas]  = i;

Enfin, il y a une erreur ici :

Code :

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

1
2
         { // échange des valeurs
            tableau[j][0];  = tableau[j-pas][0];

tu as un ";" en trop..