Algorithmes de tri - Classification des espèces

Bienvenue de nouveau ! Darwin ici, avec une autre compétence essentielle.

Imagine que tu as découvert 100 espèces différentes pendant une expédition. Tu dois les organiser par ordre alphabétique pour un catalogue. Comment vas-tu t'y prendre ? Tu pourrais :

• Faire des bulles - comparer les voisins, les échanger (lent mais simple)
• Sélectionner - trouver le plus petit, l'ajouter à une nouvelle liste (lent aussi)
• Diviser et fusionner - découper en moitiés, trier séparément, fusionner (rapide !)

Ce sont des algorithmes de tri - différentes façons d'ordonner des données. Chacun a ses forces, ses faiblesses et sa complexité !

Pourquoi le tri est-il important ?

Les données triées permettent :

• Une recherche plus rapide - la recherche binaire nécessite des données triées
• Une analyse plus facile - facile de trouver le min/max, la médiane
• Une meilleure présentation - par ordre alphabétique, chronologique
• De l'efficacité - beaucoup d'algorithmes fonctionnent mieux sur des données triées

1# Exemple : Rechercher dans une liste triée
2species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
3
4# Recherche binaire - O(log n) - mais nécessite un tri !
5import bisect
6index = bisect.bisect_left(species, "Leo")  # Rapide !
7
8# vs liste non triée - O(n)
9unsorted_species = ["Python", "Leo", "Gorilla", ...]
10index = unsorted_species.index("Leo")  # Plus lent pour de grandes listes

Recherche binaire - pourquoi un catalogue trié est utile

Une liste triée permet de chercher plus malin qu'entrée par entrée. La recherche binaire fonctionne comme la recherche d'une espèce dans un guide imprimé : tu l'ouvres au milieu et tu sais tout de suite dans quelle moitié continuer. Chaque tour répète les mêmes quatre étapes :

1. Trouve l'élément du milieu de la plage recherchée.
2. Compare-le avec la valeur recherchée.
3. Si ce n'est pas lui, choisis la moitié gauche ou droite - celle où la valeur peut encore se trouver.
4. Répète sur la plage plus petite jusqu'à trouver l'élément ou épuiser la plage - puis renvoie le résultat.

1def binary_search(sorted_list, target):
2    left = 0
3    right = len(sorted_list) - 1
4    while left <= right:
5        mid = (left + right) // 2       # 1. milieu de la plage
6        if sorted_list[mid] == target:  # 2. comparaison
7            return mid                  # 4. trouvé - renvoie la position
8        elif sorted_list[mid] < target:
9            left = mid + 1              # 3. cherche dans la moitié droite
10        else:
11            right = mid - 1             # 3. cherche dans la moitié gauche
12    return -1                           # 4. introuvable
13
14species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
15print(binary_search(species, "Leo"))  # 2

La liste doit être triée : sinon, la comparaison avec le milieu ne dit rien sur la moitié où se trouve l'espèce. Chaque tour élimine la moitié de la liste, donc même un million d'entrées ne demande qu'environ 20 comparaisons, soit O(log n).

Le tri intégré de Python

Python possède un tri intégré - Timsort (hybride merge sort + insertion sort).

1# 1. list.sort() - trie sur place (modifie la liste d'origine)
2animals = ["Tiger", "Elephant", "Lion", "Parrot"]
3animals.sort()  # Modifie animals
4print(animals)  # ['Elephant', 'Lion', 'Parrot', 'Tiger']
5
6# 2. sorted() - renvoie une nouvelle liste triée
7animals = ["Tiger", "Elephant", "Lion", "Parrot"]
8sorted_animals = sorted(animals)  # Nouvelle liste
9print(animals)  # ['Tiger', 'Elephant', 'Lion', 'Parrot'] - inchangée
10print(sorted_animals)  # ['Elephant', 'Lion', 'Parrot', 'Tiger']
11
12# 3. Tri avec une clé (key)
13animals = ["Tiger", "Elephant", "Lion", "Parrot"]
14sorted_by_length = sorted(animals, key=len)
15print(sorted_by_length)  # ['Lion', 'Tiger', 'Parrot', 'Elephant']
16
17# 4. Tri inversé
18animals.sort(reverse=True)
19print(animals)  # ['Tiger', 'Parrot', 'Lion', 'Elephant']
20
21# 5. Trier un dict par valeurs
22species_count = {"Python": 5, "Leo": 3, "Elephas": 8}
23sorted_species = sorted(species_count.items(), key=lambda x: x[1], reverse=True)
24print(sorted_species)  # [('Elephas', 8), ('Python', 5), ('Leo', 3)]

Complexité de Timsort : O(n log n) dans le pire cas, O(n) dans le meilleur cas

Mais comprendre les algorithmes de tri classiques t'aidera à :

• Comprendre comment fonctionne le tri "en coulisses"
• Résoudre des questions d'entretien
• Choisir le bon algorithme pour des cas spécifiques

Tri à bulles (Bubble Sort)

Idée : Comparer les éléments adjacents et les échanger s'ils sont dans le mauvais ordre. Répéter jusqu'à ce que tout soit trié.

Analogie de safari : Comme des bulles d'air dans l'eau - à chaque passage, le plus grand élément non trié "remonte" jusqu'à la fin de la liste, comme une bulle vers la surface.

1def bubble_sort(arr):
2    """
3    Tri à bulles - O(n²)
4
5    Algorithme :
6    1. Parcourir toute la liste
7    2. Comparer chaque paire d'éléments adjacents
8    3. Les échanger s'ils sont dans le mauvais ordre
9    4. Répéter jusqu'à ce que rien ne change
10    """
11    n = len(arr)
12
13    for i in range(n):
14        # Après chaque itération, le plus grand élément "remonte" vers la fin
15        swapped = False  # Optimisation - si rien n'a changé, la liste est triée
16
17        for j in range(0, n - i - 1):  # Ignore les i derniers éléments (déjà triés)
18            if arr[j] > arr[j + 1]:
19                # Échange
20                arr[j], arr[j + 1] = arr[j + 1], arr[j]
21                swapped = True
22
23        if not swapped:
24            break  # Liste déjà triée
25
26    return arr
27
28# Exemple
29species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
30sorted_species = bubble_sort(species.copy())
31print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
32
33# Étape par étape :
34# Passe 1 : ["Leo", "Elephas", "Gorilla", "Panthera", "Python"]  # Python a "remonté"
35# Passe 2 : ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Panthera a "remonté"
36# Passe 3 : ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Déjà trié

Complexité :

• Temps : O(n²) pire et moyen cas, O(n) meilleur cas (pour une liste déjà triée)
• Mémoire : O(1) - trie sur place
• Stable : Oui - préserve l'ordre des éléments égaux

Avantages : Simple, stable, bon pour de petites données ou presque triées Inconvénients : Très lent pour de grandes données - O(n²)

Tri par sélection (Selection Sort)

Idée : Trouver le plus petit élément et le placer au début. Trouver le deuxième plus petit et le placer en deuxième position. Répéter.

Analogie de safari : Choisir la plus petite espèce une par une pour un catalogue trié.

1def selection_sort(arr):
2    """
3    Tri par sélection - O(n²)
4
5    Algorithme :
6    1. Trouver le plus petit élément de la partie non triée
7    2. L'échanger avec le premier élément de la partie non triée
8    3. Déplacer la frontière triée de 1
9    4. Répéter
10    """
11    n = len(arr)
12
13    for i in range(n):
14        # Trouver l'index du plus petit élément de la partie non triée
15        min_index = i
16        for j in range(i + 1, n):
17            if arr[j] < arr[min_index]:
18                min_index = j
19
20        # Échanger le plus petit élément avec le premier non trié
21        arr[i], arr[min_index] = arr[min_index], arr[i]
22
23    return arr
24
25# Exemple
26species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
27sorted_species = selection_sort(species.copy())
28print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
29
30# Étape par étape :
31# i=0 : ["Elephas", "Leo", "Python", "Gorilla", "Panthera"]  # Min trouvé : Elephas
32# i=1 : ["Elephas", "Gorilla", "Python", "Leo", "Panthera"]  # Min trouvé : Gorilla
33# i=2 : ["Elephas", "Gorilla", "Leo", "Python", "Panthera"]  # Min trouvé : Leo
34# i=3 : ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Min trouvé : Panthera
35# i=4 : Terminé

Complexité :

• Temps : O(n²) toujours - même pour une liste triée !
• Mémoire : O(1) - trie sur place
• Stable : Non - peut changer l'ordre des éléments égaux

Avantages : Simple, temps prévisible, peu d'échanges Inconvénients : Lent - toujours O(n²), instable

Tri par insertion (Insertion Sort)

Idée : Construire une liste triée élément par élément, en insérant chaque nouvel élément à la bonne position.

Analogie de safari : Comme ranger des cartes dans ta main - tu prends une carte et l'insères au bon endroit.

1def insertion_sort(arr):
2    """
3    Tri par insertion - O(n²)
4
5    Algorithme :
6    1. Commencer par le deuxième élément
7    2. Le comparer avec les éléments à sa gauche
8    3. Décaler les éléments plus grands vers la droite
9    4. Insérer l'élément à la bonne position
10    5. Répéter pour chaque élément
11    """
12    for i in range(1, len(arr)):
13        key = arr[i]  # Élément à insérer
14        j = i - 1
15
16        # Décaler les éléments plus grands que key d'une position vers la droite
17        while j >= 0 and arr[j] > key:
18            arr[j + 1] = arr[j]
19            j -= 1
20
21        # Insérer key à la bonne position
22        arr[j + 1] = key
23
24    return arr
25
26# Exemple
27species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
28sorted_species = insertion_sort(species.copy())
29print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
30
31# Étape par étape :
32# i=1 (Leo) :      ["Leo", "Python", "Elephas", "Gorilla", "Panthera"]
33# i=2 (Elephas) :  ["Elephas", "Leo", "Python", "Gorilla", "Panthera"]
34# i=3 (Gorilla) :  ["Elephas", "Gorilla", "Leo", "Python", "Panthera"]
35# i=4 (Panthera) : ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]

Complexité :

• Temps : O(n²) pire et moyen cas, O(n) meilleur cas (pour presque trié)
• Mémoire : O(1) - trie sur place
• Stable : Oui

Avantages : Simple, stable, excellent pour de petites données ou presque triées, en ligne (peut trier au fur et à mesure de la réception des données) Inconvénients : Lent pour de grandes données désordonnées - O(n²)

Timsort utilise le tri par insertion pour les petites sous-listes (<64 éléments) !

Tri fusion (Merge Sort)

Idée : Diviser la liste en moitiés, trier récursivement, fusionner les moitiés triées.

Analogie de safari : Diviser l'équipe en groupes plus petits, chaque groupe trie séparément, puis tu combines les résultats.

1def merge_sort(arr):
2    """
3    Tri fusion - O(n log n)
4
5    Algorithme (Diviser pour régner) :
6    1. Si la liste a 1 élément - déjà triée
7    2. Diviser la liste en deux moitiés
8    3. Trier chaque moitié récursivement
9    4. Fusionner les deux moitiés triées
10    """
11    if len(arr) <= 1:
12        return arr
13
14    # Diviser
15    mid = len(arr) // 2
16    left = merge_sort(arr[:mid])
17    right = merge_sort(arr[mid:])
18
19    # Fusionner
20    return merge(left, right)
21
22def merge(left, right):
23    """
24    Fusionner deux listes triées en une liste triée
25    """
26    result = []
27    i = j = 0
28
29    # Comparer les éléments des deux listes et ajouter le plus petit
30    while i < len(left) and j < len(right):
31        if left[i] <= right[j]:
32            result.append(left[i])
33            i += 1
34        else:
35            result.append(right[j])
36            j += 1
37
38    # Ajouter les éléments restants (une liste est vide)
39    result.extend(left[i:])
40    result.extend(right[j:])
41
42    return result
43
44# Exemple
45species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
46sorted_species = merge_sort(species)
47print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
48
49# Arbre de récursion :
50# ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
51#       /                                  \
52# ["Python", "Leo"]                  ["Elephas", "Gorilla", "Panthera"]
53#   /        \                           /                \
54# ["Python"] ["Leo"]               ["Elephas"]    ["Gorilla", "Panthera"]
55#                                                      /            \
56#                                                ["Gorilla"]    ["Panthera"]
57# Fusion :
58# ["Leo", "Python"]                 ["Elephas", "Gorilla", "Panthera"]
59#                \                    /
60#         ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

