Exercices (pc2)
Corrigé

1. Chaque élément a[i) voit passer à gauche le minimum de 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 :
   1. Une solution possible consiste à insérer successivement 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;

   2. 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;

   3. 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;

• About this document ...