Objectifs  : Il existe plusieurs versions du tri rapide.  La version tri-fusion est de complexité n log n mais nécessite des structures sophistiquées (liste chainée). La version QuickSort due à C. A. R. Hoare est de complexité n log n en moyenne, quadratique dans le pire des cas. Beaucoup plus compacte que le tri-fusion  QuickSort  possède un facteur caché minimal. L'objectif de cette séance de travaux pratiques est de mettre en évidence les résultats théoriques vue en cours.

Suggestion  de lecture : chapitres Tris du Algorithmes en Langage C de R. Sedgewick.

Durée : 3 heures.

    Pour les mesures de temps de calculs,  utiliser le profileur gprof ou encore la librairie time.h. Pour les tirages aléatoires, parcourir les pages du manuels des fonctions rand et  random.  Attention aux fuites de mémoires, et pour éviter un swap désastreux, signalons que la commande top permet de voir  bouillir la marmite. Pour les représentations graphiques, voir commande gnuplot.

[ 1 ]  Implanter une fonction   int * AleasTable( int n, int p) qui retourne un tableau aléatoire de taille  n , le  second paramètre compris entre 0 et 100 sera utilisé pour produire des tables plus ou moins désordonnées.

[ 2 ] Implanter une procédure de tri par insertion  void TriInsertion(int t[], int n).

[ 3 ] Mesurer les temps de calcul. Commenter.

[ 4 ] Implanter QuickSort.

[ 5 ]  Ecrire une procédure de test pour vérifier le bon fonctionnement de votre tri rapide.

[ 6 ] Mesurer les temps de calcul du tri rapide sur des tableaux faiblement désordonnés. Commenter.

[ 7 ] Idem fortement désordonnés.

[ 8 ]   Implanter la version mixtedes tris ci-dessous. Quelle valeur de MAX donne les meilleurs résultats ?
Expliquez !

 InsertionRapide(  t  )
    debut
        si ( taille( t) < max ) alors
            TriInsertion(t)

                    sinon
                        TriRapide(t)
                    fsi
                fin