Les structures de données constituent l'épine dorsale de l'informatique, définissant la manière dont les informations sont organisées pour une manipulation efficace. Elles représentent une collection d'éléments de données et les relations qui existent entre eux, servant de fondation pour la conception d'algorithmes robustes.

Complexité des Algorithmes

Complexité Temporelle

La complexité temporelle est une mesure qualitative décrivant la durée d'exécution d'un algorithme en fonction de la taille de son entrée. C'est un indicateur essentiel pour évaluer l'efficacité et la scalabilité d'une solution algorithmique. L'analyse de la complexité vise à sélectionner l'algorithme le plus performant pour une tâche donnée ou à améliorer des algorithmes existnats.

Elle est couramment exprimée à l'aide de la notation Grand O (O-notation), qui caractérise la borne supérieure de la fonction de croissance du temps d'exécution à mesure que la taille de l'antrée tend vers l'infini, en ignorant les termes d'ordre inférieur et les coefficients constants.

Méthode de Calcul

1. On identifie généralement l'opération fondamentale ou répétée de l'algorithme, dont le nombre d'exécutions dépend de la taille du problème n. Soit T(n) cette fonction.
2. Si une fonction auxiliaire f(n) existe telle que la limite de T(n)/f(n) est une constante non nulle lorsque n tend vers l'infini, alors f(n) est de même ordre de grandeur que T(n). On écrit alors T(n) = O(f(n)), et O(f(n)) est appelée la complexité temporelle asymptotique de l'algorithme.

Un f(n) plus petit indique une complexité temporelle plus faible et une meilleure efficacité de l'algorithme. Les ordres de grandeur courants incluent O(1) (constant), O(log n) (logarithmique), O(n) (linéaire), O(n log n), O(n²) (quadratique), O(n³) (cubique), O(2^n) (exponentiel), et O(n!) (factoriel).

Complexité Spatiale

La complexité spatiale, notée S(n) = O(f(n)), mesure la quantité de mémoire temporaire utilisée par un algorithme pendant son exécution. Par exemple, un tri par insertion a une complexité spatiale de O(1), car il ne nécessite qu'un espace constant. En revanche, de nombreux algorithmes récursifs ont une complexité spatiale de O(n) en raison de la pile d'appels qui stocke les informations de retour pour chaque appel récursif.

Il existe souvent un compromis entre la complexité temporelle et la complexité spatiale. Améliorer la vitesse (réduire le temps) peut nécessiter plus de mémoire, et vice versa. La conception d'un algorithme doit prendre en compte ces facteurs, ainsi que la fréquence d'utilisation de l'algorithme, le volume de données à traiter, et l'environnement d'exécution.

Listes Linéaires

Tableaux Séquentiels

Une liste séquentielle est une structure de données linéaire où les éléments sont stockés dans des emplacements mémoire contigus, typiquement sous la forme d'un tableau. La relation logique d'adjacence entre les éléments est directement reflétée par leur contiguïté physique en mémoire. Cette organisation permet un accès direct aux éléments par leur indice, mais les opérations d'insertion ou de suppression au milieu du tableau peuvent être coûteuses (O(n)) car elles nécessitent le déplacement des éléments suivants.

Listes Chaînées

Contrairement aux tableaux séquentiels, une liste chaînée est une structure de stockage non contiguë où l'ordre logique des éléments est maintenu par des pointeurs. Chaque élément, appelé nœud, est généré dynamiquement et se compose de deux parties : un champ de données et un champ de pointeur qui référence le nœud suivant. L'insertion et la suppression d'un nœud dans une liste chaînée peuvent être effectuées en O(1) si la position est connue, ce qui est beaucoup plus rapide que pour un tableau séquentiel. Cependant, la recherche ou l'accès à un élément par son indice nécessite un parcours séquentiel, résultant en une complexité de O(n).

Terminologie associée :

• Pointeur précédent (prédécesseur) : Référence le nœud qui précède.
• Pointeur suivant (successeur) : Référence le nœud qui suit.

Types de Listes Chaînées :

• Liste chaînée simple : Chaque nœud contient un pointeur vers le nœud suivant uniquement. Le dernier nœud pointe vers None.
• Liste chaînée double : Chaque nœud contient des pointeurs vers le nœud précédent et le nœud suivant. Les opérations de modification doivent gérer les deux pointeurs.
• Liste chaînée circulaire simple : Chaque nœud contient un pointeur vers le nœud suivant, et le pointeur du dernier nœud pointe vers le premier nœud de la liste.

Implémentation en Python

Liste Chaînée Simple

La liste chaînée simple est une structure de données fondamentale où chaque élément, ou nœud, contient une valeur et un pointeur vers le nœud suivant. Elle permet des insertions et suppressions efficaces en tête ou en queue (avec un pointeur vers la queue).

class Node:
    """Représente un nœud dans une liste chaînée simple."""
    def __init__(self, value_data):
        self.data = value_data
        self.next_node = None

