Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Shop Recherche
1966 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  [Débutant] Tri sur un tableau, totalement perdu ...

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[Débutant] Tri sur un tableau, totalement perdu ...

n°1680345
Dr Dorian
My Déjà Vu
Posté le 01-02-2008 à 12:17:08  profilanswer
 

Salut les phénos :hello:,
 
Je débute en algo, donc je me heurte à un problème qui a priori n'est pas très compliqué :D
 
Pour situer mon niveau, disons que j'ai vu les boucles Pour, TantQue, Répéter, et toutes les petites choses de ce niveau (par exemple quelques fonction comme sousChaine, etc), ainsi que les tableaux ...
 
J'ai donc l'exercice suivant :
"Ecrire l'algo de création d'un index de tri par ordre alphabétique des mots d'un tableau de 20 mots indicé de 0 à 19. L'index lui-même est un tableau, indicé de 1 à 20."
 
Disons que j'ai compris les tableaux ainsi que la notion d'index, mais j'ai du mal à travailler sur ces fichus index.
 
 
Voici le corrigé du prof :
 
Lexique :
i (entier, calculé) : indice d'itération utilisé pour remplir le tableau.
j (entier, calculé) : indice d'itération pour remplir l'index.
tabMots (tableau [0..19] de chaine, saisi) : tableau des mots.
tabIndex(tableau [1..20] de entier, saisi) : index
 
 
Algo :
 
Début
 
// Remplissage du tableau de mots
Pour i de 0 à 19
Faire   Saisir(tabMots[ i ])
FinPour
 
// Remplissage en vrac de l'index
Pour j de 1 à 20
Faire   tabIndex[j] = j-1
FinPour
 
// Tril à bulles
Pour i de 1 à 19
Faire   Pour j de i+1 à 20
         Faire   Si      tabMots[tabIndex[ i ]] > tabMots[tabIndex[j]]
                  Alors   permuter(tabIndex[ i ], tabIndex[j])
                  FinSi
         FinPour
FinPour
 
Fin
 
 
Donc, mes questions à propos du tri à bulle :D
 
La ligne "Pour i de 1 à 19", on est d'accord que c'est pour parser chaque MOT du tableau (Pas les index) ?
La ligne "Pour j de i+1 à 20", c'est pour parser chaque valeur de l'INDEX ?
 
 
 
