Prepa Help
Prepa Help › Cours › Informatique, 1re année

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.

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

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 n(n−1)2\frac{n(n-1)}{2} comparaisons, soit 4 950 pour 100 éléments ; leur coût est quadratique, en O(n2)O(n^2). Le tri par comptage, qui ne compare jamais, trie des entiers de 0 à k−1k - 1 en O(n+k)O(n + k). 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 :

L'essentiel : Le tableau des tris Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

tri en place stable comparatif comparaisons au pire échanges ou écritures au pire
sélection oui non oui n(n−1)2\frac{n(n-1)}{2} n−1n - 1 échanges
à bulles oui oui oui n(n−1)2\frac{n(n-1)}{2} n(n−1)2\frac{n(n-1)}{2} échanges
insertion oui oui oui n(n−1)2\frac{n(n-1)}{2} n(n−1)2\frac{n(n-1)}{2} décalages
comptage non oui, s'il place les éléments non aucune nn écritures
  • Trois tris quadratiques, en O(n2)O(n^2) dans le pire des cas ; le comptage en O(n+k)O(n + k), linéaire si kk reste de l'ordre de nn.
  • La sélection fait n(n−1)2\frac{n(n-1)}{2} comparaisons sur toute liste, même triée ; l'insertion et les bulles avec arrêt n'en font que n−1n - 1 sur une liste triée.
  • Échanges des bulles = décalages de l'insertion = nombre d'inversions (couples i<ji < j avec L[i] > L[j]), au plus n(n−1)2\frac{n(n-1)}{2}.
  • Quand nn double, le temps d'un tri quadratique est multiplié par environ 4.

Une méthode du chapitre Extrait gratuit

Un exercice corrigé Extrait gratuit

Dans le chapitre complet

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 offres

Plan du cours

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.

  1. Spécifier un tri et le tester
  2. Choisir entre trier en place et trier une copie
  3. Échanger deux éléments d'une liste
  4. Écrire le tri par sélection
  5. Écrire le tri à bulles, zone raccourcie et arrêt anticipé
  6. Écrire le tri par insertion par décalages
  7. Insérer un élément dans une liste déjà triée
  8. Dérouler un tri à la main
  9. Prouver un tri : variant, invariant, conclusion
  10. Compter les comparaisons et les échanges dans le pire des cas
  11. Écrire le tri par comptage et donner son coût
  12. Trier selon une clé
  13. Reconnaître un tri stable ou non, et le montrer
  14. Reconnaître un tri dans un code donné
  15. Respecter les interdits d'un énoncé
  16. Donner le meilleur et le pire cas d'un tri
  17. Employer insert, pop(i) et sorted avec 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)

Entraînement (15)

Approfondissement (5)

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.

Questions fréquentes

Comment écrire le tri par insertion en Python ?

Pour i de 1 à n−1n - 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 jj 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 n(n−1)2\frac{n(n-1)}{2} comparaisons : 10 pour 5 éléments, 4 950 pour 100. Leur coût est quadratique, en O(n2)O(n^2), et quand nn double, le temps est multiplié par environ 4. La sélection fait n(n−1)2\frac{n(n-1)}{2} comparaisons sur toute liste, même triée, mais au plus n−1n - 1 échanges. Le tri à bulles fait autant d'échanges, et l'insertion autant de décalages, que la liste a d'inversions, au plus n(n−1)2\frac{n(n-1)}{2}. Sur une liste déjà triée, l'insertion et les bulles avec arrêt anticipé ne font que n−1n - 1 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 ii, 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 ii, L[0:i] est formé des ii 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 pp, les pp derniers éléments sont les pp 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 jj est un variant.

Comment fonctionne le tri par comptage ?

Pour une liste d'entiers compris entre 0 et k−1k - 1, on crée kk 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 k=5k = 5, C vaut [1, 3, 1, 2, 1] et le résultat [0, 1, 1, 1, 2, 3, 3, 4]. Le coût est en O(n+k)O(n + k) : le tri est linéaire si kk reste de l'ordre de nn, mais le terme kk 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 aa à bb, on compte v dans la case v - a, avec b−a+1b - a + 1 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 nlog⁡2nn \log_2 n comparaisons : environ 130 000 pour 10 000 éléments, contre près de 50 millions pour n(n−1)2\frac{n(n-1)}{2}. 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.

Toute ta prépa au même endroit

Pour chaque chapitre : le cours, l'essentiel, les méthodes, les pièges, les exercices corrigés, les problèmes de concours, et un assistant qui répond à tes questions. Programmes du Maroc et de France. Avec la plateforme vidéo YOUNESS SCHOOL offerte, dès 600 DH (60 $) par mois, sans engagement.

Prépas scientifiques : voir l'offrePrépas ECS et ECT : voir l'offreTu hésites encore ? Essaie gratuitement Prepa Help.

← Tuples, dictionnaires et ensembles · Piles, files et deques →