Améliorer tri par sélection
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:
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:
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:
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.