Ne comprenant pas très très bien ce petit algo merdique (:o), j'ai voulu en faire un autre en utilisant un tri par insertion simple. J'en suis arrivé à (J'ai zappé la partie de remplissage du tableau et de l'index :
 
Début
 
Pour i de 2 à 20 // Je commence à partir de la 2nde valeur de mon index pour la comparaison
Faire      ind = i-1
            temp = tabIndex[ i ] // Je sauvegarde la valeur de mon index pour pas l'écraser plus tard
 
            // Là, je doute ... J'ai voulu dire : Tant que le mot courant est supérieur (alphabétiquement) au mot précédent, on continue, sinon on sort
            TantQue ind <= 20 et tabMot[tabIndex[ i ]] < tabMot[tabIndex[ind]]
            Faire    tabIndex[ i ] = tabIndex[ind] // J'écrase donc mon mot courant par le mot précédent
                       ind = ind - 1
            FinTantQue
 
            // Je mets à jour le mot précédent par le mot courant que j'avais sauvegardé ds ma variable avant qu'il ne soit écrasé par la précédente opération
            tabIndex[i-1] = temp
 
FinPour
Fin
 
Bref, c'est totalement foireux :/
 
Si une âme généreuse pouvait voler à mon secours :D

Message cité 1 fois
Message édité par Dr Dorian le 01-02-2008 à 13:05:50

---------------
Le topic de la cigarette électronique
mood
Publicité
Posté le 01-02-2008 à 12:17:08  profilanswer
 

n°1680352
Profil sup​primé
Posté le 01-02-2008 à 12:25:47  answer
 

Dr Dorian a écrit :


Faire   tabIndex[j] = j-1


Il y à certainement une faute ici,
je poursuis.

n°1680362
Profil sup​primé
Posté le 01-02-2008 à 12:40:01  answer
 

Cette expression,  tabMots[tabIndex[ i ]], elle est à mourir de rire de la part d'un prof.
 
En plus c'est bien définit au dessus, i et j ne sont pas du même type.
 
je poursuis  :whistle:

n°1680363
Dr Dorian
My Déjà Vu
Posté le 01-02-2008 à 12:41:16  profilanswer
 

Heu c'est bien du même type, nan ? :??:
 
entier calculé ...


---------------
Le topic de la cigarette électronique
n°1680370
Profil sup​primé
Posté le 01-02-2008 à 12:49:00  answer
 

Dr Dorian a écrit :

Heu c'est bien du même type, nan ? :??:
 
entier calculé ...


 
L'un va de 0 à 19 l'autre de 1 à 20.
Je viens d'Ada scool et c'est ainsi. De plus c'est pas très lisible ou je manque d'habitude pour ce genre de d'expression, on va dire ça  :sweat:  Ceci dis, je ne suis qu'un amateur  :jap:

n°1680385
Profil sup​primé
Posté le 01-02-2008 à 13:03:24  answer
 

Code :
  1. Début
  2.    Pour i de 2 à 20 Faire
  3.       ind = i-1
  4.       temp = tabIndex[ i ]
  5.       TantQue ind <= 20 et
  6.          tabMot[tabIndex[ i ]] < tabMot[tabIndex[ind]] Faire
  7.             tabIndex[i] = tabIndex[ind]
  8.             ind = ind - 1
  9.       FinTantQue
  10.       tabIndex[i-1] = temp
  11.    FinPour
  12. Fin


 
A la ligne 6, si I va de 2 à 20 et que index reçoit  i-1 (à la ligne 3), et est décrémenté de 1 (à la ligne 9) il ne peur jamais être supérieur ni égale à 20,
alors le teste ind <= 20 est toujours vrai et inutile.
 
A la ligne 8, l'expression tabIndex[ind] [i] référence un tableau à deux dimension, nan ? Donc une erreur c'est glissée dans l'analyse.


Message édité par Profil supprimé le 01-02-2008 à 13:47:04
n°1680386
Dr Dorian
My Déjà Vu
Posté le 01-02-2008 à 13:05:28  profilanswer
 

Yep, c'est vrai que le test sur IND sert à rien, apparement :D
 
Concernant tabIndex, c'est une erreur à cause de l'italique :D
 
Il faut lire :
tabIndex = tabIndex[ind]


---------------
Le topic de la cigarette électronique
n°1680392
Profil sup​primé
Posté le 01-02-2008 à 13:11:04  answer
 

Dr Dorian a écrit :


Concernant tabIndex, c'est une erreur à cause de l'italique :D
 
Il faut lire :
tabIndex = tabIndex[ind]


 
Yes au temps pour moi, c'est moi qui ai mal copier apparemment.

n°1680397
Profil sup​primé
Posté le 01-02-2008 à 13:13:54  answer
 

Ca, c'est le trie ar insertion en Pascal, j'en ai besoin.
 

Code :
  1. Procedure TriInsertion(n : integer ; var t : tab);
  2. var i, j : integer;
  3. var z : real;
  4. begin
  5.    for i:=2 to n do begin
  6.        z := t[i]; (* z est la valeur à insérer *)
  7.                   (* dans l'endroit approprié du tableau *)
  8.  
  9.        (* On décale toutes les valeurs du tableau < z *)
  10.        (* à droite pour vider une place pour z        *)
  11.        j := i - 1;
  12.        while (j >= 1) and (t[j] > z) do begin
  13.            t[j + 1] := t[j];
  14.            j := j - 1;
  15.        end;
  16.        (* finalement la valeur z est insérée à son emplacement adéquat *)
  17.        t[j + 1] := z;
  18.    end;
  19. end;

n°1680407
Profil sup​primé
Posté le 01-02-2008 à 13:33:51  answer
 

Yep
Je ne parviens toujours pas à lire l'algo du prof, et ne comprenant pas ce qu'est un index de tri, je ne suis pas plus avancé. Si tu m'explique un peux, peut-être que..., Tu peux cependant voir sur le code ci-dessus quelles sont les divergences avec ton propre code de tri par insertion qui n'est pas tout à fait, cependant ce que tu cherche à faire me semble t-il.


Message édité par Profil supprimé le 01-02-2008 à 13:48:09
mood
Publicité
Posté le 01-02-2008 à 13:33:51  profilanswer
 

n°1680682
Trap D
Posté le 01-02-2008 à 19:06:40  profilanswer
 

Je pense que l'utilisation de l'index permet de gagner du temps lorsque tu dois trier un tableau de données importantes (tableau de grosses structures), il est plus rapide d'échanger des données de 4/8 bytes par exemple pour des nombres que des données de 1 ko (je dis n'importe quoi pour la taille mais c'est pour te donner une idée du problème).
Je n'ai pas décortiqué l'algo du prof mais il me parait correct, je n'ai pas compris par contre pourquoi l'un des tableaux par de 0 et l'autre de 1 ???
J'aurais dit aussi  
permuter_tabindex(i ,j)  
plutôt que
permuter(tabIndex[ i ], tabIndex[j])  

n°1681403
kyntriad
Posté le 04-02-2008 à 14:00:02  profilanswer
 


=> Pour mieux comprendre l'algo tu peux te ramener a un bête tri de liste d'entiers par exemple.
 
Ca donne:
 

Code :
  1. // Remplissage du tableau d'entiers
  2. ...
  3. // Tri à bulles
  4. Pour i de 0 à nbEntier-1
  5. Faire   Pour j de i+1 à nbEntier-1
  6.          Faire   Si      tabEntier[ i ] > tabEntier[j]
  7.                   Alors   permuter(tabEntier[ i ], tabEntier[j])
  8.                   FinSi
  9.          FinPour
  10. FinPour
  11. Fin


 
Le truc de ton prof ça ajoute juste le fait qu'on trie les index et pas le tableau directement, mais c'est la même chose.


---------------
You can't start a fire with moonlight
n°1681404
kyntriad
Posté le 04-02-2008 à 14:03:33  profilanswer
 

Trap D a écrit :


Je n'ai pas décortiqué l'algo du prof mais il me parait correct, je n'ai pas compris par contre pourquoi l'un des tableaux par de 0 et l'autre de 1 ???


 
Bah c'est histoire d'habituer les élèves à jouer avec des indices.


---------------
You can't start a fire with moonlight
n°1681479
Trap D
Posté le 04-02-2008 à 15:58:56  profilanswer
 

kyntriad a écrit :

Bah c'est histoire d'habituer les élèves à jouer avec des indices.

Pas convaincu du tout  :pt1cable:

n°1681484
kyntriad
Posté le 04-02-2008 à 16:02:34  profilanswer
 

Trap D a écrit :

Pas convaincu du tout  :pt1cable:


 
Bah moi si :p
 
ça va un peu avec le côté j'tembrouille a trier les index et pas le tableau de base, et c'est un peu nécessaire de savoir jouer avec les indices pour programmer.


---------------
You can't start a fire with moonlight
n°1681511
Trap D
Posté le 04-02-2008 à 16:36:29  profilanswer
 

kyntriad a écrit :


 
Bah moi si :p
 
ça va un peu avec le côté j'tembrouille a trier les index et pas le tableau de base, et c'est un peu nécessaire de savoir jouer avec les indices pour programmer.

Autant je suis d'accord pour l'utilisation d'index différents pour une base de données, on peut avoir besoin de rechercher des données suivant des critères différents et donc là l'index est indispensable, autant faire débuter un tableau à 0 et l'autre à 1 me parait complètement artificiel.
Enfin ça n'est que mon avis et on ne va pas se battre pour ça. [:aldark]

n°1681540
kyntriad
Posté le 04-02-2008 à 17:07:04  profilanswer
 

Trap D a écrit :

Autant je suis d'accord pour l'utilisation d'index différents pour une base de données, on peut avoir besoin de rechercher des données suivant des critères différents et donc là l'index est indispensable, autant faire débuter un tableau à 0 et l'autre à 1 me parait complètement artificiel.
Enfin ça n'est que mon avis et on ne va pas se battre pour ça. [:aldark]


 
Bah vui c'est complétement artificiel on est d'accord, c'est un exercice quoi  ;)


Message édité par kyntriad le 04-02-2008 à 17:07:25

---------------
You can't start a fire with moonlight
n°1684009
matafan
Posté le 08-02-2008 à 15:18:32  profilanswer
 

L'index c'est pas juste pour embrouiller. Dans la pluspart des cas réels les tris sont faits sur un index et pas sur les vraies données, parce que déplacer un entier c'est quand même plus efficace que dépalcer des chaines de caractères ou autres structures volumineuses.

n°1684299
Trap D
Posté le 08-02-2008 à 22:41:35  profilanswer
 

matafan a écrit :

L'index c'est pas juste pour embrouiller. Dans la pluspart des cas réels les tris sont faits sur un index et pas sur les vraies données, parce que déplacer un entier c'est quand même plus efficace que dépalcer des chaines de caractères ou autres structures volumineuses.

Oui, c'est un peu ce que j'avais écrit quelques posts plus haut. [:bentley]
 

n°1684370
matafan
Posté le 09-02-2008 à 12:41:30  profilanswer
 

Oups désolé j'avais pas vu ton post :whistle:


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  [Débutant] Tri sur un tableau, totalement perdu ...

 

Sujets relatifs
[CSS] Problème pour un menu classique (niveau débutant)PHP aleatoire Problème de débutant.
initialisation de tableau à type variable[Debutant]Afficher element du tableau avec Random
Tri à bulle (forme recursif)!!!!!!!pour le débutant
Passer un tableau de pointeur au mainDebutant en C : petit problème^^
Problème pour adapter la taille d'une image à la cellule d'un tableau 
Plus de sujets relatifs à : [Débutant] Tri sur un tableau, totalement perdu ...


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR