Qu'est-ce qu'un invariant de boucle ?

Une propriété vraie à chaque itération de la boucle

Comment s'effectue un échange de deux variables a et b en Python ?

Les réponses B et C sont correctes

Pourquoi le tri par insertion est-il préféré au tri par sélection pour des listes presque triées ?

Sa complexité descend à O(n) quand la liste est presque triée

Combien de comparaisons fait le tri par sélection sur une liste de 10 éléments ?

45. Le tri par sélection fait n(n-1)/2 = 10×9/2 = 45 comparaisons.

Qu'est-ce qu'un invariant de boucle ?

Une propriété vraie à chaque itération de la boucle. Un invariant de boucle est une propriété qui reste vraie avant et après chaque itération, servant à prouver la correction de l'algorithme.

Comment s'effectue un échange de deux variables a et b en Python ?

Les réponses B et C sont correctes. En Python, a, b = b, a est l'échange simultané. L'utilisation d'une variable temporaire (B) fonctionne aussi dans tous les langages.

Quel algorithme de tri est utilisé par la fonction sorted() de Python ?

Timsort (hybride). Python utilise Timsort, un algorithme hybride (fusion + insertion) en O(n log n), bien plus efficace que les tris en O(n²).

Après 3 itérations du tri par sélection sur [5, 3, 8, 1, 4], quel est l'état ?

[1, 3, 4, 8, 5]. Itération 1 : min=1, échange avec 5 → [1,3,8,5,4]. Itération 2 : min=3, déjà en place → [1,3,8,5,4]. Itération 3 : min=4, échange avec 8 → [1,3,4,5,8]. Correction: [1,3,4,8,5] après itération 3 car on échange 4 et 8 → [1,3,4,5,8]. En fait, itération 3 cherche le min dans [8,5,4] = 4, échange avec 8 → [1,3,4,5,8].

Pourquoi le tri par insertion est-il préféré au tri par sélection pour des listes presque triées ?

Sa complexité descend à O(n) quand la liste est presque triée. Quand la liste est presque triée, le tri par insertion fait très peu de décalages, sa complexité est quasi-linéaire O(n).

NSI (Spé) — Algorithmique

Tri par sélection et tri par insertion

Q: Quel est le principe du tri par sélection ?

Chercher le minimum et le placer au début. Le tri par sélection cherche le minimum dans la partie non triée et le place au bon endroit, étape par étape.

Q: Quelle est la complexité du tri par sélection dans le pire cas ?

O(n²). Le tri par sélection effectue toujours n(n-1)/2 comparaisons, soit une complexité O(n²).

Q: Quelle analogie décrit le mieux le tri par insertion ?

Trier des cartes dans sa main. Le tri par insertion fonctionne comme quand on trie des cartes : on prend chaque carte et on l'insère à sa place parmi celles déjà triées.

Q: Quel est le meilleur cas du tri par insertion ?

Liste déjà triée. Si la liste est déjà triée, aucun décalage n'est nécessaire : la complexité est O(n), le meilleur cas possible.

Algorithmes de tri élémentaires : principe, implémentation, complexité

Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub

Résumé

Les algorithmes de tri ordonnent les éléments d'une liste selon un critère (croissant, décroissant). Le tri par sélection parcourt la liste pour trouver le minimum, le place en première position, puis recommence sur le reste de la liste. Le tri par insertion traite les éléments un par un : chaque nouvel élément est inséré à sa place dans la partie déjà triée, comme quand on trie des cartes dans sa main. Ces deux algorithmes ont une complexité quadratique O(n²) dans le pire cas, ce qui les rend inefficaces pour de grandes listes. Le tri par insertion est cependant plus rapide en pratique quand la liste est presque triée. Prouver qu'un algorithme de tri est correct nécessite de montrer un invariant de boucle : une propriété vraie à chaque itération.

Thème complet

Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale

Ce thème dans une autre classe

Seconde — Mathématiques

Algorithmique et programmation

Terminale — NSI (Spé)

Programmation orientée objet en Python

Terminale — NSI (Spé)

Calculabilité, décidabilité et mise au point

Articles utiles

Spécialités

Bac NSI 2026 : comment réussir l'épreuve écrite et pratique

Questions fréquentes

Les points clés à retenir sur Tri par sélection et tri par insertion, extraits du quiz de révision.

Quel est le principe du tri par sélection ?

Réponse : Chercher le minimum et le placer au début

Le tri par sélection cherche le minimum dans la partie non triée et le place au bon endroit, étape par étape.

Quelle est la complexité du tri par sélection dans le pire cas ?

Réponse : O(n²)

Le tri par sélection effectue toujours n(n-1)/2 comparaisons, soit une complexité O(n²).

Quelle analogie décrit le mieux le tri par insertion ?

Réponse : Trier des cartes dans sa main

Le tri par insertion fonctionne comme quand on trie des cartes : on prend chaque carte et on l'insère à sa place parmi celles déjà triées.

Quel est le meilleur cas du tri par insertion ?

Réponse : Liste déjà triée

Si la liste est déjà triée, aucun décalage n'est nécessaire : la complexité est O(n), le meilleur cas possible.

Résumé

Questions fréquentes

Les points clés à retenir sur Tri par sélection et tri par insertion, extraits du quiz de révision.

Quel est le principe du tri par sélection ?

Réponse : Chercher le minimum et le placer au début

Le tri par sélection cherche le minimum dans la partie non triée et le place au bon endroit, étape par étape.

Quelle est la complexité du tri par sélection dans le pire cas ?

Réponse : O(n²)

Le tri par sélection effectue toujours n(n-1)/2 comparaisons, soit une complexité O(n²).

Quelle analogie décrit le mieux le tri par insertion ?

Réponse : Trier des cartes dans sa main

Le tri par insertion fonctionne comme quand on trie des cartes : on prend chaque carte et on l'insère à sa place parmi celles déjà triées.

Quel est le meilleur cas du tri par insertion ?

Réponse : Liste déjà triée

Si la liste est déjà triée, aucun décalage n'est nécessaire : la complexité est O(n), le meilleur cas possible.

Tri par sélection et tri par insertion

Résumé