Classer par ordre chronologique un tableau 2D de unsigned long int

Version imprimable

23/02/2011, 12h20
lcoulon

Classer par ordre chronologique un tableau 2D de unsigned long int

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:

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,
23/02/2011, 13h09
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:

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..

:D
23/02/2011, 13h34
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 ?
23/02/2011, 13h52
souviron34

Citation:

Envoyé par lcoulon

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...

Citation:

Envoyé par lcoulon

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

Le code source est dispo partout...

Citation:

Envoyé par lcoulon

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...
23/02/2011, 14h03
lcoulon

je ne vous suis pas :

Citation:

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 ?
23/02/2011, 14h11
souviron34

Citation:

Envoyé par lcoulon

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 :

Citation:

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

Citation:

Envoyé par lcoulon

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)...

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.

Citation:

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:

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

23/02/2011, 15h06
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:

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...
23/02/2011, 15h31
lcoulon

Citation:

... 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.
23/02/2011, 16h19
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:

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.

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:

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

c'est pas compliqué..

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

Code:

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:

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:

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

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

Pour échanger il faudrait faire :

Code:

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:

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

tu as un ";" en trop..