class SimpleLinkedList:
    """Implémente une liste chaînée simple."""
    def __init__(self, initial_node=None):
        self._head = initial_node

    def est_vide(self):
        """Vérifie si la liste est vide."""
        return self._head is None

    def obtenir_longueur(self):
        """Retourne le nombre d'éléments dans la liste."""
        current = self._head
        count = 0
        while current is not None:
            count += 1
            current = current.next_node
        return count

    def afficher_elements(self):
        """Parcourt et affiche tous les éléments de la liste."""
        current = self._head
        elements = []
        while current is not None:
            elements.append(str(current.data))
            current = current.next_node
        print(" ".join(elements))

    def ajouter_en_tete(self, item):
        """Ajoute un élément au début de la liste (insertion en tête)."""
        new_node = Node(item)
        new_node.next_node = self._head
        self._head = new_node

    def ajouter_en_queue(self, item):
        """Ajoute un élément à la fin de la liste (insertion en queue)."""
        new_node = Node(item)
        if self.est_vide():
            self._head = new_node
        else:
            current = self._head
            while current.next_node is not None:
                current = current.next_node
            current.next_node = new_node

    def inserer_a_position(self, position, item):
        """Insère un élément à une position spécifique.
        :param position: L'indice où insérer l'élément (0-basé).
        """
        if position <= 0:
            self.ajouter_en_tete(item)
        elif position >= self.obtenir_longueur():
            self.ajouter_en_queue(item)
        else:
            prev_node = self._head
            count = 0
            while count < position - 1:
                count += 1
                prev_node = prev_node.next_node
            new_node = Node(item)
            new_node.next_node = prev_node.next_node
            prev_node.next_node = new_node

    def supprimer_element(self, item):
        """Supprime la première occurrence d'un élément de la liste."""
        current = self._head
        previous = None
        while current is not None:
            if current.data == item:
                if previous is None: # Si l'élément à supprimer est la tête
                    self._head = current.next_node
                else:
                    previous.next_node = current.next_node
                return
            else:
                previous = current
                current = current.next_node

    def rechercher_element(self, item):
        """Recherche si un élément existe dans la liste."""
        current = self._head
        while current is not None:
            if current.data == item:
                return True
            current = current.next_node
        return False

if __name__ == "__main__":
    ma_liste = SimpleLinkedList()
    print(f"Liste vide : {ma_liste.est_vide()}")
    print(f"Longueur : {ma_liste.obtenir_longueur()}")

    ma_liste.ajouter_en_queue(10)
    print(f"Liste vide : {ma_liste.est_vide()}")
    print(f"Longueur : {ma_liste.obtenir_longueur()}")
    
    ma_liste.ajouter_en_queue(20)
    ma_liste.ajouter_en_tete(8)
    ma_liste.ajouter_en_queue(30)
    ma_liste.ajouter_en_queue(40)
    ma_liste.ajouter_en_queue(50)
    ma_liste.ajouter_en_queue(60)
    # Liste attendue: 8 10 20 30 40 50 60

    ma_liste.inserer_a_position(-1, 9) # Devrait insérer en tête
    ma_liste.afficher_elements() # 9 8 10 20 30 40 50 60
    ma_liste.inserer_a_position(3, 100)
    ma_liste.afficher_elements() # 9 8 10 100 20 30 40 50 60
    ma_liste.inserer_a_position(10, 200) # Devrait insérer en queue
    ma_liste.afficher_elements() # 9 8 10 100 20 30 40 50 60 200

    ma_liste.supprimer_element(100)
    ma_liste.afficher_elements() # 9 8 10 20 30 40 50 60 200
    ma_liste.supprimer_element(9)
    ma_liste.afficher_elements() # 8 10 20 30 40 50 60 200
    ma_liste.supprimer_element(200)
    ma_liste.afficher_elements() # 8 10 20 30 40 50 60
    
    print(f"Recherche 30 : {ma_liste.rechercher_element(30)}") # True
    print(f"Recherche 99 : {ma_liste.rechercher_element(99)}") # False

Liste Chaînée Double

La liste chaînée double améliore la liste simple en permettant un parcours bidirectionnel grâce à des pointeurs vers le nœud précédent et le nœud suivant. Cela simplifie la suppression d'un nœud donné sans avoir besoin de son prédécesseur direct.

class DoubleNode:
    """Représente un nœud dans une liste chaînée double."""
    def __init__(self, value_data):
        self.data = value_data
        self.next_node = None
        self.prev_node = None

