Discussion :

[WhiteTigerZ]

Hola ,
voila , je veux transformer ce tri d'insertion en un tri d'insertion récursif or je ne suis pas très fort en récursivité de l'aide sera la bienvenue

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
 
procedure tri_insertion(n : integer ; var t : tab );
var
 x :integer ;
begin
 for i:= 2 to n do
  begin
   j:=i ;
    while (t[j] <t[j-1]) and (j > 1) do 
     begin
      x:=t[j] ;
      t[j]:=t[j-1];
      t[j-1]:=x; 
      j:=j-1 ;
     end; 
  end;
end;

Voila mon essai

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
 
procedure tri_insertion(n : integer ; var t : tab ; i : integer);
var
  x : integer ;
begin
 if (i >= 2) and (i <= n) then 
  begin
   j:=i ;
    while (t[j] <t[j-1]) and (j > 1) do 
     begin
      x:=t[j] ;
      t[j]:=t[j-1];
      t[j-1]:=x; 
      j:=j-1 ;
     end;
 tri_insertion(n,t,i+1);
  end;
 end;

remarque : à l'initialisation dans le programme principal
i sera remplacer par 2.
tri_insertion(n,t,2);

Merci d'avance pour votre réponse.

[katrena99]

Hola ,
voila , je veux transformer ce tri d'insertion en un tri d'insertion récursif or je ne suis pas très fort en récursivité de l'aide sera la bienvenue

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
 
procedure tri_insertion(n : integer ; var t : tab );
var
 x :integer ;
begin
 for i:= 2 to n do
  begin
   j:=i ;
    while (t[j] <t[j-1]) and (j > 1) do 
     begin
      x:=t[j] ;
      t[j]:=t[j-1];
      t[j-1]:=x; 
      j:=j-1 ;
     end; 
  end;
end;

Voila mon essai

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
 
procedure tri_insertion(n : integer ; var t : tab ; i : integer);
var
  x : integer ;
begin
 if (i >= 2) and (i <= n) then 
  begin
   j:=i ;
    while (t[j] <t[j-1]) and (j > 1) do 
     begin
      x:=t[j] ;
      t[j]:=t[j-1];
      t[j-1]:=x; 
      j:=j-1 ;
     end;
 tri_insertion(n,t,i+1);
  end;
 end;

remarque : à l'initialisation dans le programme principal
i sera remplacer par 2.
tri_insertion(n,t,2);

Merci d'avance pour votre réponse.

Il faut déjà que la version itérative soit correcte !
Le tri par insertion consiste à insérer un élément du tableau parmi ceux qui le précèdent et qui sont déjà triés. Ainsi pour le placer, on ne le permute pas avec tous les éléments qui lui sont inférieurs mais on les décale pour lui faire de la place.
Commence donc par corriger ta version itérative.

[diden138]

Ta procédure est fausse
je t'invite à regarder ça et ça
Cordialement @+

[WhiteTigerZ]

Ta procédure est fausse
je t'invite à regarder ça et ça
Cordialement @+

c'est juste

[diden138]

ok oublions le code qui est dans le lien
on va décortiquer ta procédure :

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
procedure tri_insertion(n : integer ; var t : tab );
var
 x :integer ;// i non déclaré j non déclaré 
begin
 for i:= 2 to n do
  begin
   j:=i ; j=i-1 le premier élément tu le considère comme trié :?
    while (t[j] <t[j-1]) and (j > 1) do 
     begin
      x:=t[j] ;
      t[j]:=t[j-1];
      t[j-1]:=x; 
      j:=j-1 ;
     end; 
  end;
end;

Voila
pour la version récursif qui mon sens n'a aucun avantage je ne l'a ferais pas par respect à la prog .
Cordialement @+

[WhiteTigerZ]

ok oublions le code qui est dans le lien
on va décortiquer ta procédure :

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
procedure tri_insertion(n : integer ; var t : tab );
var
 x :integer ;// i non déclaré j non déclaré 
begin
 for i:= 2 to n do
  begin
   j:=i ; j=i-1 le premier élément tu le considère comme trié :?
    while (t[j] <t[j-1]) and (j > 1) do 
     begin
      x:=t[j] ;
      t[j]:=t[j-1];
      t[j-1]:=x; 
      j:=j-1 ;
     end; 
  end;
end;

Voila
pour la version récursif qui mon sens n'a aucun avantage je ne l'a ferais pas par respect à la prog .
Cordialement @+

Pour le "j" j'ai oublié de le déclaré.
sinon le principe que j'ai utilisé est juste
en effet, c'est comme pour un jeu de cartes, on trie les premiers éléments, ensuite, pour chaque élément suivant, on regarde où il doit se situer.
Prenant l'exemple d'un prof qui a les notes de n élevés ,il prends une note quelconque supposée trier puis pour chaque copie, il regarde où elle doit se situer et ainsi de suite...
Regarde ça si tu n'es pas encore convaincu
http://asi.insa-rouen.fr/enseignants...insertion.html