Tri par sélection du minimum récursif

Version imprimable

En TP, on nous a demandé de faire un tri par sélection de minimum mais récursif, Mais je n'y arrive pas. Ma fonction SelectMin ne fonctionne pas et je n'arrive pas à modifier le code pour que cela marche.

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
 
const SUITELONGMAX = 50;
 
type element = integer;
type suite = record
             contenu : array[1..SUITELONGMAX] of element;
             long : 0..SUITELONGMAX;
             end;
 
 
var     s : suite;
        m, k : integer;
 
{Procedure de génération aléatoire d'une suite de longueur m}
 
procedure GenAleatSuite(m : integer; var s : suite);
var i : integer;
begin
 
  s.long:=m;
 
  for i:=1 to m do
    begin
      s.contenu[i]:=random(99);
    end;
end;
 
{Procedure d'affichage d'un suite entre les indices k et s.long}
 
procedure AfficheSuite(var s : suite);
begin
 
  AffSuiteRec(1);
  writeln;
  writeln;
 
end;
 
{Echange de deux elements de la suite}
 
procedure echange (var a,b : integer);
var temp: integer;
begin
  temp := a;
  a := b;
  b := temp;
end;
 
 
{Tri par selection du minimum}
 
procedure TriMin(var s : suite);
 
  {Fonction permettant de trouver l'indice du minimum de la suite compris    entre l'indice k et s.long }
 
  function SelectMin(k : integer ; var min : integer): integer;
 
  var result : integer;
 
  begin
 
    if (k > s.long) then SelectMin := min
    else
       begin
 
         if (s.contenu[k] < s.contenu[min]) then min := k;
         SelectMin := SelectMin(k+1,min);
 
       end;
 
  end;
 
  { Tri récursif entre l'indice k et s.long}
 
  procedure TriMinRec(k : integer);
  begin
 
    if k <= s.long then
      begin
        echange(s.contenu[k], s.contenu[SelectMin(k,k)]);
        TriMinRec(k+1);
      end;
  end;
  {Tri récursif entre 1 et s.long}
begin
  TriMinRec(1);
end;
 
  {Programme principal}
 
begin
 
  randomize;
  GenAleatSuite(10, s);
  AfficheSuite(s);
  writeln('longueur de la suite : ',s.long);
  TriMin(s);
  AfficheSuite(s);
 
end.

Si vous avez des pistes où je pourrais chercher.
Merci d'avance de votre aide.

05/11/2008, 13h37
ToTo13
Bonjour,

ta fonction selectMin à l'air correcte. Est ce que tu l'as testé indépendamment du reste.

Je pense que c'est ta fonction Echange qui est fausse :( Tu inverses deux valeurs passées en paramètres, donc cela n'opère pas sur le tableau. Si tu veux que cette fonction marche correctement, fais plutôt :
Code:

1 2 3 4 5 6 7 8 procedure echange (var a,b : integer); var temp: integer; begin temp := s.contenu[a]; s.contenu[a] := s.contenu[b]; s.contenu[b] := temp; end;
Petites remarques :
- Dans echange(s.contenu[k], s.contenu[SelectMin(k,k)]); tu peux le remplacer par echange(s.contenu[k], s.contenu[SelectMin(k,k+1)]); cela évitera un test.
- if k <= s.long then : inutile d'aller jusqu'au dernier élément inclus :(, en classant l'avant dernier, tu classes automatiquement le dernier :), donc if k < s.long then
- Juste pour info : la déclaration de fonction et procédure dans les variable d'une procédure... je trouve ça moche et très difficilement lisible. :aie:

Mae,

Citation:

Envoyé par ToTo13

- Juste pour info : la déclaration de fonction et procédure dans les variable d'une procédure... je trouve ça moche et très difficilement lisible. :aie:

C'est seulement un petit problème de mise en forme du code.

Et ce n'est pas dans les variables d'une procédure, c'est la place où on peut définir des fonctions/procédures internes, et personnellement, je trouve ça très utile pour clarifier le code.

Exemple :

- sans utiliser cette possibilité

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
procedure hello;
var
  ...
begin { hello }
  ...
  if (condition)
  then
  begin
    { traitement 1 - disons plus de 20 ou 30 lignes, avec des blocs indentés, ... }
 
    if (autreCondition)
    then
    begin
      { traitement 2 - disons plus de 20 ou 30 lignes, avec des blocs indentés, ... }
    end;
  end
  else
  begin
    { traitement 3 - disons plus de 20 ou 30 lignes, avec des blocs indentés, ... }
  end;
  ...
end; { hello }

- et en l'utilisant

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
procedure hello;
var
  ...
 
  { ---------------------------- }
 
  procedure Traitement1 ;
  begin
    { disons plus de 20 ou 30 lignes, avec des blocs indentés, ... }
  end ; { Traitement1 }
 
  { ---------------------------- }
 
  procedure Traitement2 ;
  begin
    { disons plus de 20 ou 30 lignes, avec des blocs indentés, ... }
  end ; { Traitement2 }
 
  { ---------------------------- }
 
  procedure Traitement3 ;
  begin
    { disons plus de 20 ou 30 lignes, avec des blocs indentés, ... }
  end ; { Traitement3 }
 
  { ---------------------------- }
 
begin { hello }
  ...
  if (condition)
  then
  begin
    Traitement1;
 
    if (autreCondition)
    then
    begin
      Traitement2;
    end;
  end
  else
  begin
    Traitement3;
  end;
  ...
end; { hello }

L'algorithme de la procédure hello est alors beaucoup plus facile à suivre, etc.