Recherche Dichotomique (Binary Search) en Python
Recherche un élément x dans une liste triée croissante L en divisant l’intervalle de recherche par deux à chaque étape. Renvoie l’indice de x s’il est présent, sinon None.
Complexité: Temps : O(log n) | Espace : O(1)
def recherche_dicho(L: list, x) -> int | None: """ list, object -> int | None Prend en argument une liste L d'éléments comparables et triés en ordre croissant, et x un élément comparable à ceux de L. Renvoie un indice c tel que L[c] == x s’il existe, et None sinon. Procède par recherche dichotomique (itérative). """ debut, fin = 0, len(L) - 1 while debut <= fin: # variant : fin - debut # Invariant : si x est présent, alors il l’est dans L[debut:fin+1] milieu = (debut + fin) // 2 if L[milieu] > x: fin = milieu - 1 elif L[milieu] == x: return milieu else: debut = milieu + 1 return None # explicite pour la clarté Tri Fusion en Python
Le tri fusion est un algorithme de tri efficace qui utilise la technique de diviser pour régner. Il divise la liste en deux moitiés, trie chaque moitié récursivement, puis fusionne les deux moitiés triées.
Complexité: Temps : O(n log n) | Espace : O(n)
def fusion(L1 : list, L2 : list) -> list: """Fonction auxiliaire pour fusionner deux listes triées L1 et L2 en une seule liste triée""" n1, n2 = len(L1), len(L2) i, j = 0, 0 L = [] while i < n1 and j < n2: if L1[i] <= L2[j]: L.append(L1[i]) i += 1 else: L.append(L2[j]) j += 1 while i < n1: L.append(L1[i]) i += 1 while j < n2: L.append(L2[j]) j += 1 return L def tri_fusion(L : list) -> None: """Fonction principale pour trier la liste L en place""" n = len(L) if n <= 1: return L mid = n // 2 L1 = L[:mid] L2 = L[mid:] T1 = tri_fusion(L1) T2 = tri_fusion(L2) return fusion(T1, T2) Tri Rapide en Python
Le tri rapide est un algorithme de tri efficace qui utilise la technique de diviser pour régner. Il choisit un pivot, partitionne la liste en éléments inférieurs et supérieurs au pivot, puis trie récursivement les sous-listes.
Complexité: Temps (moyen) : O(n log n), (pire) : O(n²) | Espace : O(log n) (pile récursive)
def partition(L : list, debut : int, fin : int) -> int: """Partitionne la liste L entre les indices debut et fin et retourne l'indice du pivot""" pivot = L[debut] g = debut + 1 d = fin - 1 while True: while g <= d and L[g] <= pivot: g += 1 while g <= d and L[d] >= pivot: d -= 1 if g > d: break L[g], L[d] = L[d], L[g] g += 1 d -= 1 L[debut], L[d] = L[d], L[debut] return d def tri_rapide(L : list) -> None: """Trie la liste L en place en utilisant l'algorithme de tri rapide""" def aux(L : list, debut : int, fin : int) -> None: if debut < fin: p = partition(L, debut, fin) aux(L, debut, p) aux(L, p + 1, fin) aux(L, 0, len(L)) Tri par sélection récursif (Selection Sort) en Python
À chaque étape k, on place le plus petit élément du segment L[k:n] à l’indice k, puis on traite récursivement le reste. Trie la liste en place.
Complexité: Temps : O(n²) | Espace : O(n) (pile récursive)
def tri_selection_rec(L: list) -> None: """Trie L en place par sélection, version récursive.""" n = len(L) def aux(k: int) -> None: # Invariant : après l'appel, L[:k] contient les k plus petits éléments triés if k >= n - 1: return # chercher l'indice du minimum sur L[k:n] ind_min = k for j in range(k + 1, n): if L[j] < L[ind_min]: ind_min = j # placer le minimum en position k if ind_min != k: L[k], L[ind_min] = L[ind_min], L[k] # traiter le suffixe suivant aux(k + 1) aux(0)Tri par insertion récursif (Insertion Sort) en Python
À chaque étape k, l’élément L[k] est inséré à la bonne position dans le sous-tableau trié L[:k]. L’algorithme est écrit en version récursive.
Complexité: Temps : O(n²) | Espace : O(n) (pile récursive)
def tri_insertion_rec(L: list) -> None: """Trie L en place par insertion, version récursive.""" def aux(k: int) -> None: """Trie récursivement L[:k+1].""" if k > 0: # cas terminal : L[:1] est déjà triée aux(k - 1) # insérer L[k] au bon endroit valeur_a_placer = L[k] j = k while j > 0 and L[j - 1] > valeur_a_placer: L[j] = L[j - 1] # décalage j -= 1 L[j] = valeur_a_placer # insertion aux(len(L) - 1)Tri à bulles (Bubble Sort) en Python
Le tri à bulles parcourt la liste plusieurs fois : à chaque passage, il compare les éléments adjacents et les échange si nécessaire. Les plus grands éléments “remontent” progressivement en fin de liste. Version itérative.
Complexité: Temps : O(n²) | Espace : O(1)
def tri_bulle(T: list) -> None: """Trie T en place par l’algorithme du tri à bulles (itératif).""" perm = True passage = 0 while perm: # Après chaque passage, T[len(T)-passage:] est trié perm = False passage += 1 for i in range(len(T) - passage): if T[i] > T[i + 1]: perm = True T[i], T[i + 1] = T[i + 1], T[i]