Discussion :

[katrena99]

Je désire vous parler du tri par sélection.
J'explique un peu le fonctionnement pour ceux qui ne connaissent pas ou qui ont oublié; le tri par sélection consiste à sélectionner le plus petit (ou plus grand selon l'ordre croissant ou décroissant avec lequel on veut trier le tableau) élément dans la partie non triée et le mettre à sa place en permutant avec la case qui le renferme.

Voici son algorithme :

Code :

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

1
2
3
4
5
6
7
procedure triselection(var table:tab; n:integer);
var ind_max,i:integer;
 
begin
for i:=1 to (n-1) do
	if max(table,i,n) <> i then permutation(table[max(table,i,n)],table[i]);
end;

La fonction max retourne l'indice du maximum d'une partie d'un tableau, cernée par les cases d (pour début) et f. Cf optionellement le code.

La procédure permutation permute les valeurs de deux éléments quelconques.


On nous propose de l'améliorer en plaçant le plus grand et le plus petit en même temps. C'est à dire que lorsqu'on place le plus petit parmi les non triés à la première case on place le plus grand à la dernière, quand on place le second dans la 2e case on place aussi l'avant dernier dans l'avant dernière...

Ce qui donne ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
procedure triselection(var table:tab; n:integer);
var ind_max,i:integer;
 
begin
for i:=1 to (n div 2) do
	begin
	if max(table,i,n+1-i) <> i then permutation(table[max(table,i,n)],table[i]);
	if min(table,i,n+1-i) <> n+1-i then permutation(table[min(table,i,n+1-i)],table[n+1-i]);
	end;
end;

Code en entier si besoin :

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
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
program pp;
uses wincrt;
type tab=array[1..50] of integer;
 
procedure remptab(var table:tab;n:integer);
var i:integer;
begin
for i:=1 to n do
       begin
       write('valeur numéro ', i,' du tableau : ');
       read(table[i]);
       end;
writeln;
for i:=1 to n do write(table[i]:6);
end;
 
function max(table:tab; d,f:integer):integer;
var j,ind:integer;
begin
ind:=d;
for j:=d+1 to f do if table[j]>table[ind] then ind:=j;
max:=ind
end;
 
function min(table:tab; d,f:integer):integer;
var j,ind:integer;
begin
ind:=d;
for j:=d+1 to f do if table[j]<table[ind] then ind:=j;
min:=ind
end;
 
procedure permutation(VAR v,v2:integer);
var e:integer;
begin
e:=v;
v:=v2;
v2:=e;
end;
 
procedure triselection(var table:tab; n:integer);
var ind_max,i:integer;
 
begin
for i:=1 to (n div 2) do
	begin
	if max(table,i,n+1-i) <> i then permutation(table[max(table,i,n)],table[i]);
	if min(table,i,n+1-i) <> n+1-i then permutation(table[min(table,i,n+1-i)],table[n+1-i]);
	end;
end;
 
 
var t:tab; n,i:integer;
begin
repeat
	write('n ?  ');
	read(n)
until n in [2..30];
remptab(T,n);
writeln;
triselection(t,n);
for i:=1 to n do write(t[i]:6);
end.

La question maintenant est : a-t-on amélioré l'algorithme du tri ? Expliquez s'il vous plaît.

Merci.

[Ultima]

Bonjour,
Je te propose de faire le calcule de min et de max en un seul appel, petite optimisation, mais optimisation quand-même.
Autre chose, tu utilise comme type CARDINAL, ou mieux, BYTE, pour les indices (économie de mémoire).

Code :

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

1
2
3
4
5
6
7
8
9
10
procedure ind_min_max(t : TABLEAU; a,b : INDICE; out min,max : INDICE);
var
 k : INTEGER;
Begin
 min:= a;    max:= b;
 for k:= succ(a) to b do begin
   if t[k] < t[min] then min:= k;
   if t[k] > t[max] then max:= k;
 end;
End;

[katrena99]

Bonjour,
Je te propose de faire le calcule de min et de max en un seul appel, petite optimisation, mais optimisation quand-même.
Autre chose, tu utilise comme type CARDINAL, ou mieux, BYTE, pour les indices (économie de mémoire).

