Projet : tris

Cours/Algorithmie/Problème du tri/Projet : tris

Prérequis :

On code des tris et on vérifie que nos algorithmes fonctionnent.

Mise en place

Structures

créez un dossier nommé tris où vous placerez vos fichiers
créez un projet vscode dans ce dossier
créez dans ce dossier les 2 fichiers de la trinité du code (on fera plusieurs main ensuite) :
- tris.py : où vous placez les algorithmes de tris
- test_tris.py : où vous placez les tests des algorithmes de tris

Vérifications

on vérifie que python est OK avec le terminal et avec vscode
on vérifie que le linter est actif dans vscode
on vérifie que les tests fonctionnent (en créant un test bidon dans tests_tris.py et en vérifiant que pytest et vscode le trouvent)

Tris basiques

En reprenant le code du cours :

Implémentez :

l'algorithme du tri sélection et ses tests
l'algorithme du tri insertion et ses tests

Pour les tests des algorithmes de tri, vous pouvez par exemple utiliser 3 tableaux différents :

le tableau des $3$ premiers entiers triés par ordre croissant
le tableau des $3$ premiers entiers triés par ordre décroissant
le tableau des $3$ premiers entiers mélangé (choisissez une permutation)

les deux fonctions sélection et insertion du cours sur les tris ne rendent rien. Elles modifient leurs paramètres. Pour tester de telles fonctions, il faut créer un objet dont on va tester s'il est bien modifié après être passé en paramètre de la fonction à tester. Le test suivant par exemple vérifie que la fonction sélection trie bien un tableau trié par ordre décroissant :

def test_sélection_décroissant():
    t = [3, 2, 1]
    sélection(t)
    assert t = [1, 2, 3]

Complexités min et max

Nous allons (enfin plutôt, vous allez) afficher les complexités temporelles des différents algorithmes de tri que vous avez codés.

Pour faire cela, on utilisera ce que nous avons fait pendant le projet exponentiation. Donc :

Relisez le projet exponentiation pour pouvoir rapidement trouver les informations nécessaires pour résoudre les questions suivantes.

Maintenant que vous êtes prêt, on peut commencer :