class DoublyLinkedList:
    """Implémente une liste chaînée double."""
    def __init__(self, initial_node=None):
        self._head = initial_node

    def est_vide(self):
        """Vérifie si la liste est vide."""
        return self._head is None

    def obtenir_longueur(self):
        """Retourne le nombre d'éléments dans la liste."""
        current = self._head
        count = 0
        while current is not None:
            count += 1
            current = current.next_node
        return count

    def afficher_elements(self):
        """Parcourt et affiche tous les éléments de la liste."""
        current = self._head
        elements = []
        while current is not None:
            elements.append(str(current.data))
            current = current.next_node
        print(" ".join(elements))

    def ajouter_en_tete(self, item):
        """Ajoute un élément au début de la liste."""
        new_node = DoubleNode(item)
        if self._head:
            new_node.next_node = self._head
            self._head.prev_node = new_node
        self._head = new_node

    def ajouter_en_queue(self, item):
        """Ajoute un élément à la fin de la liste."""
        new_node = DoubleNode(item)
        if self.est_vide():
            self._head = new_node
        else:
            current = self._head
            while current.next_node is not None:
                current = current.next_node
            current.next_node = new_node
            new_node.prev_node = current

    def inserer_a_position(self, position, item):
        """Insère un élément à une position spécifique.
        :param position: L'indice où insérer l'élément (0-basé).
        """
        if position <= 0:
            self.ajouter_en_tete(item)
        elif position >= self.obtenir_longueur():
            self.ajouter_en_queue(item)
        else:
            current = self._head
            for _ in range(position): # Aller jusqu'à la position cible
                current = current.next_node
            
            new_node = DoubleNode(item)
            new_node.next_node = current
            new_node.prev_node = current.prev_node
            
            if current.prev_node:
                current.prev_node.next_node = new_node
            current.prev_node = new_node

    def supprimer_element(self, item):
        """Supprime la première occurrence d'un élément de la liste."""
        current = self._head
        while current is not None:
            if current.data == item:
                if current == self._head: # Si c'est la tête
                    self._head = current.next_node
                    if self._head: # S'il y a un nouveau chef
                        self._head.prev_node = None
                else: # Noeud intermédiaire ou queue
                    current.prev_node.next_node = current.next_node
                    if current.next_node:
                        current.next_node.prev_node = current.prev_node
                return
            current = current.next_node

    def rechercher_element(self, item):
        """Recherche si un élément existe dans la liste."""
        current = self._head
        while current is not None:
            if current.data == item:
                return True
            current = current.next_node
        return False

if __name__ == "__main__":
    ma_liste_double = DoublyLinkedList()
    print(f"Liste vide : {ma_liste_double.est_vide()}")
    print(f"Longueur : {ma_liste_double.obtenir_longueur()}")

    ma_liste_double.ajouter_en_queue(10)
    print(f"Liste vide : {ma_liste_double.est_vide()}")
    print(f"Longueur : {ma_liste_double.obtenir_longueur()}")

    ma_liste_double.ajouter_en_queue(20)
    ma_liste_double.ajouter_en_tete(8)
    ma_liste_double.ajouter_en_queue(30)
    ma_liste_double.ajouter_en_queue(40)
    ma_liste_double.ajouter_en_queue(50)
    ma_liste_double.ajouter_en_queue(60)
    # Liste attendue: 8 10 20 30 40 50 60

    ma_liste_double.inserer_a_position(-1, 9) # Devrait insérer en tête
    ma_liste_double.afficher_elements() # 9 8 10 20 30 40 50 60
    ma_liste_double.inserer_a_position(3, 100)
    ma_liste_double.afficher_elements() # 9 8 10 100 20 30 40 50 60
    ma_liste_double.inserer_a_position(10, 200) # Devrait insérer en queue
    ma_liste_double.afficher_elements() # 9 8 10 100 20 30 40 50 60 200

    ma_liste_double.supprimer_element(100)
    ma_liste_double.afficher_elements() # 9 8 10 20 30 40 50 60 200
    ma_liste_double.supprimer_element(9)
    ma_liste_double.afficher_elements() # 8 10 20 30 40 50 60 200
    ma_liste_double.supprimer_element(200)
    ma_liste_double.afficher_elements() # 8 10 20 30 40 50 60

Liste Chaînée Circulaire Simple

Dans une liste chaînée circulaire simple, le dernier nœud de la liste pointe vers le premier nœud, formant une boucle. Cela permet un parcours continu sans début ni fin distincts, utile pour des structures comme les files d'attente circulaires.

class CircularNode:
    """Représente un nœud dans une liste chaînée circulaire simple."""
    def __init__(self, value_data):
        self.data = value_data
        self.next_node = None

