Comment visualiser l’algorithme de tri rapide ?

Le tri est un problème très classique de réorganisation des données (qui peuvent être comparées, par exemple des nombres entiers, des nombres à virgule flottante, des chaînes de caractères, etc.) d’un tableau (ou d’une liste) dans un certain ordre (croissant, non décroissant, décroissant, non croissant, lexicographique, etc.)

Il existe de nombreux algorithmes de tri différents, chacun ayant ses propres avantages et limites.

Le tri rapide

L’algorithme de tri rapide (ou Quick Sort Algorithm) est un algorithme de tri très efficace, basé sur le partitionnement d’un ensemble de données en plus petits tableaux. Un grand tableau est partitionné en deux tableaux, l’un contenant des valeurs inférieures à la valeur spécifiée, par exemple un pivot, sur la base de laquelle la partition est effectuée, et un autre tableau contenant des valeurs supérieures à la valeur du pivot.

L’algorithme de tri rapide partitionne un tableau et se fait appeler récursivement deux fois pour trier les deux sous-tableaux résultants. Cet algorithme est très efficace pour les ensembles de données de grande taille, car sa complexité moyenne et sa complexité dans le pire des cas sont respectivement O(nLogn) et O(n2).

Vous pouvez lire toute la théorie du monde sur les algorithmes de tri, mais voir ces structures en action peut vraiment vous faire avancer. Si vous êtes le genre de programmeur qui apprend mieux avec des images plutôt qu’avec des mots, consultez VisualAlgo

Avec VisualAlgo, vous pouvez créer votre propre liste de nombre et visualiser simultanément le résultat du tri et l’évolution étape par étape de l’algorithme de tri rapide (ou Quick Sort Algorithm).

VisualAlgo est un outil de visualisation d’algorithmes

VisualAlgo est un outil de visualisation d’algorithmes basé sur le web sans qu’il soit nécessaire d’installer un logiciel supplémentaire.

Il utilise les dernières technologies web : HTML5, CSS3, JavaScript.

Il permet aux utilisateurs de spécifier leurs propres entrées d’algorithme et la visualisation fonctionnera sur avec ces entrées. Il s’agit d’une collection de visualisations d’algorithmes avec une interface unifiée.

La visualisation est très efficace pour comprendre l’algorithme, et il en va de même pour comprendre la visualisation du programme. Ainsi, au fur et à mesure que la compréhension des algorithmes et de la programmation progresse, le site “VisualAlgo” permet d’apprendre simultanément les algorithmes et la programmation en visualisant le code du programme qui décrit l’algorithme en une seule fois.

Le site est interactif, vous pouvez donc choisir ou insérer des éléments dans la collection d’exemples et de regarder comment elle fonctionne visuellement.

Le coin supérieur gauche fournit généralement une explication de ce qui se passe, tandis qu’un pseudo-code apparaît en bas à droite.

C’est un très bon outil pour visualiser les concepts de structure de données et les algorithmes.

Pour aller plus loin

Pour approfondir cette notion, et développer vos compétences vous pouvez consulter cette ouvrage.

Comment visualiser l’algorithme de tri par insertion ?

Le tri est un problème très classique de réorganisation des données (qui peuvent être comparées, par exemple des nombres entiers, des nombres à virgule flottante, des chaînes de caractères, etc.) d’un tableau (ou d’une liste) dans un certain ordre (croissant, non décroissant, décroissant, non croissant, lexicographique, etc.)

Il existe de nombreux algorithmes de tri différents, chacun ayant ses propres avantages et limites.

Le tri par insertion

L’algorithme de tri par insertion (ou Insertion Sort Algorithm) considère la première valeur d’une liste comme une sous-liste triée (d’une seule valeur pour commencer). Cet algorithme itératif vérifie ensuite une à une toutes les valeurs de la liste restante. Il insère la valeur dans la sous-liste triée de l’ensemble de données à la bonne position, en déplaçant les éléments de rang supérieur vers le haut si nécessaire.

Cet algorithme n’est pas toujours très efficace et est surtout recommandé lors du tri d’une petite liste de valeurs ou d’une liste déjà presque triée.

Vous pouvez lire toute la théorie du monde sur les algorithmes de tri, mais voir ces structures en action peut vraiment vous faire avancer. Si vous êtes le genre de programmeur qui apprend mieux avec des images plutôt qu’avec des mots, consultez VisualAlgo

Avec VisualAlgo, vous pouvez créer votre propre liste de nombre et visualiser simultanément le résultat du tri et l’évolution étape par étape de l’algorithme de tri par insertion (ou Insertion Sort Algorithm)

VisualAlgo est un outil de visualisation d’algorithmes

VisualAlgo est un outil de visualisation d’algorithmes basé sur le web sans qu’il soit nécessaire d’installer un logiciel supplémentaire.

Il utilise les dernières technologies web : HTML5, CSS3, JavaScript.

Il permet aux utilisateurs de spécifier leurs propres entrées d’algorithme et la visualisation fonctionnera sur avec ces entrées. Il s’agit d’une collection de visualisations d’algorithmes avec une interface unifiée.

La visualisation est très efficace pour comprendre l’algorithme, et il en va de même pour comprendre la visualisation du programme. Ainsi, au fur et à mesure que la compréhension des algorithmes et de la programmation progresse, le site “VisualAlgo” permet d’apprendre simultanément les algorithmes et la programmation en visualisant le code du programme qui décrit l’algorithme en une seule fois.

Le site est interactif, vous pouvez donc choisir ou insérer des éléments dans la collection d’exemples et de regarder comment elle fonctionne visuellement.

Le coin supérieur gauche fournit généralement une explication de ce qui se passe, tandis qu’un pseudo-code apparaît en bas à droite.

C’est un très bon outil pour visualiser les concepts de structure de données et les algorithmes.

Pour aller plus loin

Pour approfondir cette notion, et développer vos compétences vous pouvez consulter cette ouvrage.

Comment visualiser l’algorithme de tri par sélection ?

Le tri est un problème très classique de réorganisation des données (qui peuvent être comparées, par exemple des nombres entiers, des nombres à virgule flottante, des chaînes de caractères, etc.) d’un tableau (ou d’une liste) dans un certain ordre (croissant, non décroissant, décroissant, non croissant, lexicographique, etc.)

Il existe de nombreux algorithmes de tri différents, chacun ayant ses propres avantages et limites.

Le tri par sélection

Le tri de sélection (ou Selection Sort Algorithm) est un algorithme de tri simple. Cet algorithme de tri est un algorithme de comparaison sur place dans lequel la liste est divisée en deux parties, la partie triée à l’extrémité gauche et la partie non triée à l’extrémité droite. Au départ, la partie triée est vide et la partie non triée constitue la liste complète.

Le plus petit élément est sélectionné dans le tableau non trié et échangé avec l’élément le plus à gauche, et cet élément devient une partie du tableau trié. Ce processus continue à déplacer la limite du tableau non trié d’un élément vers la droite.

Cet algorithme n’est pas adapté aux grands ensembles de données car ses complexités moyenne et pire sont de Ο(n2), où n est le nombre d’éléments.

Vous pouvez lire toute la théorie du monde sur les algorithmes de tri, mais voir ces structures en action peut vraiment vous faire avancer. Si vous êtes le genre de programmeur qui apprend mieux avec des images plutôt qu’avec des mots, consultez VisualAlgo

Avec VisualAlgo, vous pouvez créer votre propre liste de nombre et visualiser simultanément le résultat du tri et l’évolution étape par étape de l’algorithme de tri par sélection (ou Selection Sort Algorithm)

VisualAlgo est un outil de visualisation d’algorithmes

VisualAlgo est un outil de visualisation d’algorithmes basé sur le web sans qu’il soit nécessaire d’installer un logiciel supplémentaire.

Il utilise les dernières technologies web : HTML5, CSS3, JavaScript.

Il permet aux utilisateurs de spécifier leurs propres entrées d’algorithme et la visualisation fonctionnera sur avec ces entrées. Il s’agit d’une collection de visualisations d’algorithmes avec une interface unifiée.

La visualisation est très efficace pour comprendre l’algorithme, et il en va de même pour comprendre la visualisation du programme. Ainsi, au fur et à mesure que la compréhension des algorithmes et de la programmation progresse, le site “VisualAlgo” permet d’apprendre simultanément les algorithmes et la programmation en visualisant le code du programme qui décrit l’algorithme en une seule fois.

Le site est interactif, vous pouvez donc choisir ou insérer des éléments dans la collection d’exemples et de regarder comment elle fonctionne visuellement.

Le coin supérieur gauche fournit généralement une explication de ce qui se passe, tandis qu’un pseudo-code apparaît en bas à droite.

C’est un très bon outil pour visualiser les concepts de structure de données et les algorithmes.

Pour aller plus loin

Pour approfondir cette notion, et développer vos compétences vous pouvez consulter cette ouvrage.

Comment visualiser l’algorithme de tri par fusion ?

Le tri est un problème très classique de réorganisation des données (qui peuvent être comparées, par exemple des nombres entiers, des nombres à virgule flottante, des chaînes de caractères, etc.) d’un tableau (ou d’une liste) dans un certain ordre (croissant, non décroissant, décroissant, non croissant, lexicographique, etc.)

Il existe de nombreux algorithmes de tri différents, chacun ayant ses propres avantages et limites.

Le tri par fusion

Les ordinateurs sont souvent utilisés pour traiter de grandes quantités de données. Certaines des tâches pour lesquelles ils peuvent être utilisés consistent à trier les ensembles de données dans l’ordre, par exemple par ordre numérique ou alphabétique. Bien que cette tâche puisse sembler simple à réaliser, de nombreuses recherches ont été menées pour trouver l’algorithme de tri le plus efficace, en particulier lorsque l’on travaille sur de grands ensembles de données.

L’un des principaux algorithmes de tri s’appelle un tri par fusion (ou Merge Sort Algorithm) et est basé sur une approche de type “diviser pour mieux régner“.

Vous pouvez lire toute la théorie du monde sur les algorithmes de tri, mais voir ces structures en action peut vraiment vous faire avancer. Si vous êtes le genre de programmeur qui apprend mieux avec des images plutôt qu’avec des mots, consultez VisualAlgo

Avec VisualAlgo, vous pouvez créer votre propre liste de nombre et visualiser simultanément le résultat du tri et l’évolution étape par étape de l’algorithme de tri par fusion (ou Merge Sort Algorithm)

VisualAlgo est un outil de visualisation d’algorithmes

VisualAlgo est un outil de visualisation d’algorithmes basé sur le web sans qu’il soit nécessaire d’installer un logiciel supplémentaire.

Il utilise les dernières technologies web : HTML5, CSS3, JavaScript.

Il permet aux utilisateurs de spécifier leurs propres entrées d’algorithme et la visualisation fonctionnera sur avec ces entrées. Il s’agit d’une collection de visualisations d’algorithmes avec une interface unifiée.

La visualisation est très efficace pour comprendre l’algorithme, et il en va de même pour comprendre la visualisation du programme. Ainsi, au fur et à mesure que la compréhension des algorithmes et de la programmation progresse, le site “VisualAlgo” permet d’apprendre simultanément les algorithmes et la programmation en visualisant le code du programme qui décrit l’algorithme en une seule fois.

Le site est interactif, vous pouvez donc choisir ou insérer des éléments dans la collection d’exemples et de regarder comment elle fonctionne visuellement.

Le coin supérieur gauche fournit généralement une explication de ce qui se passe, tandis qu’un pseudo-code apparaît en bas à droite.