Créez un fichier mesure.py et recodez-y la fonction donne_pas de la partie mesure du temps (vous n'oublierez pas ses tests).

Pour étudier les complexités de ces deux tris, on va créer un fichier à part :

Créez un fichier main_tris_basiques.py.

Tri par sélection

Créez dans le fichier mesure.py une fonction temps_sélection(T: [int]) -> float qui, à partir d'un tableau $T$ en entrée, rend le temps mis pour exécuter cet algorithme avec le tableau donné.

solution

import time

def temps_sélection(T):
    t1 = time.perf_counter()
    sélection(T)
    t2 = time.perf_counter()

    delta = t2 - t1

    return delta

Puis on va adapter ce que l'on a fait pour l'exponentiation. Comme le tri par par sélection prend le même nombre d'opérations pour trier tous les tableaux de même taille, cela va être facile.

Vérifiez qu'il faut environ 1 seconde pour trier un tableau de taille $N = 8000$ avec le tri par sélection.

Puis on procède aux mesures :

Ajoutez au programme du fichier main_tris_basiques.py deux nouvelles listes :

la liste taille_tableau qui est le retour de la fonction donne_pas(20, 1, N) (avec $N=8000$)
la liste mesures_temps_sélection telle que mesures_temps_sélection[i] corresponde au temps mis pour exécuter le tri sélection avec le tableau list(range(taille_tableau[i]))

Affichez le tableau mesures_temps_sélection et vérifiez que le temps augmente bien lorsque la taille augmente. Précisons un peu cette augmentation :

Vérifiez que le rapport mesures_temps_sélection[i] / (taille_tableau[i]) ** 2 reste à peut prêt constant

Tri par insertion

Créez dans le fichier mesure.py une fonction temps_insertion(T: [int]) -> float qui, à partir d'un tableau $T$ en entrée, rend le temps mis pour exécuter cet algorithme avec le tableau donné.

Le tri par insertion ne prend pas le même nombre d'opérations quelque soit le tableau :

les tableaux triés par ordre croissant prendrons de l'ordre de $\mathcal{O}(n)$ opérations où $n$ est la taille du tableau
les tableaux triés par ordre décroissant prendrons de l'ordre de $\mathcal{O}(n^2)$ opérations où $n$ est la taille du tableau

Vérifiez le expérimentalement :

Ajoutez au programme du fichier main_tris_basiques.py deux nouvelles listes :

la liste taille_tableau qui est le retour de la fonction donne_pas(20, 1, N) (avec $N=8000$)
la liste mesures_temps_insertion_croissant telle que mesures_temps_insertion_croissant[i] corresponde au temps mis pour exécuter le tri insertion avec le tableau list(range(taille_tableau[i]))
la liste mesures_temps_insertion_décroissant telle que mesures_temps_instertion_décroissant[i] corresponde au temps mis pour exécuter le tri insertion avec le tableau list(range(taille_tableau[i] - 1, -1, -1))

Affichez les tableaux mesures_temps_insertion_croissant et mesures_temps_insertion_décroissant. Le premier doit augmenter moins vite que le second :

Vérifiez que :

le rapport mesures_temps_insertion_croissant[i] / (taille_tableau[i]) reste à peut prêt constant
le rapport mesures_temps_insertion_décroissant[i] / (taille_tableau[i] ** 2) reste à peut prêt constant

Complexité en moyenne

Pour connaître l'espérance de la complexité, il faut calculer la complexité en moyenne de l'algorithme. Pour cela il faut pouvoir créer un tableau aléatoire et calculer le temps mis pour le trier. Pour éviter tout cas particulier, on fait des moyennes de mesures.

Créez dans le fichier mesure.py la fonction tableau_aléatoire(n) qui rend un tableau de taille $n$ contenant les $n$ premiers entiers placé à des positions aléatoires.

Vous pourrez utiliser les techniques de création de listes classiques pour créer ces listes.

Nous allons utiliser cette fonction pour mesurer le temps moyen du tri insertion :

Ajoutez au programme du fichier main_tris_basiques.py la liste mesures_temps_insertion_moyen telle que mesures_temps_insertion_moyen[i] corresponde au temps mis pour exécuter le tri insertion avec le tableau tableau_aléatoire(taille_tableau[i]).

Le temps moyen du tri insertion doit être comparable au temps maximum. Vérifiez le :

Vérifiez que le rapport mesures_temps_insertion_décroissant[i] / mesures_temps_insertion_moyen[i] reste à peut prêt constant

Graphiques

Nous allons faire comme pour le projet exponentiation et afficher nos mesures de temps. Si vous n'aviez pas fait la partie graphique de ce projet, commencez par lire la partie consacré à Matplotlib pour installer la bibliothèque et faire son tutoriel.

En utilisant le code du projet exponentiel, affichez sur un même graphique (l'abscisse est le tableau taille_tableau) :

le tableau mesures_temps_insertion_croissant
le tableau mesures_temps_insertion_décroissant
le tableau mesures_temps_insertion_moyen

L'allure des 3 courbes est-elle conforme aux résultats théoriques de complexité ?

Tri à bulles

Implémentez le tri à bulle optimisé dans le fichier tris.py (nommez l'algorithme bulles) et ses tests dans le fichier test_tris.py.

Complexités du tri à bulle

Créez dans le fichier mesure.py une fonction temps_bulles(T: [int]) -> float qui, à partir d'un tableau $T$ en entrée, rend le temps mis pour exécuter cet algorithme avec le tableau donné.

Pour ne pas refaire la même chose que pour le calcul de la complexité en moyenne du tri par insertion, vous pourrez utiliser le fait que l'on peut passer une fonction en paramètre d'une autre !

Vous pourrez ainsi utiliser l'exemple ci-dessous qui crée une fonction de mesure de temps générique :

import random
import time

def temps_tri(fonction_tri, T):
    d = time.perf_counter()
    fonction_tri(T)
    f = time.perf_counter()

    return f - d


def temps_insertion(T):
    return temps_tri(insertion, T)  # en supposant qu'une fonction insertion existe


def temps_sélection(T):
    return temps_tri(sélection, T)  # en supposant qu'une fonction sélection existe


def temps_bulles(T):
    return temps_tri(bulles, T)  # en supposant qu'une fonction bulles existe

Les complexités maximales (pour les tableau triés par ordre décroissant) et moyenne du tri à bulles sont de $\mathcal{O}(n^2)$ opérations où $n$ est la taille du tableau et la complexité minimale (pour les tableau triés par ordre croissant) de $\mathcal{O}(n^2)$ opérations. Vérifiez le expérimentalement :

Dans un fichier main_bulles, affichez le graphique des complexités minimales, maximales et moyenne pour le tri à bulle.

Visualisation

Cette partie va vous montrer comment un tri se trie. Chaque tri est différent et vous allez le voir.

Copiez le code suivant dans un fichier main_visu.py :

import random

import matplotlib.pyplot as plt


def draw_tab(tab):
    ax.cla()  # on efface le dessin
    ax.plot(tab, 'ro')
    plt.pause(0.1)  # on pause le dessin


def insertion_visu(T):
    for i in range(1, len(T)):
        courant = T[i]
        j = i
        while (j > 0) and (courant < T[j - 1]):
            T[j] = T[j - 1]
            draw_tab(T)  # on affiche le tableau

            j -= 1
        T[j] = courant
        draw_tab(T)
    draw_tab(tab)


fig, ax = plt.subplots(figsize=(20, 5))

tab = list(range(30))
random.shuffle(tab)

print(tab)

ax.plot(tab, 'ro')
insertion_visu(tab)

print(tab)

Le code précédent modifie l'algorithme insertion pour qu'il affiche dans un graphique le tableau après chaque modification.

Exécutez le code précédent, et comprenez pourquoi il fonctionne.
Ajoutez une modification du tri par sélection pour le voir trier le même tableau et voir les différences entre les deux algorithmes.
Ajoutez une modification du tri par bulles pour le voir trier le même tableau et voir les différences entre les trois algorithmes.

Tris complexes

Implémentez (algorithmes et tests) :

l'algorithme du tri rapide et ses tests
l'algorithme du tri fusion et ses tests

N'oubliez pas que le tri fusion possède une fonction annexe combiner qu'il faut aussi tester

Les complexités des tris rapide et fusion sont identiques en moyenne.

En utilisant ce que vous avez appris avec les tris simples, vérifiez que les complexités en moyennes des tris rapide et fusion sont similaires et correspondent bien à $\mathcal{n\ln(n)}$ où $n$ est la taille du tableau.

Vous pouvez suivre ce tutoriel qui vous explique comment faire pour augmenter le nombre limite de récursions dans main_rapide.py.