IMG_4424.jpeg

# Algorithmes de tri ## Tri par insertion Principe: Comme pour ranger une main de cartes, on prend les éléments un par un et on les insère à leur place parmi ceux déjà triés. ```python def tri_insertion(tableau): """Trie un tableau en place en utilisant l'algorithme de tri par insertion."""...

# Algorithmes de tri ## Tri par insertion Principe: Comme pour ranger une main de cartes, on prend les éléments un par un et on les insère à leur place parmi ceux déjà triés. ```python def tri_insertion(tableau): """Trie un tableau en place en utilisant l'algorithme de tri par insertion.""" n = len(tableau) for i in range(1, n): element_a_inserer = tableau[i] j = i # Déplacer les éléments du tableau[0..i-1], qui sont plus grands que # element_a_inserer, d'une position vers l'avant de leur position actuelle while j > 0 and tableau[j-1] > element_a_inserer: tableau[j] = tableau[j-1] j -= 1 tableau[j] = element_a_inserer return tableau ``` * Complexité: $O(n^2)$ dans le pire cas et en moyenne, $O(n)$ dans le meilleur cas (tableau déjà trié). * Avantage: simple à implémenter, efficace pour les petits tableaux ou les tableaux presque triés. * Inconvénient: inefficace pour les grands tableaux. ## Tri par sélection Principe: On cherche le plus petit élément du tableau et on l'échange avec le premier élément, puis on cherche le plus petit élément du reste du tableau et on l'échange avec le deuxième élément, et ainsi de suite. ```python def tri_selection(tableau): """Trie un tableau en place en utilisant l'algorithme de tri par sélection.""" n = len(tableau) for i in range(n): # Trouver l'index du minimum dans le reste du tableau non trié index_min = i for j in range(i+1, n): if tableau[j] < tableau[index_min]: index_min = j # Échanger l'élément minimum trouvé avec le premier élément non trié tableau[i], tableau[index_min] = tableau[index_min], tableau[i] return tableau ``` * Complexité: $O(n^2)$ dans tous les cas. * Avantage: simple à implémenter, effectue peu d'échanges. * Inconvénient: inefficace pour les grands tableaux. ## Tri à bulles Principe: On parcourt le tableau et on échange les éléments adjacents qui ne sont pas dans le bon ordre. On répète le parcours tant qu'il y a des échanges. ```python def tri_bulles(tableau): """Trie un tableau en place en utilisant l'algorithme de tri à bulles.""" n = len(tableau) for i in range(n): # Le dernier i éléments sont déjà à leur place for j in range(0, n-i-1): # Parcourir le tableau de 0 à n-i-1 # Échanger si l'élément trouvé est plus grand que le suivant if tableau[j] > tableau[j+1]: tableau[j], tableau[j+1] = tableau[j+1], tableau[j] return tableau ``` * Complexité: $O(n^2)$ dans le pire cas et en moyenne, $O(n)$ dans le meilleur cas (tableau déjà trié). * Avantage: simple à implémenter. * Inconvénient: inefficace pour les grands tableaux. ## Tri rapide (quicksort) Principe: On choisit un élément pivot, on partitionne le tableau en deux sous-tableaux (les éléments inférieurs au pivot et les éléments supérieurs au pivot), puis on trie récursivement les deux sous-tableaux. ```python def partition(tableau, low, high): """Fonction de partitionnement pour le tri rapide.""" pivot = tableau[high] i = low - 1 for j in range(low, high): if tableau[j] 1: mid = len(tableau) // 2 # Trouver le milieu du tableau L = tableau[:mid] # Diviser le tableau en deux moitiés R = tableau[mid:] tri_fusion(L) # Trier la première moitié tri_fusion(R) # Trier la deuxième moitié i = j = k = 0 # Copier les données dans les tableaux temporaires L[] et R[] while i < len(L) and j < len(R): if L[i] < R[j]: tableau[k] = L[i] i += 1 else: tableau[k] = R[j] j += 1 k += 1 # Vérifier si des éléments restent dans L[] while i < len(L): tableau[k] = L[i] i += 1 k += 1 # Vérifier si des éléments restent dans R[] while j < len(R): tableau[k] = R[j] j += 1 k += 1 ``` * Complexité: $O(n \log n)$ dans tous les cas. * Avantage: stable, efficace pour les grands tableaux. * Inconvénient: nécessite de l'espace mémoire supplémentaire.