Code :

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

1
2
3
4
5
6
7
8
9
10
procedure ind_min_max(t : TABLEAU; a,b : INDICE; out min,max : INDICE);
var
 k : INTEGER;
Begin
 min:= a;    max:= b;
 for k:= succ(a) to b do begin
   if t[k] < t[min] then min:= k;
   if t[k] > t[max] then max:= k;
 end;
End;

Merci pour la réponse.
Je suis d'accord pour byte pour les indices mais enfin ça dépend de la taille du tableau... Par contre, min et max dans une procédure au lieu de deux fonctions, j'ai seulement l'impression que ça fait gagner quelque chose que ce soit temps ou mémoire, je ne suis pas sûr. Je voudrais avoir l'explication de plus expérimentés tels que Alcatîz, Wormful_sickfoot ou the_who (pour en citer, il y en a bcp)...
Revenons à ta procédure, il y a tout d'abord une erreur d'inattention.

Code :

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

1
2
min:= a;    max:= b;
 for k:= succ(a) to b

si le maximum est la case d'indice a ça ne marche pas...
sinon pour améliorer on pourrait ajouter "else if" comme ça on ne fait pas de test inutile.

Code :

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

1
2
3
4
5
6
7
8
procedure ind_min_max(t : TABLEAU; a,b : INDICE; out min,max : INDICE);
var
 k : INTEGER;
Begin
 min:= a;    max:= a;
 for k:= succ(a) to b do
        if t[k] < t[min] then min:= k else if t[k] > t[max] then max:= k;
End;

PS : j'ai compris que out signifiait var mais c'est quel langage s'il te plaît ?

[Ultima]

Bonjour,
J’ais en effet omis de spécifier que dans ma fonction, il fallait que l’utilisateur mette les indices dans l’ordre, c'est-à-dire que a<=b ;
Quand au if then eslse if, tu as tout a fait raison (katrena99), mais j’avoue que je trouvais que ça faisait plus "beau" avec les deux if successifs.

[katrena99]

b>=a c'est sûr mais t[b]>=t[a] n'est pas garanti puisque le tableau n'est pas encore trié d'ailleurs c'est ce que fait le programme hehe.
tu n'as pas répondu à ça : "PS : j'ai compris que out signifiait var mais c'est quel langage s'il te plaît ?"

[Ultima]

Bonjour,
out n’est pas du tout la même chose que var ;
les variables out sont des variables qui n’ont pas encore été initialisées, c’est la procédure qui va leur affecter une valeur.
Je crois que c’est du Delphi, je compile sur FPC, et pour que ça compile j’utilise le paramètre –Mdelphi sur la ligne de commande.
Si non il y a la directive "$MODE DELPHI".

Voici ma version : Je suis persuadé qu’on peut l’optimiser encore, mais je signale que j’ai commencé le pascal en octobre 2006 (avant je faisais du ti-Basique lol, je sais que c’est nulle, lol)

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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
type
  INDICE  = 1..50;
  TABLEAU = array [INDICE] of INTEGER;
 
procedure permutation(var v,v2:INTEGER);
begin
  v:=  v2+v;        // Katrena fait trois affectations, j'en fais toujours trois, mais sans variable en plus
  v2:= v-v2;
  v:=  v-v2;
end;
 
procedure ind_min_max(t : TABLEAU; a,b : INDICE; out min,max : INDICE); // Condition: a <= b
var
  i : INTEGER;
Begin
  min:= a;    max:= b;
  for i:= succ(a) to b do
    if      t[i] < t[min] then min:= i
    else if t[i] > t[max] then max:= i;
End;
 
procedure triselection(var t : TABLEAU, n : INDICE);
var
  i, idmin, idmax : INDICE;
Begin
  for i:= 1 to (n div 2) do begin
    ind_min_max(t, i,(n-i+1), idmin, idmax);  // je fais appel (n div 2)fois à ind_min_max, tandis que katrena faisait (2*(n div 2))*2 appel à min et max
                                              // Personnellement katrena99, je crois que c'est plus éfficace.
    permutation(t, i, idmin);
    permutation(t, (n-i+1), idmax);
  end;
End;

[katrena99]

