Exercices (pc2) Corrigé

1. Chaque élément a[i) voit passer à gauche le minimum de a[i], …, a[N] sauf si a[i] est ce minimum. Ainsi inv[i] diminue de 1 sauf s’il est nul.

2. Calcul de la table des inversions :

for i:= 1 to N do begin
inv[a[i]]:=0;
for j:= i+1 to N do
if a[i]>a[j] then inv[a[i]]:= inv[a[i]]+1;
end;

3. Voici trois solutions :

(a) Une solution possible consiste à insérer successivement i = 1, 2, …, N parmi les précédents. La place de i est i−inv[i] puisque i a à sa droite inv[i] éléments plus petits.

for i := 1 to N do {placer i}
begin
 k := i - inv[i]; {k = place de i}
 for j := i downto k+1 do
   a[j] := a[j-1]; {d\'ecaler vers la droite}
   a[k] := i
 end;

(b) On peut aussi insérer en ordre décroissant en plaçant chaque élément à sa place définitive.

for i:=N downto 1 do
begin
k:=inv[i];
j:=N;
while (k<>0) and (a[j]<>0) do begin
 {on recule de inv[i] places vides}
  j:=j-1;
  if a[j]=0 then k:=k-1;
end;
a[j]:=i
end;

(c) Une troisième solution consiste à appliquer le tri de la bulle à l’envers.

for i:= N-1 downto 1 do
for j:= i+1 to N do
if inv[a[j]>=i then
begin t:=a[j]; a[j]:=a[j-1]; a[j-1]:=t
end;