Comparaisons
Échanges
Passage

  • En cours d'insertion
  • Comparées
  • Échangées
  • Partie triée

En savoir plus sur le tri par insertion

Tri par insertion

Le tri par insertion fonctionne comme beaucoup de gens trient les cartes qu'ils ont en main. Il garde une partie triée au début de la liste, prend la valeur suivante et la fait reculer au-delà de chaque valeur plus grande jusqu'à ce qu'elle trouve sa place. Lancez le tri à la vitesse de votre choix, ou avancez d'une comparaison à la fois, et suivez les compteurs de comparaisons, d'échanges et de passages. Appuyez sur Lecture pour regarder le tri, ou sur Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. Les tuiles comptent les comparaisons, les échanges et les passages. Choisissez le nombre de barres, leur ordre de départ, ou saisissez vos propres nombres. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Choisissez le nombre de barres et leur ordre de départ : aléatoire, presque trié, inversé ou avec peu de valeurs distinctes. Ou saisissez vos propres nombres.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans le tri.
  3. Essayez une liste presque triée puis une liste inversée, et comparez le nombre de comparaisons de chacune.

Comment fonctionne le tri par insertion

La première valeur seule forme une partie triée. Prenez la deuxième valeur et comparez-la à celle qui la précède ; si celle-ci est plus grande, échangez-les, et continuez à comparer et à échanger jusqu'à ce que la valeur précédente ne soit pas plus grande ou que la valeur atteigne le début. Les deux premières valeurs sont alors dans l'ordre. Faites de même avec la troisième valeur, la quatrième, et ainsi de suite jusqu'à la fin de la liste.

Rapide sur les listes presque triées

Chaque passage s'arrête à la première valeur qui n'est pas plus grande : une valeur déjà proche de sa place ne coûte donc qu'une ou deux comparaisons. Une liste triée demande n − 1 comparaisons et aucun échange ; une liste inversée, le pire cas, demande n(n − 1)/2 de chaque. Le nombre d'échanges est toujours égal au nombre d'inversions de la liste de départ, c'est-à-dire de paires mal ordonnées. C'est pourquoi le tri par insertion sert souvent pour les listes courtes ou presque triées, et à l'intérieur de tris plus rapides pour finir les petits morceaux.

Questions fréquemment posées

Comment fonctionne le tri par insertion ?

Il construit une partie triée au début de la liste. Chaque passage prend la valeur suivante et la fait reculer au-delà de chaque valeur plus grande placée avant elle, jusqu'à ce qu'elle trouve sa place. Après le passage k, les k + 1 premières valeurs sont dans l'ordre, mais une valeur venue plus tard peut encore s'insérer entre elles.

Combien de comparaisons et d'échanges fait le tri par insertion ?

Le nombre d'échanges est toujours égal au nombre d'inversions de la liste de départ : aucun pour une liste triée, n(n − 1)/2 pour une liste inversée. Les comparaisons sont les échanges plus au plus une par passage, donc entre n − 1 et n(n − 1)/2.

Pourquoi le tri par insertion est-il rapide sur les listes presque triées ?

Parce qu'un passage s'arrête dès qu'il rencontre une valeur qui n'est pas plus grande. Quand chaque valeur est proche de sa place finale, chaque passage est court, et le tri entier prend un temps proche de n.

Le tri par insertion est-il stable ?

Oui. Une valeur ne dépasse que des valeurs strictement plus grandes, donc des valeurs égales ne se dépassent jamais et gardent leur ordre d'origine.

Mes nombres sont-ils envoyés quelque part ?

Non. Le tri s'exécute dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur