Tris par sélection, à bulles, par insertion et par comptage : cours et exercices corrigés
Le problème du tri, tris en place, tri par sélection, tri à bulles, tri par insertion, tri par comptage ; terminaison, invariants, nombre de comparaisons et d'échanges, stabilité, choix d'un tri.
- 17méthodes
- 33exercices corrigés
- 3problèmes
- 20pièges
- 40figures
Le tri par sélection place à chaque tour le minimum de la partie restante, le tri à bulles échange les voisins mal rangés, le tri par insertion range chaque élément dans le début déjà trié, par décalages : tous trois sont en place et font au pire comparaisons, soit 4 950 pour 100 éléments ; leur coût est quadratique, en . Le tri par comptage, qui ne compare jamais, trie des entiers de 0 à en . Ce chapitre d'informatique commune de première année, au programme de MPSI, PCSI, PTSI, TSI et TPC, au Maroc et en France, déroule chaque tri à la main, le prouve par un invariant, compte ses comparaisons et ses échanges, dit s'il est stable, puis apprend à trier des couples selon une clé, dans l'ordre décroissant ou selon deux critères. Les exercices et problèmes reprennent des questions des sujets du CNC, de CCINP, de Mines-Ponts et de Centrale-Supélec. Le meilleur et le pire cas de chaque tri, demandés au programme marocain, sont donnés dans une partie qui lui est propre.
Ce que tu sauras faire
Trier, c'est ranger les éléments d'une liste dans l'ordre : les caisses du jour de la plus légère à la plus lourde, les lots d'un registre par numéro, des mots dans l'ordre du dictionnaire. Une liste triée se consulte plus vite (recherche dichotomique), se compare plus facilement et met côte à côte les valeurs égales ou voisines. À la fin de ce chapitre, tu dois savoir :
- spécifier un tri et dire s'il est en place, stable, comparatif ;
- écrire, dérouler à la main et prouver le tri par sélection, le tri à bulles et le tri par insertion ;
- compter leurs comparaisons et leurs échanges dans le pire des cas, et reconnaître un coût quadratique ;
- écrire le tri par comptage et dire quand il est plus rapide qu'un tri par comparaisons ;
- trier des couples selon une clé, dans l'ordre croissant ou décroissant, et selon deux critères ;
- reconnaître un tri dans un code donné, le nommer et donner son coût.
L'essentiel : Le tableau des tris Extrait gratuit
| tri | en place | stable | comparatif | comparaisons au pire | échanges ou écritures au pire |
|---|---|---|---|---|---|
| sélection | oui | non | oui | échanges | |
| à bulles | oui | oui | oui | échanges | |
| insertion | oui | oui | oui | décalages | |
| comptage | non | oui, s'il place les éléments | non | aucune | écritures |
- Trois tris quadratiques, en dans le pire des cas ; le comptage en , linéaire si reste de l'ordre de .
- La sélection fait comparaisons sur toute liste, même triée ; l'insertion et les bulles avec arrêt n'en font que sur une liste triée.
- Échanges des bulles = décalages de l'insertion = nombre d'inversions (couples avec
L[i] > L[j]), au plus . - Quand double, le temps d'un tri quadratique est multiplié par environ 4.
Une méthode du chapitre Extrait gratuit
L'énoncé demande un tri par insertion, un tri efficace sur une liste presque triée, ou un tri stable en place.
Au tour , L[0:i] est trié ; on met x = L[i] de côté, on décale d'une case vers la droite les éléments de L[0:i] strictement plus grands que x, et on pose x dans la place libérée. La condition s'écrit j > 0 and L[j - 1] > x, la borne en premier.
- Boucle
for i in range(1, n). x = L[i]etj = i.while j > 0 and L[j - 1] > x:L[j] = L[j - 1], puisj = j - 1.- Après la boucle,
L[j] = x.
for i in range(1, len(L)):
x = L[i]
j = i
while j > 0 and L[j - 1] > x:
L[j] = L[j - 1]
j = j - 1
L[j] = x
« Au début du tour , L[0:i] est formé des premiers éléments de départ, triés ; le tour y insère x à sa place par décalages. »
On trie [4, 2, 5, 1] en affichant, à chaque tour, la valeur insérée, sa place et la liste.
L = [4, 2, 5, 1]
for i in range(1, len(L)):
x = L[i]
j = i
while j > 0 and L[j - 1] > x:
L[j] = L[j - 1]
j = j - 1
L[j] = x
print(i, x, j, L)
Le programme affiche :
1 2 0 [2, 4, 5, 1]
2 5 2 [2, 4, 5, 1]
3 1 0 [1, 2, 4, 5]
Au tour 2, 5 est déjà plus grand que tout le début : aucun décalage. Au tour 3, 1 traverse tout le début trié.
- Écrire
L[j] = L[j - 1]sans avoir misL[i]de côté : la valeur à insérer est écrasée au premier décalage. Les correcteurs du concours Mines-Ponts (rapport 2018, question 16) notent que « le rôle de la variable tmp n'a pas toujours été perçue clairement par les candidats ». - Inverser les conditions du
while:L[-1]est lu quand vaut 0. - Oublier la dernière affectation
L[j] = x.
Exercices 5, 6, 8, 15, 19, 24 et 29, problèmes 1 et 3.
Un exercice corrigé Extrait gratuit
On veut trier dans l'ordre croissant la liste L = [17, 5, 3, 21, 2].
- Dérouler à la main le tri par sélection : donner la liste après chaque tour de la boucle externe, avec l'indice du minimum échangé.
- Même question pour le tri à bulles avec arrêt anticipé (liste après chaque passage) et pour le tri par insertion (liste après chaque tour).
- Pour chacun des trois tris, compter les comparaisons et les échanges (ou les décalages, pour l'insertion). Combien
La-t-elle d'inversions ? Quel lien voit-on ?
- Méthode 8 : on écrit une ligne par tour, comme sur un document réponse ; on ne saute aucun tour, même quand la liste ne change pas.
- Méthode 10 : au tour , la sélection fait comparaisons ; l'insertion s'arrête au premier élément qui n'est pas plus grand que la valeur mise de côté.
- Une inversion est un couple d'indices tel que
L[i] > L[j](cours, section 5.2).
Les trois tris rangent la même liste, mais pas de la même façon. La sélection place à chaque tour la plus petite valeur restante en tête de la partie non triée : la partie de gauche est définitive. Les bulles poussent à chaque passage la plus grande valeur restante au bout : c'est la fin de la liste qui devient définitive. L'insertion range la valeur suivante dans le début déjà trié, qui reste provisoire. Pour ne pas se tromper dans les comptes, on écrit des versions des trois tris qui affichent la liste après chaque tour et comptent ce qu'elles font.
1., 2. et 3. Les trois fonctions suivantes font exactement les mêmes opérations que tri_selection, tri_bulles_arret et tri_insertion ; elles affichent en plus la liste après chaque tour et renvoient le couple (comparaisons, échanges ou décalages).
def trace_selection(L):
# trie L comme tri_selection et affiche (i, k, L)
# après chaque tour ; renvoie (comparaisons, échanges)
n = len(L)
comp = 0
ech = 0
for i in range(n - 1):
k = i
for j in range(i + 1, n):
comp = comp + 1
if L[j] < L[k]:
k = j
L[i], L[k] = L[k], L[i]
ech = ech + 1
print(i, k, L)
return (comp, ech)
def trace_bulles(L):
# trie L comme tri_bulles_arret et affiche L après
# chaque passage ; renvoie (comparaisons, échanges)
n = len(L)
p = 0
comp = 0
ech = 0
echange_fait = True
while echange_fait:
echange_fait = False
for j in range(n - 1 - p):
comp = comp + 1
if L[j] > L[j + 1]:
L[j], L[j + 1] = L[j + 1], L[j]
ech = ech + 1
echange_fait = True
p = p + 1
print(p, L)
return (comp, ech)
def trace_insertion(L):
# trie L comme tri_insertion et affiche (i, L)
# après chaque tour ; renvoie (comparaisons,
# décalages)
comp = 0
dec = 0
for i in range(1, len(L)):
x = L[i]
j = i
while j > 0 and L[j - 1] > x:
comp = comp + 1
L[j] = L[j - 1]
dec = dec + 1
j = j - 1
if j > 0:
comp = comp + 1 # comparaison qui arrête
L[j] = x
print(i, L)
return (comp, dec)
print(trace_selection([17, 5, 3, 21, 2]))
print(trace_bulles([17, 5, 3, 21, 2]))
print(trace_insertion([17, 5, 3, 21, 2]))
print(nb_inversions([17, 5, 3, 21, 2]))
Le programme affiche :
0 4 [2, 5, 3, 21, 17]
1 2 [2, 3, 5, 21, 17]
2 2 [2, 3, 5, 21, 17]
3 4 [2, 3, 5, 17, 21]
(10, 4)
1 [5, 3, 17, 2, 21]
2 [3, 5, 2, 17, 21]
3 [3, 2, 5, 17, 21]
4 [2, 3, 5, 17, 21]
5 [2, 3, 5, 17, 21]
(10, 7)
1 [5, 17, 3, 21, 2]
2 [3, 5, 17, 21, 2]
3 [3, 5, 17, 21, 2]
4 [2, 3, 5, 17, 21]
(8, 7)
7
- Sélection : au tour 2, le minimum de
[5, 21, 17]est déjà en tête ; on l'échange avec lui-même, et la liste ne change pas. Le tri fait comparaisons et 4 échanges, un par tour. - Bulles : quatre passages, chacun plus court que le précédent ( comparaisons). Le quatrième passage fait encore un échange : le drapeau reste vrai, et la boucle
whilefait un cinquième tour, sur une zone vide, sans aucune comparaison, avant de s'arrêter. Le 2, tout au bout au départ, n'avance que d'une place par passage. - Insertion : 8 comparaisons et 7 décalages. Au tour 3, le 21 est comparé au 17 et reste en place.
Interprétation : la liste a 7 inversions ; les bulles font 7 échanges et l'insertion 7 décalages. Chaque échange de deux voisins mal rangés, comme chaque décalage, corrige exactement une inversion (cours, section 5.2). La sélection fait moins d'échanges (4), mais toujours 10 comparaisons.
Une trace s'écrit une ligne par tour, sans en sauter. Pour compter, on additionne le travail de chaque tour : au plus. Voir les méthodes 8 et 10.
Le cours détaillé, toute la fiche « L'essentiel », 17 méthodes, 20 pièges corrigés, la carte mentale, 33 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Les trois premiers chapitres de chaque matière sont offerts avec un compte d’essai gratuit.
Ouvrir l'essai gratuitVoir les offresPlan du cours
- 1. Trier : le problème
- 1.1 Le besoin
- 1.2 Spécifier un tri
- 1.3 En place ou par copie
- 1.4 Échanger deux éléments
- 1.5 Trois mots pour classer les tris
- 2. Le tri par sélection
- 2.1 L'idée
- 2.2 Dérouler à la main
- 2.3 Le code
- 2.4 Terminaison et correction
- 2.5 Combien de comparaisons et d'échanges ?
- 2.6 Un tri qui n'est pas stable
- 3. Le tri à bulles
- 3.1 L'idée
- 3.2 Dérouler à la main
- 3.3 Le code
- 3.4 S'arrêter plus tôt
- 3.5 Un tri stable
- 3.6 Lent, et pourquoi
- 4. Le tri par insertion
- 4.1 L'idée
- 4.2 Dérouler à la main
- 4.3 Le code
- 4.4 Terminaison et correction
- 4.5 Combien de comparaisons ?
- 4.6 Un tri stable
- 4.7 Insérer un élément dans une liste triée
- 5. Compter les opérations des trois tris
- 5.1 Le tableau
- 5.2 Les inversions
- 5.3 Un coût quadratique
- 5.4 Mesurer
- 5.5 La mémoire
- 5.6 Meilleur cas et pire cas des trois tris
- 6. Le tri par comptage
- 6.1 L'idée
- 6.2 Le code
- 6.3 Terminaison et correction
- 6.4 Le coût, et sa condition
- 6.5 Des valeurs entre un minimum et un maximum
- 6.6 Placer les éléments eux-mêmes
- 7. Trier selon une clé
- 7.1 Des couples
- 7.2 L'ordre décroissant
- 7.3 Des chaînes
- 7.4 Deux critères
- 8. Choisir un tri
- 8.1 Le tableau des tris
- 8.2 Quel tri pour quelle situation
- 8.3 Les tris de Python
- 8.4 Plus vite que
- 9. Compléments du programme marocain
- 9.1 Meilleur cas et pire cas des quatre tris
- 9.2
insert,pop(i)etdel - 9.3
sortedavec une clé - 9.4 La sélection avec
min,indexetpop
Les méthodes du chapitre
Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.
- Spécifier un tri et le tester
- Choisir entre trier en place et trier une copie
- Échanger deux éléments d'une liste
- Écrire le tri par sélection
- Écrire le tri à bulles, zone raccourcie et arrêt anticipé
- Écrire le tri par insertion par décalages
- Insérer un élément dans une liste déjà triée
- Dérouler un tri à la main
- Prouver un tri : variant, invariant, conclusion
- Compter les comparaisons et les échanges dans le pire des cas
- Écrire le tri par comptage et donner son coût
- Trier selon une clé
- Reconnaître un tri stable ou non, et le montrer
- Reconnaître un tri dans un code donné
- Respecter les interdits d'un énoncé
- Donner le meilleur et le pire cas d'un tri
- Employer
insert,pop(i)etsortedavec une clé
Les exercices corrigés
Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.
Application directe (13)
- Trois tris sur la même rangée
- Le tri à bulles qui s'arrête
- Le minimum d'une fin de liste
- Un tri écrit avec pop et insert
- Trier des nombres, puis des motifs d'ADN
- La machine mystère des photos
- L'histogramme d'une photo, puis son tri
- Stable ou non : les villes du même degré
- Mêmes éléments, mêmes effectifs
- Une médiane par un tri au choix
- Le tri par dénombrement à la main
- Décroissant, sans renverser et sans toucher à l'original
- Meilleur cas, pire cas des quatre tris
Entraînement (15)
- Un tri pour des études statistiques, suite
- Trier une équipe selon une colonne
- La congestion, médiane par insertion
- Une seule ligne déplacée
- Le catalogue des chocs
- Des compteurs dans les tris
- Les couples mal rangés
- Quand la taille double
- Le comptage entre un minimum et un maximum
- Le registre par producteur, puis par poids
- Des bulles dans les deux sens
- Insérer par dichotomie
- Prouver le tri par sélection
- Prouver et chiffrer le tri par comptage
- sorted, une clé et deux critères
Approfondissement (5)
- Le comptage qui place les couples
- Trier par chiffres
- Trier les indices au lieu des éléments
- Trois couleurs en un seul passage
- La sélection avec min, index et pop
Les problèmes de concours
Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.
- Trier des chemins par leur longueur
- Un tri par répartition des sommets d'un graphe
- Trier des produits par rentabilité
Questions fréquentes
Comment écrire le tri par insertion en Python ?
Pour i de 1 à , on met x = L[i] de côté et l'on pose j = i ; tant que j > 0 and L[j - 1] > x, on décale L[j] = L[j - 1] et l'on diminue j de 1 ; après la boucle, L[j] = x. Le test de la borne vient en premier, sinon L[-1] est lu quand vaut 0, et sans x mis de côté la valeur à insérer est écrasée au premier décalage. Le tri est en place et ne renvoie rien. Il est stable, puisque le test L[j - 1] > x est strict. Sur une liste presque triée, il fait très peu de travail : pour 4 000 éléments triés dont on a échangé 10 paires, 24 027 comparaisons, contre 7 998 000 pour la sélection.
Quelle est la complexité du tri par sélection, du tri à bulles et du tri par insertion ?
Dans le pire des cas, une liste décroissante, les trois font comparaisons : 10 pour 5 éléments, 4 950 pour 100. Leur coût est quadratique, en , et quand double, le temps est multiplié par environ 4. La sélection fait comparaisons sur toute liste, même triée, mais au plus échanges. Le tri à bulles fait autant d'échanges, et l'insertion autant de décalages, que la liste a d'inversions, au plus . Sur une liste déjà triée, l'insertion et les bulles avec arrêt anticipé ne font que comparaisons. Une complexité s'annonce avec le cas qu'elle décrit ; au programme marocain, on donne le meilleur et le pire cas.
Qu'est-ce qu'un tri stable ?
Un tri est stable si deux éléments de même clé restent, après le tri, dans l'ordre où ils étaient avant. Cela compte dès qu'on trie des couples selon une seule composante, par exemple des caisses (producteur, poids) selon le poids. Le tri par insertion et le tri à bulles sont stables, grâce à leur comparaison stricte ; avec >=, le tri à bulles échange deux voisins égaux et perd la stabilité. Le tri par sélection n'est pas stable : son échange à grande distance fait sauter un élément par-dessus ses égaux. Pour trier selon deux critères, on trie d'abord selon le critère secondaire, puis, par un tri stable, selon le critère principal.
Quel est l'invariant du tri par sélection et du tri par insertion ?
Pour la sélection : au début du tour , L[0:i] est trié et ses éléments sont inférieurs ou égaux à ceux de L[i:n] ; ils sont à leur place définitive. Pour l'insertion : au début du tour , L[0:i] est formé des premiers éléments de la liste de départ, rangés dans l'ordre croissant ; leur place n'est que provisoire. Pour le tri à bulles : au début du passage , les derniers éléments sont les plus grands, rangés. On rédige chaque preuve en trois temps, initialisation, conservation et sortie, et l'on vérifie aussi que la liste a gardé les mêmes éléments. La boucle while de l'insertion termine, car est un variant.
Comment fonctionne le tri par comptage ?
Pour une liste d'entiers compris entre 0 et , on crée compteurs, C = [0] * k, on compte chaque valeur en un parcours, puis on écrit chaque valeur v autant de fois que C[v], dans l'ordre croissant. Pour [3, 1, 4, 1, 0, 3, 2, 1] et , C vaut [1, 3, 1, 2, 1] et le résultat [0, 1, 1, 1, 2, 3, 3, 4]. Le coût est en : le tri est linéaire si reste de l'ordre de , mais le terme l'emporte si les valeurs s'étalent sur un grand intervalle. Ce tri n'est ni comparatif ni en place : il renvoie une nouvelle liste. Pour des valeurs de à , on compte v dans la case v - a, avec cases.
Quelle différence entre sort et sorted en Python ?
L.sort() trie la liste L en place et renvoie None, sorted(L) renvoie une nouvelle liste triée et laisse L intacte ; tous deux sont stables. Un sujet qui demande d'écrire un tri les interdit souvent, et une réponse qui s'en sert alors ne rapporte rien : on sait toujours les remplacer par un tri écrit à la main. Les meilleurs tris par comparaison, comme le tri par fusion et le tri rapide, font de l'ordre de comparaisons : environ 130 000 pour 10 000 éléments, contre près de 50 millions pour . En France, sort et sorted sont hors de l'annexe du programme et ne s'emploient qu'avec la documentation du sujet ; au programme marocain, sorted s'emploie aussi avec une clé.
Comment y accéder
Ce chapitre fait partie de l'accès complet. Les trois premiers chapitres de chaque matière (deux par bloc en économie et droit, en management et gestion) sont offerts avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet et les tarifs, vois les offres.