Discussion :

[argon]

Bonsoir tout le monde

J'épprouve quel que difficulté avec l'algo de tri par insertion.

J'ai commi une erreur.

Voici mon algo

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
pour j = 1 a longueur de j
cle = t[j]
i=j-1
 
tant que(cle<t[i])
t[]=cle
i--1
 
fin de tant que
t[i]=cle

Mon erreur se trouve i--1.

j'ai cherché pour voir ce qui n'allé pas, j'ai pas trouvé.

Pourriez vous m'aider svp, à corriger cette erreur.

Je vous en remerci d'avance.

Cordialement.

A bientôt

[Trap D]

Que cherches-tu à faire exactement ?
Le principe du tri par sélection est d'aller chercher le plus petit élément du tableau pour le mettre en premier, puis de repartir du second élément et d'aller chercher le plus petit élément du tableau restant pour le mettre en second, etc...
Dans un premier temps ton algo peut s'écrire comme ça

Code :

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

1
2
3
4
pour i de 1 à taille faire
  selectionner le plus petit element du tableau restant 
  ranger ce plus petit dans la case d'indice i
fin pour

Il rest à écrire l'algo de la recherche du plus petit élément du tableau restant
Celà se fait en initialisant la clé à la valeur du tableau à l'indice courant et à parcourir le reste du tableau, si on rencontre un élément plus petit que la clé, on mémorise cette valeur et son indice k

Une fois que la recherche est terminée, ranger ce plus petit élément dans la case i revient à intervertir les valeurs du tableaux d'indices i et k, et on passe au nombre suivant.

[Pragmateek]

Code :

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

1
2
3
4
5
6
7
pour i de 1 a taille tableau-1
   minimum<-i
   pour j de i+1 a taille tableau
      si tableau[j] < minimum alors minimum<-tableau[j]
   fin pour j
   echanger(tableau[i],minimum)
fin pour i

[argon]

Bonjour tout le monde

C'est un tri par insertion, comme on tri les carte à joué.

J'ai modiffié i--1 par i=-1.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
<div style="text-align: left;">pour j = 1 a longueur de j
cle = t[j]
i=j-1
 
tant que(cle<t[i])
t[]=cle
i=-1
 
fin de tant que
t[i]=cle</div>

En java il me sort cette erreur.

Je ne comprends pas, j'ai pour pourtant vérifié plusieurs foi dans mes cours et livres d'algo.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at Triinssertion.main(Triinssertion.java:72)

J'ignore si le problème vient de Algo ou du code.

Merci

Cordialement

A bientôt

[Matthieu Brucher]

C'est ton code, et ilm l'indique bien. Tu as un indice -1 pour un tableau, il ne doit pas apprécier !
pourquoi i=-1, j'aurai plutôt dit i-=1.

[argon]

Re

Il n'aime pas non plus le tant que.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
pour j = 1 a longueur de j
cle = t[j]
i=j-1
 
tant que(cle<t[i])
t[]=cle
i=-1
 
fin de tant que
t[i]=cle

Il s'arrette à cle<t[i] c'est i=j-1 qui fait cela.

Je ne vois vraiement pas comment contourner cela.

A+

[cedric49fr2000]

salut,

c'est clair que si tu donne ca a javac, il va pas aimer.

c'est pas du java. c'est de l'algorithmique en bon francais.

et puis personnellement je vois pas que cette erreur la .

longueur de j : ca veut dire quoi ?

ton "pour" va jusqu'ou ?

si t[j] est dans le pour, autant mettre tout de suite le dernier element de T dans "cle".

ensuite dans le tant que : t[] ca a quel sens ?

je pense pas que le i=-1 soit le vrau probleme .

au plaisir , cedric

[argon]

Re

Longeur est un entier on fait

longeur<=t.length;

j'espere que ce sera plus clair ci-dessous.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
pour j <= 1 a  n
cle <= t[j]
i<=j-1
 
tant que(cle<t[i])
t[i+1]=t[i]
i<=-1
 
fin de tant que
t[i]<=cle
 
fin pour

A+

[Jedai]

Ton algorithme est toujours faux...

--
Jedaï

[argon]

Bon

En quoi est faut mon algo.

A+

[Trap D]

Essaye le sur un petit tableau par exemple {1, 5, 2, 11, 7,3} et tu verras ...

[argon]

Je m'aperçois que les prof raconte n'importe quoi et que les livres c'est pareille.

Avec ce que tu ma données, ca fait la même erreur.

A+

[Trap D]

L'algo corrigé

Code :

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

1
2
3
4
5
6
7
pour i de 1 a taille tableau-1
   minimum<-i
   pour j de i+1 a taille tableau
      si tableau[j] < tableau[minimum] alors minimum <-j
   fin pour j
   echanger(tableau[i],tableau[minimum])
fin pour i

[Pragmateek]

En effet je n'ai pas relu.
Merci de l'avoir fait.

[Trap D]

De toute façon, pour moi c'est pas mieux, argon recherche le tri par insertion et je lui ai expliqué le tri par sélection
pour le tri par insertion, on peut faire comme ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
pour j = 1 a longueur de j
  cle = t[j]
  i=j
 
  // il faut faire attention de ne pas dépasser les limites du tableau
  tant que(i > 0 && cle<t[i-1])
     // on remonte l'element
     t[i]=t[i-1]
     i = i - 1
  fin de tant que
  t[i]=cle
fin pour

[Pragmateek]

Tout est clair ici:
http://asi.insa-rouen.fr/~fdelorme/c...insertion.html

[Trap D]

Tu es à Rouen ??

[Pragmateek]

Tu es à Rouen ??

Pas du tout, c'est juste un lien que j'ai trouvé en faisant des recherches sur les tris.

[argon]

Merci beaucoup pour votre aide

Maintenant, je vais m'attaquer au tri par permutation.

Si, j'ai bien compris.

un algo est un langage, et il faut traduire ce langage pour faire le programme.

A bientôt

[Matthieu Brucher]

Un algorithme est une suite d'actions à accomplir. Un programme est l'implémentation de cet algorithme dans un langage.