Tout bon livre ou cours d'algorithmique se doit d'aborder ces algorithmes fondamentaux. Les chaînes de caractères sont un cas particulier. On manipule tellement de chaînes de caractères que des algorithmes dédiés existent. Nous avons vu un exemple en TP concernant le tri de chaînes de caractères.

Comme indiqué, de nombreux problèmes peuvent se décomposer en d'autres familles de problèmes pour lesquels des algorithmes efficaces sont connus. Les algorithmes de résolutions d'équation appartiennent à une autre famille. Lors d'un cours précédent, nous avons abordé l'algorithme de l'élimination de Gauss-Jordan, qui est un exemple classique dans cette famille.

Par conséquent, rechercher un élément dans une liste est très simple en Python.

Le même opérateur in peut être utilisé sur d'autres types de collections.

Cela fonctionne aussi avec les chaînes de caractères.

Pour les dictionnaires, on peut rechercher soit par clé, soit par valeur.

Lorsque l'on travaille avec des dictionnaires, il n'est pas rare que l'on souhaite obtenir la valeur d'un clé, si elle existe, et une valeur par défaut, sinon. La méthode get rempli ce rôle.

Vous avez déjà implémenté cet algorithme. En pratique, utilisez plutôt l'opérateur in en Python. Cet algorithme peut être utile si vous implémentez vos propres structures de données.

Rappelez-vous que c'est le Grand O le plus important. Le Grand Oméga est donné à titre indicatif ici.

Utilisez plutôt la version itérative de l'algorithme.

C'est identique à une dichotomie.

Le principe est encore mieux visible sous forme d'arbre.

On va prouver la complexité en 0(log N) en établissant le rapport entre la profondeur de l'arbre et le nombre maximal de noeud dans cet arbre.

Le tableau sur la diapositive suivante illustre cette relation.

A noter qu'il s'agit là d'une valeur maximale puisque le nombre de valeurs dans l'espace de recherche n'est pas nécessairement une puissance de 2. Il nous reste à exprimer p en fonction de N.

On va utiliser cette astuce pour simplifier la somme de la diapositive précédente.

A la 2e ligne, on applique simplement la relation trouvée sur la diapositive précédente. Puis on élimine chaque composante 2 à 2. Il nous reste au final N = 2^p - 1.

On exprime donc la profondeur de l'arbre en fonction du logarithme du nombre maximal de noeud dans l'arbre binaire.

Comprendre cette preuve est importante car on peut souvent la réutiliser pour des algorithmes logarithmiques ou linéarithmiques.

Attention, il s'agit de code qui doit tenir sur une diapositive de cours. Dans un contexte industriel, il vaudrait mieux avoir 2 fonctions séparées et correctement documentées.

Les détails concernant la relation de récurrence sont considérés comme trop avancés pour ce cours. Retenez simplement qu'elle existe et offre une base mathématiques pour prouver la complexité d'algorithmes qui peuvent être exprimés de manière récursive.

Le tri "in-place" modifie la liste originale.

Le tri "in-place" est moins coûteux car il économise la copie.

Un tuple est immutable. Par conséquent, on ne peut pas lui appliquer un tri "in-place". La fonction globale sorted renvoie toujours une liste. En pratique, la fonction sorted prend en entrée un itérable.

Un set n'est pas ordonné pas définition. Par contre, un set est itérable. Par conséquent, on peut utiliser un set en entrée de sorted pour obtenir une liste triée.

Chaque caractère de la chaîne est trié lexicographiquement. Evidemment, cela prend aussi en compte les virgules et les espaces. Ces derniers apparaissent en première position.

Si on veut se limiter aux chiffres, il suffit d'éliminer les caractères qui ne nous intéressent pas.

Un dictionnaire est itérable par défaut sur ses clés. Par conséquent, la fonction sorted travaille par défaut sur les clés du dictionnaire. Il s'agit d'un tri lexicographique donc les chaînes sont renvoyées par ordre alphabétique.

Il est possible également de trier les valeurs d'un dictionnaire.

On tri par taille de sous-collection.

On spécifie les champs à utiliser pour le tri. On tri d'abord par euro, puis par centimes.

On utilise à la fois key et reverse

En utilisant "-", on dit que l'on souhaite trié dans l'ordre décroissant pour le poid. Pour le nom, on tri dans l'ordre croissant.

Les moins performants sont également les plus simples à comprendre. Nous allons commencer par ceux-là.

L'idée de cet algorithme est de mettre le plus petit élément au début à chaque itération. On parcourt tous les éléments dans la boucle externe. Dans la boucle interne, on repart du ième élément jusqu'au dernier. En d'autres termes, dans la boucle interne, on considère que les i premiers sont déjà triés. C'est bien ce que l'on fait : on recherche le plus petit élément dans la boucle interne, et on le met à la ième position.

Pour observer visuellement le tri, on utilise ici des "barres" (en réalité, de petits histogrammes). On cherche à trier les barres par taille de la plus petite à la plus grande. On voit ici dynamiquement comment fonctionne le tri sélection. On voit notamment qu'à chaque itération, la plus petite barre est déplacée à sa position finale.