C’est un très bon outil pour visualiser les concepts de structure de données et les algorithmes.

Pour aller plus loin

Pour approfondir cette notion, et développer vos compétences vous pouvez consulter cette ouvrage.

Comment visualiser l’algorithme de tri à bulle ?

Le tri est un problème très classique de réorganisation des données (qui peuvent être comparées, par exemple des nombres entiers, des nombres à virgule flottante, des chaînes de caractères, etc.) d’un tableau (ou d’une liste) dans un certain ordre (croissant, non décroissant, décroissant, non croissant, lexicographique, etc.)

Il existe de nombreux algorithmes de tri différents, chacun ayant ses propres avantages et limites.

Le tri à bulles

L’algorithme de tri à bulles (ou Bubble Sort Algorithm) commence au début de l’ensemble de données. Il compare les deux premières valeurs, et si la première est supérieure à la seconde, il les échange. Il continue à le faire pour chaque paire de valeurs adjacentes jusqu’à la fin de l’ensemble de données. Il recommence ensuite avec les deux premiers éléments, en répétant jusqu’à ce qu’aucun échange n’ait eu lieu lors de la dernière passe.

Cet algorithme est particulièrement utile lorsque vous avez besoin de trouver les x valeurs les plus élevées d’une liste.

Vous pouvez lire toute la théorie du monde sur les algorithmes de tri, mais voir ces structures en action peut vraiment vous faire avancer. Si vous êtes le genre de programmeur qui apprend mieux avec des images plutôt qu’avec des mots, consultez VisualAlgo

Avec VisualAlgo, vous pouvez créer votre propre liste de nombre et visualiser simultanément le résultat du tri et l’évolution étape par étape algorithme de tri à bulles

VisualAlgo est un outil de visualisation d’algorithmes

VisualAlgo est un outil de visualisation d’algorithmes basé sur le web sans qu’il soit nécessaire d’installer un logiciel supplémentaire.

Il utilise les dernières technologies web : HTML5, CSS3, JavaScript.

Il permet aux utilisateurs de spécifier leurs propres entrées d’algorithme et la visualisation fonctionnera sur avec ces entrées. Il s’agit d’une collection de visualisations d’algorithmes avec une interface unifiée.

La visualisation est très efficace pour comprendre l’algorithme, et il en va de même pour comprendre la visualisation du programme. Ainsi, au fur et à mesure que la compréhension des algorithmes et de la programmation progresse, le site “VisualAlgo” permet d’apprendre simultanément les algorithmes et la programmation en visualisant le code du programme qui décrit l’algorithme en une seule fois.

Le site est interactif, vous pouvez donc choisir ou insérer des éléments dans la collection d’exemples et de regarder comment elle fonctionne visuellement.

Le coin supérieur gauche fournit généralement une explication de ce qui se passe, tandis qu’un pseudo-code apparaît en bas à droite.

C’est un très bon outil pour visualiser les concepts de structure de données et les algorithmes.

Pour aller plus loin

Pour approfondir cette notion, et développer vos compétences vous pouvez consulter cette ouvrage.

Programmation d’une liste chainée en Python

Introduction

Les listes chaînées sont une structure de données qui représente une collection linéaire de nœuds. Une caractéristique spécifique des listes chaînées est que l’ordre des nœuds n’est pas dicté par leur présence en mémoire, mais plutôt par les pointeurs que chaque nœud possède vers le nœud suivant dans la séquence.

Il existe plusieurs types de listes chaînées :

  • Listes chaînées simples – Une liste chaînée classique, comme celle présentée dans l’image ci-dessus. Les nœuds des listes à liens simples contiennent un pointeur vers le nœud suivant de la liste.
  • Listes doublement chaînées – Ce type de liste chaînée contient à la fois un pointeur vers le nœud suivant, mais aussi un pointeur vers le nœud précédent de la liste.
  • Listes chaînées circulaires – Au lieu de contenir un pointeur nul à la fin de la liste, le dernier nœud de ces listes contient un pointeur vers le premier nœud, ce qui les rend circulaires.