Complexité :

• Temps : O(n log n) toujours - pire, moyen, meilleur cas
• Mémoire : O(n) - crée de nouvelles listes lors de la fusion
• Stable : Oui

Avantages : O(n log n) prévisible, stable, bon pour de grandes données Inconvénients : Utilise de la mémoire supplémentaire O(n)

Tri rapide (Quick Sort)

Idée : Choisir un pivot, diviser la liste en éléments plus petits et plus grands que le pivot, trier chaque partie récursivement.

Analogie de safari : Choisir une espèce "médiane", diviser en plus petites et plus grandes, répéter.

1def quick_sort(arr):
2    """
3    Tri rapide - O(n log n) en moyenne, O(n²) dans le pire cas
4
5    Algorithme :
6    1. Si la liste a ≤1 élément - déjà triée
7    2. Choisir un pivot (ex. le dernier élément)
8    3. Diviser en : plus petit que le pivot, égal au pivot, plus grand que le pivot
9    4. Trier récursivement les plus petits et les plus grands
10    5. Combiner : [plus petits triés] + [pivot] + [plus grands triés]
11    """
12    if len(arr) <= 1:
13        return arr
14
15    # Choisir un pivot (ex. le dernier élément)
16    pivot = arr[-1]
17
18    # Diviser en 3 groupes
19    smaller = [x for x in arr[:-1] if x < pivot]
20    equal = [x for x in arr if x == pivot]
21    larger = [x for x in arr[:-1] if x > pivot]
22
23    # Trier récursivement et combiner
24    return quick_sort(smaller) + equal + quick_sort(larger)
25
26# Version plus efficace (sur place) :
27def quick_sort_inplace(arr, low=0, high=None):
28    """Tri rapide sur place avec partitionnement de Lomuto"""
29    if high is None:
30        high = len(arr) - 1
31
32    if low < high:
33        # Partitionner et obtenir l'index du pivot
34        pivot_index = partition(arr, low, high)
35
36        # Trier les parties avant et après le pivot
37        quick_sort_inplace(arr, low, pivot_index - 1)
38        quick_sort_inplace(arr, pivot_index + 1, high)
39
40    return arr
41
42def partition(arr, low, high):
43    """Partitionnement de Lomuto"""
44    pivot = arr[high]  # Choisir le dernier élément comme pivot
45    i = low - 1  # Index du plus petit élément
46
47    for j in range(low, high):
48        if arr[j] <= pivot:
49            i += 1
50            arr[i], arr[j] = arr[j], arr[i]
51
52    # Placer le pivot à la bonne position
53    arr[i + 1], arr[high] = arr[high], arr[i + 1]
54    return i + 1
55
56# Exemple
57species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
58sorted_species = quick_sort(species)
59print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

Complexité :

• Temps : O(n log n) en moyenne, O(n²) dans le pire cas (quand le pivot est toujours le pire choix)
• Mémoire : O(log n) récursion (version sur place)
• Stable : Non (implémentation standard)

Avantages : Très rapide en pratique, trie sur place (peu de mémoire) Inconvénients : Instable, O(n²) dans le pire cas, nécessite un bon choix de pivot

Comparaison des algorithmes de tri

Quel algorithme utiliser ?

1# Petites données (<50 éléments) ou presque triées
2# → Insertion Sort
3small_list = ["Python", "Leo", "Elephas"]
4insertion_sort(small_list)  # Rapide pour de petites données !
5
6# Grandes données, besoin de stabilité
7# → Merge Sort ou Python sort()
8import random
9
10large_list = [random.random() for _ in range(10000)]
11sorted_list = sorted(large_list)  # Timsort - stable !
12
13# Grandes données, mémoire limitée, pas besoin de stabilité
14# → Quick Sort (sur place)
15import random
16
17large_list = [random.random() for _ in range(10000)]
18quick_sort_inplace(large_list)  # Peu de mémoire !
19
20# En pratique : utilise TOUJOURS le sort() ou sorted() de Python
21# Ils sont optimisés, stables et très rapides (Timsort) !
22animals.sort()  # Le meilleur choix dans 99% des cas !

