Compétences évaluées
Concevoir des solutions algorithmiques
Traduire un algorithme dans un langage de programmation

Tous les TP seront notés (barème indicatif).

Tout TP non rendu avant la fin de la séance sera noté zéro.
Veuillez mettre clairement vos noms sur votre code source ou noms de fichiers.

Algorithmes de tri et complexité¶

Vous arrivez dans l'équipe de recherche de John McNugget, un scientifique réputé qui ne rigole pas avec la complexité algorithmique. Celui-ci vous demande de rendre votre travail sur les algorithmes de tri par insertion et tri par sélection.

Exercice 1 (5 points)¶

Tri par insertion¶

Le principe du tri par insertion est assez naturel. On prend les cartes une par une en commençant par la première.

Au départ la première est supposée à sa place. On regarde la deuxième e { width: 200px; }t on compare à la premiere, on échange si besoin. Les deux premières cartes sont donc rangées dans l'ordre.
On regarde la troisième, on compare aux précédentes en partant de la plus proche à la première et on échange si l'ordre n'est pas bon. Si l'on n'échange pas cela signifie que l'on peut passer à la carte suivante. Maintenant les 3 premières cartes sont rangées.
On regarde la 4ème carte et on la fait ainsi descendre à la position qui lui correspond...les 4 premières cartes sont rangées.
On poursuit ainsi jusqu'à la dernière carte.

Vous pouvez regarder cette vidéo et essayez de comprendre le principe du tri par insertion : https://www.numerique-sciences-informatiques.fr/videos/triInsertion.mp4

On appelle procédure, une fonction qui ne retourne rien.

Implémentez ce pseudo-code correspondant au tri par insertion :

procédure TriInsertion(tableau T, entier n)
    Pour i allant de 1 à n-1
        e ← T[i]
        j ← i
        Tant que j > 0 et T[j-1] > e
            T[j] ← T[j-1]
            j ← j-1

        T[j] ← e

Exercice 2 (5 points)¶

Tri par sélection¶

On cherche le plus petit élément du tableau et on l'échange avec celui qui est au début. Le premier élément est maintenant le plus petit
Maintenant on cherche le plus petit élément du tableau mais en partant du 2nd élément et on l'échange avec celui qui est placé deuxième. Les deux premiers éléments sont les plus petits et sont rangés.
On poursuit ainsi.

Vous pouvez regarder cette vidéo et essayer de comprendre le principe du tri par selection : https://www.numerique-sciences-informatiques.fr/videos/triSelection.mp4

Soit le pseudo-code suivant :

procédure TriSelection(tableau T, entier n)
    Pour i allant de 0 à n - 2
        min ← i
        Pour j allant de i + 1 à n-1
            Si T[j] < T[min]
                min ← j
        Si min ≠ i
            temp←T[i]
            T[i] ← T[min]
            T[min] ← temp

Implémenter l’algorithme de tri par sélection (il peut être judicieux de découper le tri en deux fonctions, dont une fonction pour trouver l'indice du minimum de la liste)

Exercice 3 (10 points)¶

Comparaison des temps d'exécution ¶

En utilisant la bibliothèque matplotlib, on souhaite construire un nuage de points avec sur l’axe des abscisses la taille de la liste et en ordonnée le temps d’exécution de chacune des fonctions correspondant au tri par insertion et tri par sélection.

L'objectif est de compléter le code ci-dessous de manière à afficher ces courbes :

import matplotlib.pyplot as plt
import timeit

# Utilisé pour être affiché sur l'axe des abscisses
nb_elements_a_trier = [i for i in range(100)]

# On a deux listes qui contiennent elles mêmes des listes
# [[0], [0, 1], ...]
donnees_cas_croissant  = []
# [[100, 99, ...], [99, 98, ...], ...]
donnees_cas_decroissant = []

for i in range(len(nb_elements_a_trier)):
    lst_croissant = [i for i in range(nb_elements_a_trier[i])]
    donnees_cas_croissant.append(lst_croissant)

    #TODO : COMPLETER AVEC LES LISTES CONTENANT DES VALEURS DECROISSANTES

# Ces listes sont utilisées pour mesurer les temps d'exécution des
# Fonctions de tri
tri_insertion_cas_croissant = []
tri_insertion_cas_decroissant = []

#TODO : COMPLETER POUR LE TRI PAR SELECTION


for i in range(len(nb_elements_a_trier)):

    tri_insertion_cas_croissant.append(
        timeit.timeit(f'tri_insertion(donnees_cas_croissant[{i}],
        len(donnees_cas_croissant[{i}]))',number=1, globals=globals()))

    tri_insertion_cas_decroissant.append(
        timeit.timeit(f'tri_insertion(donnees_cas_decroissant[{i}],
        len(donnees_cas_decroissant[{i}]))', number=1, globals=globals()))

    #TODO : COMPLETER AVEC LE TRI PAR SELECTION


plt.plot(nb_elements_a_trier, tri_insertion_cas_croissant, 'g')
plt.plot(nb_elements_a_trier, tri_insertion_cas_decroissant, 'b')
#TODO : COMPLETER AVEC LE TRI PAR SELECTION

plt.show()

Pour pouvez aussi développer votre propre version sans utiliser ce code.

Représentez également les courbes correspondant à la fonction de tri Python .sort().
Commentez l'allure de ces courbes.