Nous aborderons ici la liste chainée simple.

Liste chaînée simple

Une seule liste chaînée est la plus simple de toutes les variantes de listes chaînées. Chaque nœud d’une liste chaînée unique contient un élément et une référence à l’élément suivant, et c’est tout.

Dans cette partie, nous verrons comment créer un nœud pour la liste chaînée unique ainsi que les fonctions pour les différents types d’insertion, de parcourt et de suppression.

Création de la classe de nœuds

La première chose à faire est de créer une classe pour les nœuds. Les objets de cette classe seront les nœuds réels que nous insérerons dans notre liste de liens. Nous savons qu’un nœud pour une seule liste chaînée contient l’objet et la référence au nœud suivant. Par conséquent, notre classe de nœuds contiendra deux variables membres : item et ref. La valeur de l’élément sera fixée par la valeur passée dans le constructeur, tandis que la référence sera initialement fixée à zéro.

Exécutez le script suivant :

class Node:
    def __init__(self, data):
        self.item = data
        self.ref = None

Création de la classe de liste chainée simple

Ensuite, nous devons créer une classe pour la liste des liens. Cette classe contiendra les méthodes pour insérer, supprimer, parcourir et trier la liste. Au départ, la classe ne contiendra qu’un seul membre start_node qui pointera vers le nœud de départ ou le premier nœud de la liste. La valeur de start_node sera fixée à null à l’aide du constructeur puisque la liste liée sera vide au moment de sa création. Le script suivant crée une classe pour la liste chaînée.

class LinkedList:
    def __init__(self):
        self.start_node = None

 

Nous avons maintenant créé une classe pour notre liste unique. L’étape suivante consiste à ajouter une fonction d’insertion pour insérer des éléments dans la liste chaînée. Mais avant cela, nous allons ajouter une fonction pour parcourir une liste chaînée. Cette fonction nous aidera à lire les données de notre liste.

Parcourir les éléments de la liste liée

Le code Python pour la fonction de parcours est le suivant. Ajoutez la fonction ci-dessous à la classe LinkedList que nous avons créée dans la dernière section.

def traverse_list(self):
    if self.start_node is None:
        print("Pas d'élément dans la liste")
        return
    else:
        n = self.start_node
        while n is not None:
            print(n.item , " ")
            n = n.ref

 

Voyons ce qui se passe dans la fonction ci-dessus. Cette fonction comporte deux parties principales. Premièrement, elle vérifie si la liste chaînée est vide ou non. Le code suivant vérifie cela :

    if self.start_node is None:
        print("Pas d'élément dans la liste")
        return

 

Si la liste chaînée est vide, cela signifie qu’il n’y a pas d’élément à itérer. Dans ce cas, la fonction traverse_list() affiche simplement l’instruction que la liste n’a pas d’élément.

Sinon, si la liste comporte un élément, le code suivant s’exécutera :

        n = self.start_node
        while n is not None:
            print(n.item , " ")
            n = n.ref

 

Comme nous l’avons dit précédemment, la variable de départ contiendra une référence aux premiers nœuds. Par conséquent, nous initialisons une variable n avec la variable de départ. Ensuite, nous exécutons une boucle qui s’exécute jusqu’à ce que n devienne nul. À l’intérieur de la boucle, nous imprimons l’élément stocké au nœud actuel, puis nous fixons la valeur de la variable n à n.ref, qui contient la référence au nœud suivant. La référence du dernier noeud est None puisqu’il n’y a pas de noeud après cela. Par conséquent, lorsque n devient None, la boucle se termine.

Maintenant, nous avons une fonction pour parcourir une liste chaînée, nous verrons dans un prochain article  comment nous pouvons ajouter des éléments à une  liste chaînée.

 

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.