Le problème du tri est parmi les plus élémentaires en algorithmique, mais ses ramifications peuvent être poussées.

Le but de ce TP est d'implémenter différentes méthodes standard de tri et de comparer leur efficacité.

Nous aborderons par ce TP la notion de complexité algorithmique, c'est à dire l'évaluation de l'efficacité des algorithmes, indispensable pour les comparer entre eux.

Nous travaillerons sur un tableau de nombres, par exemple :

array: list[int] = [2, 34, -4, 2, 8, 1]

Notez que les entiers pourraient être remplacés par des nombres décimaux, des chaînes de caractère (à trier par ordre alphabétique) ou même des objets complexes (à trier selon une certaine clé de l'objet). Le fonctionnement est le même.

Cela peut-être pratique pour générer de grands tableaux.

Voici comment générer un tableau de 10 nombres compris entre 0 et 100 :

import random
array = [random.randint(0, 100) for i in range(10)]

Cela sera indispensable pour évaluer nos algorithmes.

import time
start: float = time.time()
# do something
end: float = time.time()
print("Temps écoulé :", end - start)

Complétez la fonction generate_array_of_number du fichier sort/range.py pour qu'elle génère un tableau de n nombres aléatoires entre 0 et 100.

Mesurez combien de temps prend python à générer un tableau composés de :

• 1 000 000 entrées
• 2 000 000 entrées
• 3 000 000 entrées
• ...
• 10 000 000 entrées

Astuce : vous pouvez écrire les nombres avec des underscores pour mieux les lire : 1_000_000

Sur un tableur, générez un tableau permettant de visualiser le temps d'éxécution en fonction de la taille de l'entrée.

Comment vous semble évoluer la courbe ? Observez bien les différentes courbes du graphique ci-dessous. Quelle est la plus ressemblante à notre situation ? O(n) (Par ressemblance visuelle avec le graphique fourni, O(n) et O(n log n) sont acceptables. Il faut l'explication des complexités, ou un graphique exposant davantage la courbe de n log n pour répondre à la question.)

• Un algorithme de complexité O(1) a un temps d'éxécution qui ne dépend pas de la taille de l'entrée. C'est très efficace.
• Un algorithme de complexité O(n) a un temps d'éxécution qui est proportionnel à la taille du problème à résoudre. Autrement dit, multiplier la taille de l'entrée par 10 multipliera le temps d'éxécution par 10. C'est une croissance linéaire. C'est plutôt efficace.
• Un algorithme de complexité O(n²) a un temps d'éxécution qui est proportionnel au carré de la taille du problème à résoudre. Autrement dit, multiplier la taille de l'entrée par 10 multipliera le temps d'éxécution par 100 ! Ce n'est pas terrible du tout...

Observez attentivement l'animation de tri par sélection ci-dessous pour en comprendre le fonctionnement.

Écrivez en français classique ce que vous voyez. Quel est le fonctionnement ? Comment l'expliqueriez-vous à quelqu'un ? On explore un tableau à la recherche de la plus petite valeur, puis on la place au premier emplacement disponible. À la première itération, la plus petite valeur du tableau est donc placée à l'index 0. À la seconde, la valeur la plus petite trouvée entre l'index 1 et la fin du tableau est placée à l'index 1, etc.

Puis implémentez l'algorithme en python dans la fonction sort du fichier sort/selection.py. Vérifiez son bon fonctionnement en éxécutant le fichier python3 -m unittest. Le test correspondant au tri par sélection doit passer.

Mesurez le temps d'éxécution pour un tableau de :

• 1000 entrées
• 2000 entrées
• ...
• 10000 entrées

Tracez le graphique correspondant.

Quelle semble être la complexité de notre fonction de tri ? Cela est-il logique par rapport au code que vous avez implémenté ? O(n²). Cela semble logique car pour chaque entrée supplémentaire, à chaque itération (il y en a n * n-index soit presque n²) on explore une valeur de plus. Soit n² fois plus de valeurs.

Observez attentivement l'animation de tri par insertion ci-dessous pour en comprendre le fonctionnement.

Écrivez en français classique ce que vous voyez. Quel est le fonctionnement ? Comment l'expliqueriez-vous à quelqu'un ? On regarde pour chaque valeur si elle est plus petite que celle qui la précède. Si c'est le cas, elle est placée avant elle. Cela est répété jusqu'à ce que la valeur précédente soit plus petite que celle qu'on déplace.

Puis implémentez l'algorithme en python dans la fonction sort du fichier sort/insertion.py. Utilisez les tests automatiques pour vérifier votre implémentation.

Mesurez le temps d'éxécution pour un tableau de :

• 1000 entrées
• 2000 entrées
• ...
• 10000 entrées

Tracez le graphique correspondant.

Quelle semble être la complexité de notre fonction de tri ? Cela est-il logique par rapport au code que vous avez implémenté ? O(n²). En effet, pour chaque élément dans le tableau, dans le pire des cas on itère entre le début du tableau et l'index de ce nombre. Cela représente presque n² itérations pour explorer tous les éléments.

Le tri par fusion est plus complexe : il utilise en effet la récursion, c'est à dire une fonction qui s'appelle elle-même.

Exemple :

def loop_forever():
    loop_forever()

L'appel de cette fonction va entraîner une boucle infinie, car il n'y a pas de condition qui stoppe la boucle.

Voici une fonction récursive avec une "condition" pour la récursion.

def increment_until_10(i):
    if i < 10:
        return increment_until_10(i + 1)
    else:
        return i

Si on appelle increment_until_10(1), la fonction sera appelée 9 fois supplémentaires pour "compter" jusqu'à 10.

Complétez la fonction sort du fichier sort/recursion.py en suivant les instructions suivantes.

Utilisez le concept de la récursion pour calculer la factorielle du nombre passé en paramètre.

Pour rappel, la factorielle de 5 est 5 x 4 x 3 x 2 x 1 = 120.

Utilisez les tests automatiques pour vérifier votre implémentation.

Observez bien le schéma suivant : il représente le concept du tri par fusion.

Cet algorithme est de type "diviser pour régner".

Écrivez en français classique ce que vous voyez. Quel est le fonctionnement ? Comment l'expliqueriez-vous à quelqu'un ? On sépare un tableau en 2 jusqu'à ce que tous les élements soient isolés. Ensuite, on compare les élements deux à deux. Le plus petit est placé au début d'un nouveau tableau de 2 élémnts. On compare ensuite deux à deux les premières valeurs des tableaux de deux éléments. La plus petite valeur est placé au début d'un tableau de 4 éléments. On compare ensuite la première valeur du tableau de deux éléments avec la deuxième du tableau dont la première valeur a été prise. On place la plus petite de ces valeurs à la suite de la première. On itère jusqu'à avoir reconstituté un unique tableau.

Complétez la fonction sort du fichier sort/fusion.py en suivant les instructions suivantes.

Il vous faudra deux fonctions :

• sort, la fonction principale, qui sera chargée de diviser les tableaux ayant plus d'un élément, et de rappeler sort avec ces nouveaux tableaux
• merge, la fonction qui sera appelée pour fusionner deux tableaux

Utilisez les tests automatiques pour vérifier votre implémentation.

Mesurez le temps d'éxécution pour un tableau de :

• 1000 entrées
• 2000 entrées
• ...
• 10000 entrées

Tracez le graphique correspondant.

Quelle semble être la complexité de notre fonction de tri ? Cela est-il logique par rapport au code que vous avez implémenté ? O(n log n). Cet algorithme utilise la récursivité plutôt que des boucles imbriquées. Pour chaque élement supplémentaire, on va réaliser une récursion de plus, mais pas explorer de nouveau tout le tableau. C'est donc une complexité logique.

Question bonus : Y a-t-il des tailles de tableaux pour lesquelles le tri par fusion n'est pas aussi rapide que les précédents tris abordés ? Des tailles je ne sais pas, mais si le tableau fourni est déjà trié, il est plus lent que les autres.

Bien que tout cela soit fascinant, Python possède sa propre méthode de tri : sort().

Une dernière fois, analysez le temps d'exécution et découvrez si python fait mieux que nos implémentations rudimentaires ;) Il est effectivement beaucoup plus rapide !

Merci de faire une Pull Request vers ce repository.

Le nom de la PR doit contenir votre nom.

Vérifiez que votre code est conforme aux normes pep8 et aux autres critères de qualité dont nous avons parlé.

La PR doit également contenir un ou plusieurs graphiques présentant vos résultats sur la complexité des fonctions de tri.