Comparaisons
Écritures
Fusions

  • Partie en fusion
  • Comparées
  • Réécrites
  • Déjà fusionnées

En savoir plus sur le tri fusion

Tri fusion

Le tri fusion est un algorithme « diviser pour régner ». Il coupe la liste en deux, trie chaque moitié de la même façon, puis fusionne les deux moitiés triées en prenant à chaque fois la plus petite valeur de tête. Regardez les moitiés passer dans une rangée tampon puis revenir dans l'ordre, à la vitesse voulue ou une étape à la fois, et comptez les comparaisons, les écritures et les fusions. Appuyez sur Lecture pour regarder le tri, ou sur Étape et Retour pour avancer d'une étape à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. Les tuiles comptent les comparaisons, les écritures dans la liste et les fusions. 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 étape à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans le tri.
  3. Suivez chaque fusion : les deux moitiés triées descendent dans le tampon, et la plus petite valeur de tête remonte, une à la fois.

Comment fonctionne le tri fusion

Une valeur seule est déjà triée. Pour toute liste plus longue, coupez-la en deux moitiés et triez chaque moitié par tri fusion. Puis fusionnez-les : regardez la valeur de tête de chaque moitié, placez la plus petite dans le résultat, et recommencez jusqu'à ce que les deux moitiés soient vides. Comme les deux moitiés sont triées, le résultat l'est aussi.

Toujours n log n

Couper en deux encore et encore donne environ log₂ n niveaux, et chaque niveau de fusions écrit chaque valeur une fois : le tri fait donc environ n log₂ n écritures, et au plus autant de comparaisons. Contrairement au tri à bulles, au tri par sélection et au tri par insertion, ce nombre ne croît pas comme n², et l'ordre de la liste compte beaucoup moins. Le prix à payer est un tampon aussi long que la liste. Le tri fusion est aussi stable, c'est pourquoi il sert de base aux tris de Python et de Java.

Questions fréquemment posées

Comment fonctionne le tri fusion ?

Il coupe la liste en deux, trie chaque moitié par tri fusion, puis fusionne les deux moitiés triées en prenant à chaque fois la plus petite de leurs valeurs de tête. Une liste d'une seule valeur est déjà triée : le découpage s'arrête là.

Combien de comparaisons fait le tri fusion ?

Pour n valeurs, au plus environ n log₂ n − n + 1, et au moins environ la moitié de n log₂ n. Pour 40 valeurs, c'est au plus 177. Les écritures dans la liste sont toujours les mêmes pour un n donné : une par valeur à chaque niveau de fusion.

Pourquoi le tri fusion a-t-il besoin de mémoire en plus ?

Fusionner deux moitiés sur place est difficile à faire vite, donc le tri fusion habituel copie les moitiés dans un tampon et les réécrit dans l'ordre. Le tampon est aussi long que la liste : c'est le principal défaut par rapport au tri rapide et au tri par tas.

Le tri fusion est-il stable ?

Oui. Quand les deux valeurs de tête sont égales, celle de la moitié gauche passe en premier : les valeurs égales 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