Niveau : Difficile — Durée estimée : 90 min — 8 exercices avec corrections détaillées
Rappel des notions clés
Un algorithme de tri permet d'organiser une collection d'éléments selon un ordre défini (croissant ou décroissant). Le tri par sélection cherche le plus petit élément pour le placer au début, tandis que le tri par insertion construit la liste triée un élément à la fois en "insérant" chaque nouvelle donnée à sa place correcte.
La complexité algorithmique, notée $O(n)$, mesure l'efficacité d'un algorithme en fonction du nombre d'éléments $n$. Pour les tris simples (sélection, insertion, bulles), la complexité dans le pire des cas est généralement $O(n^2)$, car ils utilisent des boucles imbriquées.
Complexité : Tri Sélection = $O(n^2)$ | Tri Insertion = $O(n^2)$ | Tri Fusion = $O(n \log n)$
Exercices — Niveau Facile
Exercice 1 : Applique manuellement le tri par sélection sur la liste [5, 2, 9, 1]. Détaille chaque étape de l'échange.
Correction :
1. On cherche le min entre [5, 2, 9, 1] -> c'est 1. On l'échange avec 5. Liste : [1, 2, 9, 5].
2. On cherche le min entre [2, 9, 5] -> c'est 2. Il est déjà à sa place. Liste : [1, 2, 9, 5].
3. On cherche le min entre [9, 5] -> c'est 5. On l'échange avec 9. Liste : [1, 2, 5, 9].
La liste est triée.
Exercice 2 : Quel est l'avantage principal du tri par insertion par rapport au tri par sélection sur une liste déjà presque triée ?
Correction :
Le tri par insertion a une complexité de $O(n)$ dans le meilleur des cas (liste déjà triée), car il ne fait qu'une comparaison par élément sans déplacement. Le tri par sélection, lui, reste en $O(n^2)$ car il parcourt systématiquement le reste de la liste pour chercher le minimum.
Exercices — Niveau Moyen
Exercice 3 : Écris en pseudo-code l'algorithme du tri par insertion.
Correction :
Pour i allant de 1 à longueur(A)-1 : cle = A[i] j = i - 1 Tant que j >= 0 et A[j] > cle : A[j + 1] = A[j] j = j - 1 A[j + 1] = cle
Exercice 4 : Si une liste contient 1000 éléments, combien d'itérations environ le tri par sélection effectuera-t-il dans la boucle interne ?
Correction :
La complexité est $O(n^2)$. Plus précisément, c'est $\frac{n(n-1)}{2}$. Pour $n=1000$, cela fait environ $1000^2 / 2 = 500\,000$ itérations.
Exercice 5 : Explique pourquoi le tri par sélection est considéré comme un algorithme "en place" (in-place).
Correction :
Il est "en place" car il ne nécessite pas de structure de données supplémentaire (comme une deuxième liste) pour trier les éléments. Il utilise uniquement une quantité constante $O(1)$ de mémoire additionnelle pour les variables temporaires lors des échanges.
Exercices — Niveau Difficile
Exercice 6 : On considère un algorithme dont la complexité est $T(n) = 3n^2 + 10n + 5$. Quelle est sa complexité au sens de la notation Grand O ? Justifie.
Correction :
En notation Grand O, on ne garde que le terme de plus haut degré et on ignore les constantes multiplicatives.
Ici, quand $n$ devient très grand, $n^2$ domine largement $n$ et les constantes.
La complexité est donc $O(n^2)$.
Exercice 7 : Compare les performances du tri par insertion et du tri fusion (Merge Sort) pour une liste de 1 000 000 d'éléments. Quel est le meilleur choix ?
Correction :
Tri insertion ($O(n^2)$) -> $10^{12}$ opérations. Tri fusion ($O(n \log n)$) -> $10^6 \times 20 \approx 2 \times 10^7$ opérations.
Le Tri Fusion est infiniment plus rapide pour de grandes quantités de données.
Exercice 8 : Code en Python une fonction qui implémente le tri par sélection et compte le nombre d'échanges effectués.
Correction :
def tri_selection_compte(L): echanges = 0 for i in range(len(L)): min_idx = i for j in range(i+1, len(L)): if L[j] < L[min_idx]: min_idx = j if min_idx != i: L[i], L[min_idx] = L[min_idx], L[i] echanges += 1 return L, echanges
Bilan et conseils
Ce qu'il faut retenir : Le choix d'un algorithme de tri dépend de la taille de tes données et de leur état initial. Pour des petits tableaux, l'insertion est efficace. Pour du Big Data, privilégie toujours des complexités en $O(n \log n)$.
Comment ORBITECH Peut T'aider
ORBITECH AI Academy met à ta disposition des outils concrets pour réviser plus efficacement et progresser à ton rythme.
- Générateur de Quiz : crée des quiz personnalisés pour tester tes connaissances et identifier tes lacunes.
- Générateur d'Exercices : crée des exercices d'entraînement adaptés à ton niveau avec corrections détaillées.
- Générateur de Résumés : transforme tes cours en fiches de révision claires et structurées.
- Générateur de Mind Maps : visualise et organise tes idées avec des cartes mentales générées automatiquement.
Tous ces outils sont disponibles sur ta plateforme ORBITECH. Connecte-toi et explore ceux qui correspondent le mieux à tes besoins !