Algorithmes de Recherche et de Tri

Recherche Linéaire

Fonction	Description	Paramètres	Retour	Exemple
linear_search	Parcourt séquentiellement la liste jusqu'à trouver l'élément	element, liste	booléen	linear_search(5, [1,3,5]) → True

def linear_search(element, liste):
    for elt in liste:
        if elt == element:
            return True
    return False
    

Complexité

O(n) dans le pire cas - Parcourt toute la liste

Recherche Dichotomique

Fonction	Description	Paramètres	Retour	Exemple
binary_search	Divise la liste triée par 2 à chaque étape	element, liste_triée	booléen	binary_search(7, [1,3,5,7,9]) → True

def binary_search(element, sorted_list):
    low = 0
    high = len(sorted_list) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == element:
            return True
        elif element < sorted_list[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return False
    

Tri par Sélection

1. Trouver le minimum dans la partie non triée
2. L'échanger avec le premier élément non trié
3. Répéter jusqu'à ce que la liste soit triée

def tri_selection(liste):
    n = len(liste)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if liste[j] < liste[min_index]:
                min_index = j
        liste[i], liste[min_index] = liste[min_index], liste[i]
    return liste
    

Tri par Insertion

1. Prendre un élément non trié
2. Le comparer avec les éléments triés
3. Insérer à la bonne position

def tri_insertion(liste):
    for i in range(1, len(liste)):
        cle = liste[i]
        j = i-1
        while j >= 0 and cle < liste[j]:
            liste[j+1] = liste[j]
            j -= 1
        liste[j+1] = cle
    return liste
    

Comparaisons

Algorithme	Complexité	Stable	En place
Sélection	O(n²)	Non	Oui
Insertion	O(n²)	Oui	Oui