Bonus pour les plus avancés

Codez un quicksort fonctionnant sur un tableau d'entiers.

On se propose de tracer des courbes pour étudier le nombre moyen d'échanges effectués par le tri rapide. Modifiez votre programme en y intégrant une variable globale compteur incrémentée de 1 à chaque comparaison entre deux éléments du tableau.

Faites une fonction void stat(int min,int max,int step,int nbr) qui fait varier la taille des tableaux tirés au sort de min jusqu'à max en avançant de step à chaque fois. Pour chaque taille, effectuez nbr générations aléatoires de tableaux et appelez la fonction de tri. Indiquez sur la sortie standard la taille suivie du nombre moyen d'opérations effectuées, avec une ligne pour chaque taille.

Par exemple, pour min=10 max=20 step=5 nbr=10 on obtient quelque chose comme:

10 12.30
15 27.40
20 32.40

Créez ensuite un fichier plot où vous recopiez:

set output "tri.ps"
set terminal postscript
set yrange [0:10000]
plot "data", x*log(x), x*x

Ce fichier permet de tracer en format postscript les données présentes dans le fichier data et de mettre le résultat dans le fichier tri.ps, grâce au programme gnuplot.

Pour obtenir les courbes:

• Executez le programme en redirigeant la sortie dans le fichier data: a.out > data
• Lancez gnuplot sur le fichier plot: gnuplot plot
• Visualisez le résultat avec gv tri.ps

Retrouvez-vous des courbes correspondant à la complexité théorique du quicksort ?