Tris

Ce TD a pour objectif de se familiariser avec différents algorithmes pour trier les données d'un tableau.

Écrivez l'algorithme de tri à bulles vu en cours. Effectuez une à une les étapes de cet algorithme appliqué à la suite : [6,2,3,3,1,7,6]
Combien d'itérations de boucle ont été effectuées?
Donnez un exemple qui maximise le nombre d'itérations (d'inversion) pour un tableau de taille n .
Quelle est la complexité du tri à bulles?
Améliorez l'algorithme pour qu'il s'arrête s'il se rend compte que le tableau est trié en cours d'exécution.
Quels sont les tableaux qui minimisent le temps de ce nouvel algorithme?

Proposez un algorithme pour trier un tableau contenant n entiers compris entre 1 et 10 .
Calculez sa complexité.

Expliquez le principe du tri rapide en quelques mots.
Appliquez-le à la séquence suivante en prenant le premier élément comme pivot à chaque fois : 7, 2, 12, 1, 13, 3, 7, 8, 1, 5, 11, 4
Quelle est la complexité de cet algorithme?
Comment choisir le pivot pour diminuer le nombre d'appels récursifs?

Combien y a-t-il de permutations possibles sur l'ensemble des entiers compris entre 1 et n ?
On suppose qu'on a un algorithme de tri qui fonctionne en effectuant des comparaisons d'éléments deux à deux. Expliquez pourquoi cet algorithme ne peut pas avoir une complexité meilleure que n log n .