class SingleCircularLinkedList:
    """Implémente une liste chaînée circulaire simple."""
    def __init__(self, initial_node=None):
        self._head = initial_node
        if initial_node:
            initial_node.next_node = initial_node # Pour une liste d'un seul nœud

    def est_vide(self):
        """Vérifie si la liste est vide."""
        return self._head is None

    def obtenir_longueur(self):
        """Retourne le nombre d'éléments dans la liste."""
        if self.est_vide():
            return 0
        count = 0
        current = self._head
        while True:
            count += 1
            current = current.next_node
            if current == self._head:
                break
        return count

    def afficher_elements(self):
        """Parcourt et affiche tous les éléments de la liste."""
        if self.est_vide():
            return
        current = self._head
        elements = []
        while True:
            elements.append(str(current.data))
            current = current.next_node
            if current == self._head:
                break
        print(" ".join(elements))

    def ajouter_en_tete(self, item):
        """Ajoute un élément au début de la liste (nouvelle tête)."""
        new_node = CircularNode(item)
        if self.est_vide():
            self._head = new_node
            new_node.next_node = new_node
        else:
            current = self._head
            while current.next_node != self._head: # Trouver le dernier nœud
                current = current.next_node
            new_node.next_node = self._head
            self._head = new_node
            current.next_node = self._head # Le dernier nœud pointe vers la nouvelle tête

    def ajouter_en_queue(self, item):
        """Ajoute un élément à la fin de la liste."""
        new_node = CircularNode(item)
        if self.est_vide():
            self._head = new_node
            new_node.next_node = new_node
        else:
            current = self._head
            while current.next_node != self._head: # Trouver le dernier nœud
                current = current.next_node
            new_node.next_node = self._head
            current.next_node = new_node

    def inserer_a_position(self, position, item):
        """Insère un élément à une position spécifique.
        :param position: L'indice où insérer l'élément (0-basé).
        """
        if position <= 0:
            self.ajouter_en_tete(item)
        elif position >= self.obtenir_longueur():
            self.ajouter_en_queue(item)
        else:
            prev_node = self._head
            for _ in range(position - 1):
                prev_node = prev_node.next_node
            new_node = CircularNode(item)
            new_node.next_node = prev_node.next_node
            prev_node.next_node = new_node

    def supprimer_element(self, item):
        """Supprime la première occurrence d'un élément de la liste."""
        if self.est_vide():
            return

        current = self._head
        previous = None

        if self._head.data == item:
            if self.obtenir_longueur() == 1: # Si un seul élément et c'est celui à supprimer
                self._head = None
                return
            
            # Si la tête est l'élément et il y a d'autres éléments
            tail_node = self._head
            while tail_node.next_node != self._head:
                tail_node = tail_node.next_node
            self._head = self._head.next_node
            tail_node.next_node = self._head
            return
        
        previous = self._head
        current = self._head.next_node
        while current != self._head:
            if current.data == item:
                previous.next_node = current.next_node
                return
            previous = current
            current = current.next_node

    def rechercher_element(self, item):
        """Recherche si un élément existe dans la liste."""
        if self.est_vide():
            return False
        current = self._head
        while True:
            if current.data == item:
                return True
            current = current.next_node
            if current == self._head:
                break
        return False

if __name__ == "__main__":
    ma_liste_circulaire = SingleCircularLinkedList()
    print(f"Liste vide : {ma_liste_circulaire.est_vide()}")
    print(f"Longueur : {ma_liste_circulaire.obtenir_longueur()}")

    ma_liste_circulaire.ajouter_en_queue(10)
    print(f"Liste vide : {ma_liste_circulaire.est_vide()}")
    print(f"Longueur : {ma_liste_circulaire.obtenir_longueur()}")

    ma_liste_circulaire.ajouter_en_queue(20)
    ma_liste_circulaire.ajouter_en_tete(8)
    ma_liste_circulaire.ajouter_en_queue(30)
    ma_liste_circulaire.ajouter_en_queue(40)
    ma_liste_circulaire.ajouter_en_queue(50)
    ma_liste_circulaire.ajouter_en_queue(60)
    # Liste attendue: 8 10 20 30 40 50 60

    ma_liste_circulaire.inserer_a_position(-1, 9) # Devrait insérer en tête
    ma_liste_circulaire.afficher_elements() # 9 8 10 20 30 40 50 60
    ma_liste_circulaire.inserer_a_position(3, 100)
    ma_liste_circulaire.afficher_elements() # 9 8 10 100 20 30 40 50 60
    ma_liste_circulaire.inserer_a_position(10, 200) # Devrait insérer en queue
    ma_liste_circulaire.afficher_elements() # 9 8 10 100 20 30 40 50 60 200

    ma_liste_circulaire.supprimer_element(100)
    ma_liste_circulaire.afficher_elements() # 9 8 10 20 30 40 50 60 200
    ma_liste_circulaire.supprimer_element(9)
    ma_liste_circulaire.afficher_elements() # 8 10 20 30 40 50 60 200
    ma_liste_circulaire.supprimer_element(200)
    ma_liste_circulaire.afficher_elements() # 8 10 20 30 40 50 60

Algorithmes de Tri

Stabilité des Algorithmes de Tri

Un algorithme de tri est dit stable si, pour tout ensemble de records ayant des clés égales, l'ordre relatif de ces records n'est pas modifié par le tri. Si deux éléments r[i] et r[j] ont la même clé et que r[i] apparaît avant r[j] dans la séquence originale, alors r[i] doit apparaître avant r[j] dans la séquence triée pour que l'algorithme soit stable.

Tri à Bulles (Bubble Sort)

Le tri à bulles est un algorithme de tri simple qui parcourt répétitivement une liste, compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Les éléments plus grands "remontent" progressivement vers la fin de la liste, comme des bulles dans un liquide. Le processus se répète jusqu'à ce qu'aucun échange ne soit nécessaire, indiquant que la liste est triée.

Son principe est le suivant :

1. Comparer chaque paire d'éléments adjacents.
2. Échanger les éléments s'ils ne sont pas dans le bon ordre.
3. Après un passage, l'élément le plus grand (ou le plus petit) est à sa position finale.
4. Répéter le processus pour les éléments restants, en excluant les éléments déjà placés.
5. Continuer jusqu'à ce qu'aucun échange ne se produise lors d'un passage complet.

