Algorithmique TD 1

Licence M/I

28 septembre 2005

Exercice 1: On considère la procédure suivante:

    static void triSelection(int t[]){
        int n=t.length;
        for(int i=1;i<n;i++){
            int j=i, p=t[j];
            while(j>0 && p<t[j-1]){
                t[j]=t[j-1];
                j--;
            }
            t[j]=p;
        }
    }

1. Décrire ce que fait cet algorithme.
2. Quelle est sa complexité dans le pire des cas?
3. On considère fixé l'ensemble d'éléments du tableau (par exemple les entiers de 1 à n). Donner le nombre de permutations de ces n éléments, c'est-à-dire le nombre de tableaux différents de taille n qui peuvent contenir n éléments fixés distincts.
4. Le nombre d'inversions d'un tableau t est le nombre de couples d'entiers (i,j) inférieurs à n tels que i<j et t[i]>t[j]. Montrer que le nombre d'inversions de t est égal au nombre de boucles effectuées dans le tri par sélection appliqué à t.
5. On suppose que t[n] est égal au k-ième plus petit élément de t. Montrer que le nombre d'inversions de t est égal au nombre d'inversions de t privé de la case n, plus (n-k). Quel est le nombre de tableaux contenant n éléments fixés tels que la dernière case contient le k-ième plus petit élément?
6. On note i(n) le nombre moyen d'inversions d'un tableau de n éléments. Exprimer i(n) en fonction de i(n-1). En déduire i(n) et la complexité en moyenne du tri par insertion.

Exercice 2: On considère la procédure suivante:

    static void triRapide(int t[],int g, int d){//1er appel, g=0 d=t.length-1
        int n=t.length;
        int j=g, p=t[j];
        for(int i=g+1;i<=d;i++)
            if(t[i]<p){ // A
                t[j++]=t[i];
                t[i]=t[j];
            }
        t[j]=p;
        if(j-1>g) triRapide(t, g, j-1);
        if(j+1<d) triRapide(t, j+1, d);
    }

1. Décrire ce que fait cet algorithme.

2. Quelle est sa complexité dans le pire des cas?

3. Soit C(n) le nombre de fois qu'on exécute en moyenne la comparaison A lorsqu'on trie un tableau de n éléments. Montrer que C(n)=n-1+2*(C(0)+...+C(n-1))/n.

4. Conclure quant à la complexité en moyenne du tri rapide. On admettra que 1+1/2+...+1/3 est équivalent à log(n).

Exercice 3: On considère les procédures suivantes:

    static void retourne(int t[],int g, int d){
      int c;
      while(g<d){
        c=t[g]; t[g]=t[d]; t[d]=c;
        g++; d--;
      }
    }

    static void placeZero(int t[]){
      while(t[0]!=0)
        retourne(t,0,t[0]);
    }