L'idée est symmétrique au tri sélection : on met le plus grand élément à la fin de chaque itération. On parcourt tous les éléments dans la boucle externe. Dans la boucle interne, on repart du 1er élément et on va jusqu'à N - (i + 1). En d'autres termes, dans la boucle interne, on considère que les (i + 1) derniers sont déjà triés. C'est bien ce que l'on fait dans le test : on "pousse" les plus grandes valeurs vers la droite.

A la fin de la 1ière itération de i, la plus grande valeur est à droite. A la fin de la 2ième itération de i, la 2e grande valeur est triée. Etc. Sur le principe, on peut observer qu'il y a une symmétrie avec le tri sélection présenté précédemment.

On notera que le tri sélection a moins d'échanges. Il est donc meilleur que le tri à bulles. La raison est simple : dans le cas du tri sélection, on chercher l'indice minimum avant de faire l'échange. Dans le cas du tri à bulle, on fait des échanges à la place de réaffecter la variable min. En revanche, le tri à bulles fait l'économie de la variable min.

C'est le principe du tri d'un jeu de cartes dans notre main. On insère chaque carte au "bon endroit" une à une. Autrement dit, pour chaque carte, on l'insère à sa position finale dans la partie déjà triée de la main. Ici, la boucle externe parcourt chaque élément. La boucle interne positionne le ième élément à sa position finale dans l'intervalle [0 ; i].

A chaque étape, on voit que la partie triée devient plus importante à chaque itération sur i.

Sur le principe, c'est exactement la même chose que le tri insertion. La différence essentielle, c'est que l'on tente d'améliorer le cas moyen de l'algorithme en utilisant un coefficient h. Ce coefficient h est calculé de telle sorte qu'il soit inférieur au tier de la taille du tableau (c'est une heuristique). Les valeurs que peut prendre h sont : 1, 4, 13, 40, 121, 364, 1093... Plutôt que de travailler uniquement sur l'intervalle [0 ; i] et décrémenter j de un en un, on effectue à chaque fois des déplacements plus larges d'une valeur h. La valeur de h est réduite progressivement. Si h commence à 40, il sera ensuite : 40 // 3 = 13, puis 4, 1, et 0. Lorsque h == 1, on a précisément le tri insertion. Il s'agit de l'étape de "finition".

Les petites valeurs sont ramenées vers la gauche d'un facteur h = 13, puis 4 et enfin 1. On peut observer à certains moments un état h-sorted, ce qui signifie que la collection est triée du point de vue de h. Lorsque c'est le cas, on passe à la valeur inférieure de h pour peaufiner le tri.

La preuve d'algorithme est en dehors de la portée de ce cours.

Ici, on observe bien la symmétrie entre les algorithmes.

On peut voir ici que le principe de ces algorithmes est différent.

La dernière étape d'un tri coquille est un tri insertion. Attention : le temps d'exécution des gifs n'est pas proportionnel au temps d'exécution des algorithmes. Dans le cas général, le tri coquille a une meilleure complexité que le tri insertion. Par conséquent, le tri coquille s'exécute plus vite en moyenne en réalité. La raison pour laquelle le gif du tri coquille prend plus de temps est qu'il a été généré avec plus d'images pour mieux voir son évolution plus complexe.

On remarquera dans l'exemple que le 1er sous-ensemble contient l'ensemble des éléments plus petits que 6. Le 2e sous-ensemble contient uniquement 6. Le 3e sous-ensemble contient tous les éléments plus grands que 6.

Dans cette version de l'algorithme, la valeur de partitionnement est prise au début de l'ensemble "e". Cet algorithme est illustré sur la diapositive suivante. Globalement, on fait converger à droite l'indice i vers un élément qui devrait appartenir à l'autre partition. De même, on fait converger à gauche l'indice j vers un élément qui devrait appartenir à l'autre partition. A chaque fois que l'on trouve des pairs d'éléments se trouvant du mauvais côté, on les échange. Les 2 sous-ensembles n'ont pas besoin d'être symmétriques : on continue d'échanger les indices ensuite.

Pour plus de lisibilité, la variable "valeur" s'appelle "v" dans ce diagramme. On voit ici

Les sous-ensembles de part et d'autre de 6 forment une partition. Ici, le chiffre 6 marque le début du 2e sous-ensemble.

Les éléments qui ne sont pas plus petits que 6 vont dans le 1er sous-ensemble. 6 n'est pas plus petit que 6, donc il va dans le 2e sous-ensemble.

On a certes des boucles imbriquées, mais elles ne parcourent pas [0 ; N]. En pratique on a i qui part de 0 et j qui part de N. A chaque itération i est incrémenté au moins 1 fois et j est décrémenté au moins une fois. L'algorithme s'arrête dès que les indices se croisent, donc : - i parcourt [0 ; j_final] - j partcout [j_final ; N]

On effectue simplement quelques ajustements à l'algorithme de partitionnement que nous venons de voir. En pratique, plutôt que de supposer que l'on partitionne sur l'intervalle [0 ; N], on partitionne sur l'intervalle [debut ; fin]. Par ailleurs, on renvoie aussi l'indice j correspondant au nouvelle emplacement de la "valeur" de partition.

Pour trier un ensemble, on le partitionne en 2 sous-ensembles tels que tous les éléments du 1er sous-ensembles soient plus petits que ceux du 2e sous-ensemble. Ensuite, il suffit de trier chaque sous-ensembles.

A noter que le tri rapide est "in-place" : il ne nécessite pas de réserver un espace mémoire supplémentaire.

Chaque itération du gif montre le résultat d'une partition. Donc, dès la 1ière image, on a partitionné l'ensemble des "barres" par rapport à la 1ière. On remarquera que la progression est moins triviale que celle d'un tri à bulles, par exemple.

Quelques arrêts sur image sont utiles pour observer le partitionnement progressif, et les appels récursifs sur les sous-ensembles. Entre le placement initial et le 1er partitionnement, on voit un net changement. Entre les 4e et 10e partitions, on voit le travail effectué au tout début.

Sur des étapes plus avancées, on voit également se former puis résoudre les intervalles de partitionnement.

La preuve d'algorithme est en dehors de la portée de ce cours.

Si la valeur "v" se retrouve en premier après partitionnement, cela signifie qu'il n'existe pas de valeur plus petite, par définition. S'il n'y a pas de valeur plus petite sur cet ensemble, cette valeur est déjà triée. Le sous-ensemble suivant est constitué de tous les éléments restants. Dans ce nouveau sous-ensemble, si la valeur "v2" se retrouve en premier après partionnement, elle est déjà triée.

Même si le pire cas est rare, avoir une forte disproportion entre les sous-ensembles partitionnés peut avoir un impact négatif sur l'efficacité de l'algorithme de tri rapide.

On commence par faire une copie du tableau "a" dans "auxiliaire". Cette copie est nécessaire pour choisir les éléments depuis leur ordre d'origine. Ensuite, l'index k parcourt de la gauche vers la droite l'intervalle [debut ; fin]. Cet intervalle est coupé en deux par "milieu". L'index i parcourt de la gauche vers la droite l'intervalle [debut ; milieu]. L'index j parcourt de la gauche vers la droite l'intervalle ]milieu ; fin]. On considère que les intervalles [debut ; milieu] et ]milieu ; fin] sont triés. A chaque etape, on choisi le plus petit élément parmis [debut ; milieu] ou ]milieu ; fin]. Une fois que l'on a épuisé un intervalle, on va piocher dans l'autre.

Comme indiqué en introduction, cette implémentation est quasiment identique à tri_rapide_recursif. La seule différence, c'est que la fusion a lieu après les récursions. L'idée essentielle est que l'on fusionne 2 liste triées. Le résultat est une liste triée.

Comme pour le tri rapide, on peut se contenter d'initialiser la récursion avec l'intervalle [0, N - 1].

Plus l'algorithme avance, plus les fusions sont larges. On voit de mieux en mieux les opérations de fusion. Ceci jusqu'à la fusion ultime qui réunit les 2 intervalles [0 ; milieu] et ]milieu, N].