def tri_a_bulles(liste_elements):
    """Implémente le tri à bulles."""
    taille = len(liste_elements)
    # Parcourt tous les éléments de la liste
    for i in range(taille - 1):
        # Le dernier i éléments sont déjà en place
        for j in range(taille - 1 - i):
            # Compare les éléments adjacents et échange si nécessaire
            if liste_elements[j] > liste_elements[j + 1]:
                liste_elements[j], liste_elements[j + 1] = liste_elements[j + 1], liste_elements[j]

if __name__ == "__main__":
    liste_desordonnee = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(f"Liste originale: {liste_desordonnee}")
    tri_a_bulles(liste_desordonnee)
    print(f"Liste triée: {liste_desordonnee}")

Tri par Sélection (Selection Sort)

Le tri par sélection est un autre algorithme de tri simple et intuitif. Il fonctionne en divisant la liste en deux parties : une partie triée à gauche et une partie non triée à droite. À chaque itération, l'algorithme trouve l'élément minimum (ou maximum) dans la partie non triée et l'échange avec le premier élément de cette partie, l'ajoutant ainsi à la partie triée.

La distinction avec le tri à bulles réside dans le fait que le tri par sélection effectue une seule permutation par passage pour placer l'élément correct à sa position finale, tandis que le tri à bulles effectue de multiples échanges d'éléments adjacents.

def tri_par_selection(liste_elements):
    """Implémente le tri par sélection."""
    taille = len(liste_elements)
    # Parcourt la liste jusqu'à l'avant-dernier élément
    for i in range(taille - 1):
        index_min = i # Supposons que l'élément actuel est le minimum
        # Trouve l'élément minimum dans le reste de la liste non triée
        for j in range(i + 1, taille):
            if liste_elements[j] < liste_elements[index_min]:
                index_min = j
        # Échange l'élément minimum trouvé avec l'élément à la position i
        liste_elements[i], liste_elements[index_min] = liste_elements[index_min], liste_elements[i]

if __name__ == "__main__":
    liste_desordonnee = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(f"Liste originale: {liste_desordonnee}")
    tri_par_selection(liste_desordonnee)
    print(f"Liste triée: {liste_desordonnee}")

Tri par Insertion (Insertion Sort)

