Durée : 3 heures.

    L'objectif de cette feuille de travaux pratiques est de comparer les  performances d'un tri rapide avec un tri à bulles.  Pour les mesures de temps de calculs, il est recommandé d'utiliser la librairie time.h. Pour les tirages voir les fonctions rand et  random. Dans la dernière partie, la commande top permet de voir  bouillir la marmite.

Dérangements.

1. Soit T une table de n  entiers. Un couple d'indices (i,j) est un dérangement de la table T si i < j et T[j] < T[i] et  on note der(T) le nombre de dérangements de T.  Clairement le tableau T est trié  si et seulement si d(T) est nul .
2. Quelle est la valeur maximale de d(T) ?
3. En déduire une définition du taux de dérangement de T.
4. Ecrire une fonction  taux(T,n) pour compter le  taux de dérangements de T.
5. Ecrire une fonction  table(n,t) pour construire une table aléatoire dont le taux de dérangement est t.

6. Vérifier le bon fonctionnement de ces deux fonctions pour n = 100000.
7. Implanter une version  TriBulles(T,n)  du tri à bulles
8. Implanter une version  TriRapide(T,n) du tri rapide.
9. Vérifier le bon fonctionnement de ces deux procédures.

10. Impanter l'algorithme décrit  ci-dessous pour comparer les deux méthodes de tris.
11. Insérer des temps de calcul et faire une représentatiion graphique.