Algorithmes de Tri
Ranger des cartes dans l'ordre, classer des copies par note, trier des fichiers par date... Le tri est partout ! En informatique, c'est l'une des operations les plus fondamentales. Il existe des dizaines d'algorithmes de tri, mais en NSI 1ere, on se concentre sur deux tris simples : selection et insertion.
60 min Niveau 3/5 +40 XP
Objectifs
- Comprendre le principe du tri par selection
- Comprendre le principe du tri par insertion
- Implementer ces deux algorithmes en Python
- Analyser la complexite O(n²) de ces tris
Erreurs courantes
- !Confondre les indices i et j dans les boucles
- !Oublier d'echanger les elements (tri selection)
- !Mauvaise gestion des bornes des boucles
- !Modifier le tableau pendant le parcours sans precaution
Cours
Principe : a chaque etape, on cherche le minimum du sous-tableau non trie et on le place au debut.
Complexite
Meilleur
O(n²)
Moyen
O(n²)
Pire
O(n²)
Avantages
- + Simple a comprendre et implementer
- + Nombre d'echanges minimal O(n)
- + Tri en place (pas de memoire supplementaire)
Inconvenients
- - Toujours O(n²) meme si deja trie
- - Pas adapte aux grands tableaux
Tableau initial : [64, 25, 12, 22, 11]
Etape 1 : Chercher min dans [64, 25, 12, 22, 11] → 11
Echanger 64 et 11 → [11, 25, 12, 22, 64]
✓
Etape 2 : Chercher min dans [25, 12, 22, 64] → 12
Echanger 25 et 12 → [11, 12, 25, 22, 64]
✓ ✓
Etape 3 : Chercher min dans [25, 22, 64] → 22
Echanger 25 et 22 → [11, 12, 22, 25, 64]
✓ ✓ ✓
Etape 4 : Chercher min dans [25, 64] → 25
Deja en place → [11, 12, 22, 25, 64]
✓ ✓ ✓ ✓ ✓def tri_selection(tab):
"""
Trie le tableau en place par selection.
"""
n = len(tab)
for i in range(n - 1):
# Trouver l'indice du minimum dans tab[i:]
i_min = i
for j in range(i + 1, n):
if tab[j] < tab[i_min]:
i_min = j
# Echanger tab[i] et tab[i_min]
tab[i], tab[i_min] = tab[i_min], tab[i]
return tab
# Test
tableau = [64, 25, 12, 22, 11]
print(f"Avant : {tableau}")
tri_selection(tableau)
print(f"Apres : {tableau}") # [11, 12, 22, 25, 64]Quiz Tris
5 questions pour tester tes connaissances
Dans ce chapitre
- Tri par selection
- Tri par insertion
- Comparaison
- Complexite O(n²)
A retenir
Selection : toujours O(n²), peu d'echanges.
Insertion : O(n) si presque trie, beaucoup de decalages.
Pour les grands tableaux → tri fusion O(n log n) !
