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;