Trier les espèces selon différents critères

Tu peux construire une clé de tri à partir de n'importe quelle information sur une espèce. Ci-dessous, la même liste de dictionnaires est triée de trois façons ; lambda s: s["name"] est une courte fonction qui donne, pour chaque espèce, la valeur à comparer (nous la verrons plus en détail dans le projet à la fin du module) :

1species_list = [
2    {"name": "Python regius", "size": 1.5, "dangerous": False},
3    {"name": "Panthera leo", "size": 2.5, "dangerous": True},
4    {"name": "Elephas maximus", "size": 3.5, "dangerous": False},
5    {"name": "Crocodylus niloticus", "size": 4.5, "dangerous": True},
6    {"name": "Gorilla gorilla", "size": 1.8, "dangerous": False}
7]
8
9# 1. Trier par nom
10sorted_by_name = sorted(species_list, key=lambda s: s["name"])
11for s in sorted_by_name:
12    print(s["name"])
13# Crocodylus niloticus, Elephas maximus, Gorilla gorilla, Panthera leo, Python regius
14
15# 2. Trier par taille (décroissant)
16sorted_by_size = sorted(species_list, key=lambda s: s["size"], reverse=True)
17for s in sorted_by_size:
18    print(f"{s['name']}: {s['size']}m")
19# Crocodylus niloticus: 4.5m, Elephas maximus: 3.5m, Panthera leo: 2.5m, ...
20
21# 3. D'abord les dangereux, puis du plus grand au plus petit
22sorted_by_danger_size = sorted(species_list, key=lambda s: (not s["dangerous"], -s["size"]))
23for s in sorted_by_danger_size:
24    danger = "dangereux" if s["dangerous"] else "sans danger"
25    print(f"{s['name']}: {s['size']}m ({danger})")
26# Crocodylus niloticus: 4.5m (dangereux)
27# Panthera leo: 2.5m (dangereux)
28# Elephas maximus: 3.5m (sans danger)
29# ...

Tri par comptage (Counting Sort) - Pour des cas particuliers

Si l'on trie des entiers dans une plage limitée, on peut utiliser le Counting Sort - O(n + k) !

1def counting_sort(arr, max_value):
2    """
3    Tri par comptage - O(n + k) où k = max_value
4
5    Fonctionne uniquement pour des entiers dans la plage [0, max_value]
6    """
7    # Compter les occurrences de chaque nombre
8    count = [0] * (max_value + 1)
9    for num in arr:
10        count[num] += 1
11
12    # Construire la liste triée
13    sorted_arr = []
14    for num, freq in enumerate(count):
15        sorted_arr.extend([num] * freq)
16
17    return sorted_arr
18
19# Exemple de safari : Trier le nombre de découvertes (0-100)
20daily_discoveries = [5, 3, 8, 3, 12, 5, 7, 3, 10, 5]
21sorted_discoveries = counting_sort(daily_discoveries, max(daily_discoveries))
22print(sorted_discoveries)  # [3, 3, 3, 5, 5, 5, 7, 8, 10, 12]
23
24# O(n) pour une plage limitée ! Plus rapide que O(n log n) pour un grand n !

Exemple pratique - Système de catalogage

L'exemple ci-dessous regroupe la liste et ses fonctions dans une classe - tu découvriras les classes au module 3, alors lis-le pour l'instant comme un ensemble de fonctions qui travaillent sur une seule liste :