Dans la suite de fusions 22, 23 et 24, on voit à gauche quelques fusions sur des sous-ensembles. Cela permet de visualiser les fusions successives.

A la fin de l'algorithme, les fusions sont larges. Entre la fusion 98 et 99 (nommée "trié"), on voit le résultat typique d'une fusion sur 2 sous-ensembles triés.

Concernant la fusion, la preuve est immédiate : on a une boucle for dans l'intervalle [debut, fin + 1]. Or, au minimum, debut = 0, et au maximum fin = N. Donc la fusion a dans le pire cas un parcourt sur l'intervalle [0 ; N], dons O(N) Dans le cas du tri fusion, on sait que la dernière fusion se fait sur l'intervalle [0 ; N]. Par conséquent, on est à la fois O(N) et Oméga(N), donc Théta(N).

Nous avons montré plus tôt dans ce cours la relation entre la profondeur p et le logarithme de N. La preuve d'algorithme complète est en dehors de la portée de ce cours.

Encore une fois, la vitesse d'exécution des gifs n'est pas corrélé à l'efficacité des algorithmes mais uniquement au nombre d'étapes capturées de ces algorithmes. Même si le principe entre ces 2 algorithmes repose sur des fondements similaires, leur exécution est complètement différente.

L'un des chemins dans l'arbre binaire de toutes les permutations nous donne l'ensemble des permutations à effectuer pour trier notre collection. L'arbre binaire n'est pas forcément complet (c'est à dire qu'il n'a pas forcément d'enfant à gauche et à droite partout). On s'intéresse à la profondeur maximale p de l'arbre, puisque c'est le nombre maximal de permutations que l'on aura à faire pour trier une collection.