besoin d'aide pour le tri par insertion.

Version imprimable

16/05/2006, 19h22
argon

besoin d'aide pour le tri par insertion.
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:

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
16/05/2006, 22h27
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:

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.

Code:

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

17/05/2006, 07h50
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:

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.

Citation:

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
17/05/2006, 09h00
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.
17/05/2006, 10h04
argon
Re

Il n'aime pas non plus le tant que.
Code:

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+
17/05/2006, 10h29
cedric49fr2000

il naime pas le "tant que"

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 :D

Re

Longeur est un entier on fait

longeur<=t.length;

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

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+

17/05/2006, 16h47
Jedai

Ton algorithme est toujours faux...

--
Jedaï
17/05/2006, 16h57
argon

Bon

En quoi est faut mon algo.

A+
17/05/2006, 19h24
Trap D

Essaye le sur un petit tableau par exemple {1, 5, 2, 11, 7,3} et tu verras ...
17/05/2006, 19h36
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+

L'algo corrigé

Code:

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

17/05/2006, 21h23
Pragmateek

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

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 :oops: :oops:
pour le tri par insertion, on peut faire comme ça :
Code:

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

17/05/2006, 22h25
Pragmateek

Tout est clair ici:
http://asi.insa-rouen.fr/~fdelorme/c...insertion.html
17/05/2006, 22h31
Trap D

Tu es à Rouen ??
17/05/2006, 22h43
Pragmateek

Citation:

Envoyé par Trap D

Tu es à Rouen ??

Pas du tout, c'est juste un lien que j'ai trouvé en faisant des recherches sur les tris.
18/05/2006, 10h54
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
18/05/2006, 11h15
Matthieu Brucher

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