1class SpeciesCatalog:
2    """Système de catalogage des espèces avec différents tris"""
3
4    def __init__(self):
5        self.species = []
6
7    def add_species(self, name, size, habitat, dangerous):
8        """Ajoute une espèce au catalogue"""
9        self.species.append({
10            "name": name,
11            "size": size,
12            "habitat": habitat,
13            "dangerous": dangerous
14        })
15
16    def sort_by_name(self):
17        """Trie par ordre alphabétique"""
18        return sorted(self.species, key=lambda s: s["name"])
19
20    def sort_by_size(self, descending=True):
21        """Trie par taille"""
22        return sorted(self.species, key=lambda s: s["size"], reverse=descending)
23
24    def sort_by_danger_then_size(self):
25        """Trie : les dangereux d'abord, puis par taille"""
26        return sorted(self.species, key=lambda s: (not s["dangerous"], -s["size"]))
27
28    def filter_and_sort(self, habitat=None, min_size=None, sort_by="name"):
29        """Filtre et trie"""
30        filtered = self.species
31
32        if habitat:
33            filtered = [s for s in filtered if s["habitat"] == habitat]
34
35        if min_size:
36            filtered = [s for s in filtered if s["size"] >= min_size]
37
38        if sort_by == "name":
39            return sorted(filtered, key=lambda s: s["name"])
40        elif sort_by == "size":
41            return sorted(filtered, key=lambda s: s["size"], reverse=True)
42
43        return filtered
44
45# Utilisation
46catalog = SpeciesCatalog()
47catalog.add_species("Python regius", 1.5, "jungle", False)
48catalog.add_species("Panthera leo", 2.5, "savanna", True)
49catalog.add_species("Elephas maximus", 3.5, "jungle", False)
50catalog.add_species("Crocodylus niloticus", 4.5, "river", True)
51
52# Grandes espèces de la jungle triées par taille
53jungle_large = catalog.filter_and_sort(habitat="jungle", min_size=2.0, sort_by="size")
54for s in jungle_large:
55    print(f"{s['name']}: {s['size']}m")
56# Elephas maximus: 3.5m

Exercice pratique

L'éditeur contient des distances jusqu'à un point d'eau et une liste de serpents :

1. Trie la liste distances par ordre croissant avec sort() et affiche-la
2. Avec sorted() et reverse=True, construis à partir de species une nouvelle liste décroissante sans modifier l'originale

1# Trier des listes
2# .sort() modifie la liste d'origine, sorted() en crée une nouvelle
3
4animal_weights = [450, 120, 5000, 30, 900, 1500]
5animal_names = ["cheetah", "lion", "elephant", "zebra", "antelope", "buffalo"]
6
7# sort() - trie sur place (modifie la liste d'origine)
8animal_weights.sort()
9print(f"Poids croissants : {animal_weights}")
10
11animal_weights.sort(reverse=True)
12print(f"Poids décroissants : {animal_weights}")
13
14# sorted() - renvoie une NOUVELLE liste triée
15sorted_names = sorted(animal_names)
16print(f"\nNoms par ordre alphabétique : {sorted_names}")
17print(f"Liste d'origine : {animal_names}")  # Inchangée !
18
19# TODO : Crée une liste de distances jusqu'à un point d'eau (en km)
20distances = [12.5, 3.2, 8.7, 1.1, 15.3, 6.4]
21
22# TODO : Trie distances par ordre croissant avec .sort()
23
24
25# TODO : Affiche la liste triée
26print(f"Distances croissantes : {distances}")
27
28# TODO : Utilise sorted() avec reverse=True pour l'ordre décroissant SANS modifier la liste d'origine
29species = ["python", "cobra", "mamba", "anaconda", "boa"]
30sorted_desc = sorted(species)  # Ajoute reverse=True
31print(f"Espèces décroissantes : {sorted_desc}")
32

Résumé

Dans cette leçon, tu as appris :

• Pourquoi le tri est important
• Comment fonctionne la recherche binaire et pourquoi elle exige une liste triée
• Les fonctions intégrées sort() et sorted() de Python
• Bubble Sort, Selection Sort, Insertion Sort (O(n²))
• Merge Sort et Quick Sort (O(n log n))
• Les comparaisons d'algorithmes de tri
• Quel algorithme utiliser
• Trier des dictionnaires selon différents critères avec key
• Counting Sort pour des cas particuliers

Point de contrôle

Avant de continuer :

• Tu comprends comment fonctionnent les algorithmes de tri de base
• Tu connais la différence entre les algorithmes O(n²) et O(n log n)
• Tu sais utiliser sort() et sorted() avec le paramètre key
• Tu sais quand utiliser un tri stable
• Tu comprends le compromis entre temps et mémoire
• Tu sais choisir le bon algorithme pour une situation donnée

En pratique : Utilise le sort() ou sorted() de Python - ils sont optimisés et fonctionnent parfaitement dans 99% des cas !

Dans la prochaine leçon, tu rassembleras tout dans le projet Traqueur d'espèces de safari !