Bonjour,
out n’est pas du tout la même chose que var ;
les variables out sont des variables qui n’ont pas encore été initialisées, c’est la procédure qui va leur affecter une valeur.
Je crois que c’est du Delphi, je compile sur FPC, et pour que ça compile j’utilise le paramètre –Mdelphi sur la ligne de commande.
Si non il y a la directive "$MODE DELPHI".

Voici ma version : Je suis persuadé qu’on peut l’optimiser encore, mais je signale que j’ai commencé le pascal en octobre 2006 (avant je faisais du ti-Basique lol, je sais que c’est nulle, lol)

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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
type
  INDICE  = 1..50;
  TABLEAU = array [INDICE] of INTEGER;
 
procedure permutation(var v,v2:INTEGER);
begin
  v:=  v2+v;        // Amine fait trois affectations, j'en fais toujours trois, mais sans variable en plus
  v2:= v-v2;
  v:=  v-v2;
end;
 
procedure ind_min_max(t : TABLEAU; a,b : INDICE; out min,max : INDICE); // Condition: a <= b
var
  i : INTEGER;
Begin
  min:= a;    max:= b;
  for i:= succ(a) to b do
    if      t[i] < t[min] then min:= k
    else if t[i] > t[max] then max:= k;
End;
 
procedure triselection(var t : TABLEAU, n : INDICE);
var
  i, idmin, idmax : INDICE;
Begin
  for i:= 1 to (n div 2) do begin
    ind_min_max(t, i,(n-i+1), idmin, idmax);  // je fais appel (n div 2)fois à ind_min_max, tandis que Amine faisait (2*(n div 2))*2 appel à min et max
                                              // Personnellement katrena99, je crois que c'est plus éfficace.
    permutation(t, i, idmin);
    permutation(t, (n-i+1), idmax);
  end;
End;

Qui est Amine ? lol

Je suis en train de sourire tellement les changements que tu as apporté à permutation m'ont plu. Je trouve l'idée très ingénieuse. Seulement, est-ce vraiment une amélioration ? Car si on est sûr d'utiliser moins d'espace mémoire, on fait 3 fois plus d'opérations bien que l'on fasse autant d'affectations (3). C'est à dire, comment est-ce qu'on calcule l'overall gain de mémoire contre gain de traitement ? A part ça, je souris toujours lol.

Concernant les changements que tu as apporté à la procédure triselection, tu as remplacé

Code :

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

if max(table,i,n+1-i) <> i then permutation(table[max(table,i,n)],table[i]);

par

Code :

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

permutation(t, i, idmin)

l'appel ne correspond pas à celui de la procédure telle que tu l'as écrite mais on s'en fout, ce n'est qu'une inattention... ce que j'aimerais savoir c'est : le test "si i <> max(table, i, n+1-i)" vaut-il une affectation dans le sens temps processeur et mémoire nécessaire ? Je m'exprime très mal j'en suis conscient mais rien à faire, je n'arrive pas à trouver de meilleurs mots.
Concernant la procédure ind_min_max, il y a une erreur de raisonnement que je t'ai déjà fait remarquer. Quand tu dis que la condition est que a<=b je suis d'accord mais cela ne veut pas dire que la case a renferme une valeur plus petite que celle de b. Conclusion, tu ne fais pas le test pour a alors que rien ne garantit que ce n'est pas le maximum du tableau.

Et enfin, pour out j'ai compris merci. Mais c'est exactement var en algorithmique sauf que var ne veut pas dire que ces variables n'ont pas été initialisées. Je ne sais pas trop, moi je suis en 1ère année Sciences de l'Informatique au lycée (Bac -1).

Merci beaucoup.

[Ultima]

Bonjour,
Voici permutation, comme il est chez, moi.

Code :

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

1
2
3
4
5
6
7
8
    procedure Permutation(var t : TABLEAU; const a,b : INDICE);
    var
      e : INTEGER;
    Begin
      e:= t[a];
      t[a]:= t[b];
      t[b]:= e;
    End;

[Ultima]

Bonjour,
Je lisait d’autres algos en même temps que le tien et j’ai fini par m’emailer les pinceaux, faut dire qu’il faisait tard et que j’été pas très éveillé. Désolé.