Exercices (pc2) Corrigé

1. void Inverse(void) {
int i;
for (i=0; i< N; ++i)
  b[a[i]] = i;
}

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

3. Calcul de la table des inversions :

void Inversions(int a[]) {
int i,j;
for (i= 0; i< N; ++i) {
  inv[a[i]] =0;
  for (j= i+1; j< N; ++j)
    if (a[i]>a[j])
      inv[a[i]]= inv[a[i]]+1;
}
}

4. Voici trois solutions :

(a) Une solution possible consiste à insérer successivement i = 0, 1, …, N− 1 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 = 0; i< N; ++i) {
   /*placer i*/
     k = i - inv[i]; /*k = place de i*/
     for (j = i; j >=k+1; --j)
       a[j] = a[j-1]; /*d\'ecaler vers la droite*/
       a[k] = i;
  }

(b) On peut aussi insérer en ordre décroissant en plaçant chaque élément à sa place définitive. Le tableau a est initialisé à −1.

for (i = N-1; i>=0; --i) {
k= inv[i];
j= N-1;
while (k!= 0 || a[j]!=-1) {
 /*on recule de inv[i] places vides*/
     if (a[j]== -1) --k;
     --j;
}
a[j]= i;
}

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

for (i= N-2; i>=0; --i) {
for (j= i+1; j<N; ++j) {
  if (inv[a[j]] > i)  {
    t= a[j]; a[j]= a[j-1]; a[j-1]= t;
  }
}
}