Le tri par insertion est un algorithme qui construit la liste triée un élément à la fois. Il procède par N-1 passes. Il commence par le premier élément (considéré comme une liste triée d'un seul élément). Ensuite, à chaque passe, il prend l'élément suivant de la partie non triée et l'insère à sa position correcte dans la partie déjà triée.

Le principe est récursif : lorsqu'un élément à l'indice i est trié, la sous-séquence [0, i-1] est déjà triée.

def tri_par_insertion(liste_elements):
    """Implémente le tri par insertion."""
    taille = len(liste_elements)
    # Commence à partir du deuxième élément
    for i in range(1, taille):
        element_a_inserer = liste_elements[i]
        j = i - 1 # Pointeur vers le dernier élément de la sous-liste triée

        # Déplace les éléments de la sous-liste triée qui sont plus grands
        # que element_a_inserer d'une position vers la droite
        while j >= 0 and element_a_inserer < liste_elements[j]:
            liste_elements[j + 1] = liste_elements[j]
            j -= 1
        # Insère l'élément à sa position correcte
        liste_elements[j + 1] = element_a_inserer

if __name__ == "__main__":
    liste_desordonnee = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(f"Liste originale: {liste_desordonnee}")
    tri_par_insertion(liste_desordonnee)
    print(f"Liste triée: {liste_desordonnee}")

Tri de Shell (Shell Sort)

Le tri de Shell est une amélioration du tri par insertion. Il fonctionne en comparant des éléments éloignés dans la liste, puis en réduisant progressivement l'écart (ou "gap") entre les éléments comparés. Le but est de déplacer rapidement les éléments loin de leur position finale, avant d'effectuer un tri par insertion sur l'ensemble de la liste avec un écart de 1.

La méthode consiste à prendre un incrément initial d1, puis à diviser la liste en groupes d'éléments espacés de d1. Chaque groupe est trié par insertion. Ensuite, un nouvel incrément d2 < d1 est choisi, et le processus est répété, jusqu'à ce que l'incrément soit de 1, ce qui revient à un tri par insertion standard sur une liste déjà "presque" triée.

def tri_de_shell(liste_elements):
    """Implémente le tri de Shell."""
    taille = len(liste_elements)
    intervalle = taille // 2 # Incrément initial, généralement la moitié de la taille

    # Continue tant que l'intervalle est supérieur à 0
    while intervalle > 0:
        # Tri par insertion avec un pas de 'intervalle'
        for i in range(intervalle, taille):
            valeur_actuelle = liste_elements[i]
            position = i

            # Déplace les éléments des sous-listes qui sont plus grands
            # que valeur_actuelle d'un 'intervalle' vers la droite
            while position >= intervalle and liste_elements[position - intervalle] > valeur_actuelle:
                liste_elements[position] = liste_elements[position - intervalle]
                position -= intervalle
            liste_elements[position] = valeur_actuelle
        
        # Réduit l'intervalle pour la prochaine passe
        intervalle //= 2

if __name__ == "__main__":
    liste_desordonnee = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(f"Liste originale: {liste_desordonnee}")
    tri_de_shell(liste_desordonnee)
    print(f"Liste triée: {liste_desordonnee}")

Tri Rapide (Quick Sort)

Le tri rapide est un algorithme de tri par "diviser pour régner". Il sélectionne un élément appelé "pivot" dans le tableau, puis partitionne le reste des éléments en deux sous-tableaux : ceux inférieurs au pivot et ceux supérieurs au pivot. Le pivot est placé à sa position finale correcte. Ensuite, l'algorithme est appliqué récursivement aux deux sous-tableaux. Le tri rapide n'est généralement pas un algorithme de tri stable.

Une passe de tri rapide typique se déroule comme suit :

1. Choisir un pivot (souvent le premier élément).
2. Utiliser deux pointeurs, un à partir du début (gauche) et un à partir de la fin (droite) du tableau.
3. Déplacer le pointeur droite vers la gauche jusqu'à trouver un élément plus petit que le pivot, puis échanger cet élément avec l'élément pointé par gauche.
4. Déplacer le pointeur gauche vers la droite jusqu'à trouver un élément plus grand que le pivot, puis échanger cet élément avec l'élément pointé par droite.
5. Répéter les étapes 3 et 4 jusqu'à ce que les pointeurs gauche et droite se croisent ou se rencontrent.
6. Placer le pivot à la position finale des pointeurs.
7. Appliquer récursivement le processus aux sous-tableaux à gauche et à droite du pivot.

def tri_rapide(liste_elements, debut, fin):
    """Implémente le tri rapide."""
    if debut >= fin:
        return

    valeur_pivot = liste_elements[debut]
    ptr_gauche = debut
    ptr_droite = fin

    while ptr_gauche < ptr_droite:
        # Déplace ptr_droite vers la gauche tant que l'élément est >= pivot
        while ptr_gauche < ptr_droite and liste_elements[ptr_droite] >= valeur_pivot:
            ptr_droite -= 1
        liste_elements[ptr_gauche] = liste_elements[ptr_droite] # Place l'élément trouvé à gauche

        # Déplace ptr_gauche vers la droite tant que l'élément est < pivot
        while ptr_gauche < ptr_droite and liste_elements[ptr_gauche] < valeur_pivot:
            ptr_gauche += 1
        liste_elements[ptr_droite] = liste_elements[ptr_gauche] # Place l'élément trouvé à droite
    
    # Quand les pointeurs se rencontrent, placer le pivot à cette position
    liste_elements[ptr_gauche] = valeur_pivot

    # Trier récursivement la sous-liste à gauche du pivot
    tri_rapide(liste_elements, debut, ptr_gauche - 1)
    # Trier récursivement la sous-liste à droite du pivot
    tri_rapide(liste_elements, ptr_gauche + 1, fin)


if __name__ == "__main__":
    liste_desordonnee = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(f"Liste originale: {liste_desordonnee}")
    tri_rapide(liste_desordonnee, 0, len(liste_desordonnee) - 1)
    print(f"Liste triée: {liste_desordonnee}")

Tri Fusion (Merge Sort)

Le tri fusion est un algorithme de tri efficace basé sur le principe "diviser pour régner". Il consiste à diviser récursivement la liste en sous-listes jusqu'à ce que chaque sous-liste ne contienne qu'un seul élément (qui est intrinsèquement trié). Ensuite, ces sous-listes sont fusionnées de manière ordonnée pour former des listes triées de plus grande taille, jusqu'à ce que la liste complète soit triée.

L'opération clé est la fusion, qui prend deux sous-listes triées et les combine en une seule liste triée.

Exemple : Soit la liste {6, 202, 100, 301, 38, 8, 1}

1. Division initiale : {6, 202, 100, 301, 38, 8, 1}

2. Première phase de division (récursive) :

   • {6}, {202}, {100}, {301}, {38}, {8}, {1} (chaque élément est une liste triée)

3. Première phase de fusion :

   • {6, 202} fusion de {6} et {202}
   • {100, 301} fusion de {100} et {301}
   • {8, 38} fusion de {38} et {8}
   • {1} (reste seul)

   Liste partielle après cette phase: {{6, 202}, {100, 301}, {8, 38}, {1}}

4. Deuxième phase de fusion :

   • {6, 100, 202, 301} fusion de {6, 202} et {100, 301}
   • {1, 8, 38} fusion de {8, 38} et {1}

   Liste partielle après cette phase: {{6, 100, 202, 301}, {1, 8, 38}}

5. Troisième phase de fusion :

   • {1, 6, 8, 38, 100, 202, 301} fusion des deux listes précédentes.

   Liste finale triée.

def tri_par_fusion(liste_elements):
    """Implémente le tri par fusion."""
    taille = len(liste_elements)
    if taille <= 1:
        return liste_elements

    point_milieu = taille // 2

    # Divise la liste en deux moitiés
    moitie_gauche = tri_par_fusion(liste_elements[:point_milieu])
    moitie_droite = tri_par_fusion(liste_elements[point_milieu:])

    # Fusionne les deux moitiés triées
    index_gauche, index_droite = 0, 0
    liste_fusionnee = []

    while index_gauche < len(moitie_gauche) and index_droite < len(moitie_droite):
        if moitie_gauche[index_gauche] <= moitie_droite[index_droite]:
            liste_fusionnee.append(moitie_gauche[index_gauche])
            index_gauche += 1
        else:
            liste_fusionnee.append(moitie_droite[index_droite])
            index_droite += 1

    # Ajoute les éléments restants (s'il y en a)
    liste_fusionnee.extend(moitie_gauche[index_gauche:])
    liste_fusionnee.extend(moitie_droite[index_droite:])

    return liste_fusionnee

if __name__ == "__main__":
    liste_desordonnee = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(f"Liste originale: {liste_desordonnee}")
    liste_triee = tri_par_fusion(liste_desordonnee)
    print(f"Liste originale (non modifiée): {liste_desordonnee}") # Le tri fusion retourne une nouvelle liste
    print(f"Liste triée: {liste_triee}")

Algorithmes de Recherche

Recherche Binaire (Binary Search)

Prérequis : La liste doit être triée. Si elle ne l'est pas, un tri préalable est nécessaire.

La recherche binaire, aussi connue sous le nom de recherche par dichotomie ou recherche par demi-intervalle, est un algorithme de recherche efficace pour trouver la position d'une valeur cible dans une liste triée. L'idée principale est de comparer la valeur cible avec l'élément du milieu de la liste. Si les valeurs sont égales, l'élément est trouvé. Si la cible est inférieure, la recherche continue dans la moitié inférieure de la liste ; si elle est supérieure, la recherche continue dans la moitié supérieure. Ce processus est répété récursivement ou itérativement jusqu'à ce que l'élément soit trouvé ou que l'intervalle de recherche devienne vide.

Analyse de la complexité : Dans le pire des cas, le nombre de comparaisons est de log₂(n+1), ce qui donne une complexité temporelle attendue de O(log n).

def recherche_binaire_recursive(liste_triee, cible):
    """Implémente la recherche binaire de manière récursive."""
    if not liste_triee:
        return False
    
    milieu_idx = len(liste_triee) // 2
    valeur_milieu = liste_triee[milieu_idx]

    if valeur_milieu == cible:
        return True
    elif cible < valeur_milieu:
        return recherche_binaire_recursive(liste_triee[:milieu_idx], cible)
    else:
        return recherche_binaire_recursive(liste_triee[milieu_idx + 1:], cible)

def recherche_binaire_iterative(liste_triee, cible):
    """Implémente la recherche binaire de manière itérative."""
    debut_idx = 0
    fin_idx = len(liste_triee) - 1

    while debut_idx <= fin_idx:
        milieu_idx = (debut_idx + fin_idx) // 2
        valeur_milieu = liste_triee[milieu_idx]

        if valeur_milieu == cible:
            return True
        elif cible < valeur_milieu:
            fin_idx = milieu_idx - 1
        else:
            debut_idx = milieu_idx + 1
    return False

if __name__ == "__main__":
    ma_liste_triee = [17, 20, 26, 31, 44, 54, 55, 77, 93]
    print(f"Recherche récursive 55 : {recherche_binaire_recursive(ma_liste_triee, 55)}") # True
    print(f"Recherche récursive 100 : {recherche_binaire_recursive(ma_liste_triee, 100)}") # False
    print(f"Recherche itérative 55 : {recherche_binaire_iterative(ma_liste_triee, 55)}") # True
    print(f"Recherche itérative 100 : {recherche_binaire_iterative(ma_liste_triee, 100)}") # False

Arbres Binaires

En informatique, un arbre binaire est une structure de données arborescente où chaque nœud a au plus deux enfants, généralement appelés "enfant gauche" et "enfant droit". Les arbres binaires sont des structures fondamentales utilisées pour implémenter des arbres de recherche binaires (BST) et des tas binaires.

Les enfants d'un nœud dans un arbre binaire sont distingués par leur position (gauche ou droite) et leur ordre est significatif. Voici quelques propriétés clés des arbres binaires :

• Le nombre maximal de nœuds au niveau i est 2^(i-1) (avec la racine au niveau 1).
• Un arbre binaire de profondeur k (ou hauteur k) a au maximum 2^k - 1 nœuds et au minimum k nœuds.
• Pour tout arbre binaire non vide T, si N₀ est le nombre de nœuds feuilles et N₂ est le nombre de nœuds avec deux enfants, alors N₀ = N₂ + 1.

Terminologie associée :

• Nœud : Élément de l'arbre contenant une donnée et des références vers ses enfants.
• Nœud enfant : Un nœud directement relié et descendant d'un autre nœud.
• Nœud parent : Le nœud directement au-dessus d'un enfant.
• Nœuds frères : Nœuds ayant le même parent.
• Nœud ancêtre : Tout nœud sur le chemin de la racine à un nœud donné.
• Nœud descendant : Tout nœud dans le sous-arbre enraciné par un nœud donné.
• Niveau d'un nœud : La racine est au niveau 1, ses enfants au niveau 2, et ainsi de suite.
• Profondeur (ou hauteur) de l'arbre : Le niveau maximal de tous les nœuds de l'arbre.
• Degré d'un nœud : Le nombre de ses enfants.
• Degré de l'arbre : Le degré maximal de tous les nœuds de l'arbre.
• Nœud feuille (ou terminal) : Un nœud de degré 0 (n'a pas d'enfants).
• Nœud interne (ou branche) : Un nœud de degré non nul.

Arbre Binaire Complet

Un arbre binaire complet de profondeur h est un arbre où tous les niveaux de 1 à h-1 sont entièrement remplis, et le niveau h est rempli de gauche à droite. Il y a un total de n nœuds, et si ces nœuds étaient numérotés séquentiellement de 1 à n de haut en bas et de gauche à droite, ils occuperaient les positions 1 à n dans un arbre binaire plein de profondeur h.

Arbre Binaire Plein (ou Parfait)

Un arbre binaire plein est un arbre où chaque nœud interne a exactement deux enfants et tous les nœuds feuilles sont au même niveau. Un arbre binaire de profondeur k est plein si et seulement s'il contient exactement 2^k - 1 nœuds.

class ArbreNode:
    """Représente un nœud dans un arbre binaire."""
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

class BinaryTree:
    """Implémente un arbre binaire."""
    def __init__(self):
        self.root = None

    def add_node(self, item):
        """Ajoute un nœud à l'arbre en utilisant une approche de parcours en largeur (niveau par niveau),
        pour créer un arbre binaire presque complet.
        """
        new_node = ArbreNode(item)
        if self.root is None:
            self.root = new_node
            return
        
        queue = [self.root]
        while queue:
            current_node = queue.pop(0)
            if current_node.left is None:
                current_node.left = new_node
                return
            else:
                queue.append(current_node.left)
            
            if current_node.right is None:
                current_node.right = new_node
                return
            else:
                queue.append(current_node.right)

    def parcours_largeur(self):
        """Effectue un parcours en largeur (BFS) de l'arbre."""
        if self.root is None:
            return
        
        queue = [self.root]
        elements_visites = []
        while queue:
            current_node = queue.pop(0)
            elements_visites.append(str(current_node.val))
            if current_node.left is not None:
                queue.append(current_node.left)
            if current_node.right is not None:
                queue.append(current_node.right)
        print(" ".join(elements_visites))

    def parcours_prefixe(self, node_courant):
        """Effectue un parcours préfixe (Racine-Gauche-Droite) de l'arbre."""
        if node_courant is None:
            return
        print(node_courant.val, end=" ")
        self.parcours_prefixe(node_courant.left)
        self.parcours_prefixe(node_courant.right)

    def parcours_infixe(self, node_courant):
        """Effectue un parcours infixe (Gauche-Racine-Droite) de l'arbre."""
        if node_courant is None:
            return
        self.parcours_infixe(node_courant.left)
        print(node_courant.val, end=" ")
        self.parcours_infixe(node_courant.right)

    def parcours_postfixe(self, node_courant):
        """Effectue un parcours postfixe (Gauche-Droite-Racine) de l'arbre."""
        if node_courant is None:
            return
        self.parcours_postfixe(node_courant.left)
        self.parcours_postfixe(node_courant.right)
        print(node_courant.val, end=" ")


if __name__ == "__main__":
    mon_arbre = BinaryTree()
    for i in range(10):
        mon_arbre.add_node(i)
    
    print("Parcours en largeur:")
    mon_arbre.parcours_largeur() # 0 1 2 3 4 5 6 7 8 9 
    print("\nParcours préfixe:")
    mon_arbre.parcours_prefixe(mon_arbre.root) # 0 1 3 7 8 4 9 2 5 6 
    print("\nParcours infixe:")
    mon_arbre.parcours_infixe(mon_arbre.root) # 7 3 8 1 9 4 0 5 2 6 
    print("\nParcours postfixe:")
    mon_arbre.parcours_postfixe(mon_arbre.root) # 7 8 3 9 4 1 5 6 2 0 
    print("")

Types de Parcours d'Arbres :

• Parcours Préfixe (Pre-order Traversal) : Visite la racine, puis le sous-arbre gauche, puis le sous-arbre droit (Racine-Gauche-Droite).
• Parcours Infixe (In-order Traversal) : Visite le sous-arbre gauche, puis la racine, puis le sous-arbre droit (Gauche-Racine-Droite).
• Parcours Postfixe (Post-order Traversal) : Visite le sous-arbre gauche, puis le sous-arbre droit, puis la racine (Gauche-Droite-Racine).

Si vous connaissez le parcours infixe et l'un des deux autres parcours (préfixe ou postfixe), vous pouvez reconstruire la structure unique de l'arbre binaire.