Calculatrice de tri croissant

7 ; −3 ; 12,5 ; 0 ; −10 ; 4 ⇒ −10, −3, 0, 4, 7, 12,5 ; minimum = −10, maximum = 12,5

n

Le nombre de valeurs de la liste — entre 1 et 200. Un est accepté et donne une liste d’un élément, ce qui est réellement correct plutôt qu’un cas dégénéré : un seul nombre est déjà en ordre croissant, et il est à la fois le plus petit et le plus grand de l’ensemble

a ≤ b

La comparaison sur laquelle repose le tri, et toute sa correction. C’est une comparaison numérique, donc −10 ≤ −3 et 9 ≤ 10 sont toutes deux vraies. Un tri de textes placerait au contraire −10 avant −3 par accident et 10 avant 9 par le même accident, parce qu’il compare caractère par caractère en partant de la gauche au lieu de comparer les valeurs

−10, −3, 0, 4, 7, 12,5

La sortie triée, et une permutation de l’entrée — six valeurs entrent, six valeurs sortent, les mêmes six. C’est l’invariant à vérifier si vous doutez du résultat : le compte doit correspondre, et chaque valeur saisie doit apparaître exactement autant de fois que vous l’avez saisie. Rien sur cette page n’ajoute, ne retire ni ne combine de nombres

minimum = −10

Le premier élément de la liste triée, lu dans cette liste plutôt que trouvé par un balayage séparé. Sur une droite numérique, c’est le point le plus à gauche. Ce n’est pas la même chose que l’entrée qui en a le plus l’air la plus petite : −10 paraît plus court que −3, et c’est pourtant le plus petit des deux

maximum = 12,5

Le dernier élément de la liste triée, là encore lu plutôt que recherché. L’écart entre celui-ci et le minimum est l’étendue, la seule statistique qui n’a besoin de rien d’autre que de ces deux sorties — et la page de l’étendue calcule exactement cela à partir de la même paire

3, 5, 5

Ce que font les doublons. L’entrée 5 ; 5 ; 3 se trie en 3, 5, 5 — la répétition survit. La supprimer serait plus propre à regarder et briserait l’invariant ci-dessus ; cela changerait aussi silencieusement la réponse à toute question sur le nombre de valeurs, y compris la médiane

Lire une médiane est la raison la plus courante de trier : la médiane est la valeur du milieu de la liste triée, ou la moyenne des deux du milieu quand le compte est pair, et ni l’une ni l’autre ne se lit sur une liste en désordre. Il en va de même des quartiles et des centiles, qui se définissent par une position dans l’ordre croissant. Un deuxième usage est l’étendue, qui n’est que la plus grande valeur moins la plus petite : cette page imprime ces deux nombres directement, et la page de l’étendue fait la soustraction si c’est tout ce que vous voulez. Un troisième est l’usage humain ordinaire : une colonne de mesures, de prix, d’âges ou de notes collée depuis un tableur se lit beaucoup mieux une fois rangée, parce que les extrêmes sautent aux yeux et que les regroupements deviennent visibles. C’est la même raison qui fait d’une liste triée la première chose qu’on trace, puisqu’un décompte de fréquences comme un histogramme partent tous les deux d’elle. Un quatrième usage est de vérifier le tri d’un tableur. Trier comme du texte plutôt que comme des nombres est une erreur fréquente dans les logiciels de tableur quand une colonne a été formatée bizarrement, et le symptôme est exactement celui décrit plus haut — 10 avant 9, ou 12,5 avant 4. Si une colonne triée vous paraît fausse, faire passer les mêmes valeurs par cette page vous dit lequel des deux lit mal l’entrée. Une fois la liste en ordre, ce sont les voisines descriptives qui prennent le relais : la page de la médiane lit le milieu, celle de l’étendue les deux extrémités, celle des quartiles les positions au quart, et celle de la moyenne la moyenne, qui est la seule de ces mesures à ne pas se soucier de l’ordre. Et si vous voulez trier en sens inverse, l’ordre décroissant s’obtient en lisant la sortie de droite à gauche.

1. Signes mêlés et une décimale : 7 ; −3 ; 12,5 ; 0 ; −10 ; 4

   1. On cherche d’abord la plus petite valeur : −10 est plus à gauche que tout le reste de la liste
   2. Puis la suivante, −3, puis 0, puis 4, puis 7
   3. 12,5 est la plus grande, elle passe donc en dernier
   4. La liste triée est −10, −3, 0, 4, 7, 12,5, et ses deux extrémités donnent le minimum et le maximum

   La saisie par défaut, et volontairement peu commode : elle contient deux négatifs, une décimale positive et un zéro, donc elle met les deux pièges à l’épreuve en même temps. Remarquez que −10 se classe en premier alors que −3 est le plus long des deux à l’écrit, et que 12,5 se classe après 7 alors qu’il commence par le même chiffre que 1. Trier ces valeurs comme du texte donnerait −10, −3, 0, 12,5, 4, 7 : le côté négatif aurait l’air juste par accident et la décimale atterrirait au mauvais endroit.

2. Le piège que les nombres à un chiffre cachent : 9 ; 10 ; 100 ; 2

   1. On compare les valeurs et non le premier chiffre : 2 est plus petit que 9
   2. 10 est plus grand que 9 mais plus petit que 100
   3. L’ordre est 2, 9, 10, 100
   4. Le plus petit est 2 et le plus grand est 100

   Quatre nombres courts, tous positifs, et la liste qui attrape le tri de textes. Comparer comme des chaînes place 10 en premier et 2 en dernier, parce que la comparaison s’arrête au premier caractère : 1 vient avant 2, qui vient avant 9. L’ordre correct vient de la comparaison des valeurs, et le signe que quelque chose a mal tourné est que le résultat ne ressemble pas à une droite numérique — il n’existe aucun rangement des chiffres dans lequel 10 se trouve avant 2. C’est le cas sur lequel il faut tester tout code de tri, parce qu’une liste de nombres à un chiffre se trie correctement dans les deux méthodes.

3. Les négatifs dans l’autre sens : −5 ; −20 ; −3

   1. Sur une droite numérique, −20 est le plus à gauche des trois
   2. −5 est à sa droite, et −3 est le plus à droite des trois
   3. L’ordre croissant est donc −20, −5, −3
   4. Le minimum est −20 — le nombre qui a l’air le plus grand de la liste

   Le miroir de l’exemple précédent, et celui qui attrape les lecteurs plutôt que le code. −20 est le plus petit des trois alors que ses chiffres sont les plus grands, parce que plus à gauche sur la droite veut dire plus petit. Le tri de textes tombe ici juste par hasard — la chaîne −20 vient bien avant −5 —, donc le cas négatif est celui où un tri de textes a l’air correct, tandis que le cas des positifs à plusieurs chiffres est celui où il échoue. À eux deux, les exemples couvrent les deux directions, et c’est pourquoi ils sont tous les deux ici.

La liste accepte entre 1 et 200 nombres, séparés par des virgules, des points-virgules ou des espaces, et les trois peuvent se mélanger dans une même liste. Deux cents est une limite sur la longueur de liste que la page accepte, et non une protection de performance : les listes plus longues ne sont pas lentes, elles sont refusées, parce qu’un champ de cette longueur cesse d’être modifiable et que la réponse cesse d’être lisible. Les nombres peuvent être négatifs, comporter des décimales ou valoir zéro, et les doublons sont conservés plutôt que supprimés. Les séparateurs de milliers ne sont pas compris : une virgule suivie d’un espace sépare deux entrées, tandis qu’une virgule placée entre deux chiffres sans espace après est lue comme un séparateur décimal (1,5 vaut un et demi). La forme 1,500 n’est ni l’un ni l’autre, donc 1 500 et 1,5 ne peuvent pas être distingués et la liste est refusée d’emblée plutôt que devinée — une colonne collée depuis un tableur qui groupe les grands nombres est rejetée, pas silencieusement mal lue. Retirez les séparateurs avant de coller. La notation exponentielle n’est pas comprise non plus, donc 1e5 est refusé plutôt que lu comme 100 000. La sortie est une écriture canonique de chaque valeur plutôt qu’une copie de ce que vous avez tapé : 12,50 s’imprime 12,5, +7 s’imprime 7, et −0 s’imprime 0. Les très grandes valeurs passent en notation exponentielle dans la sortie, à partir de 10²¹, qui est le point où la conversion d’un nombre en texte change de notation toute seule ; l’aplatir voudrait dire écrire un second formateur de nombres, et la page n’en a pas. Il n’y a aucune table de référence sur cette page : une table sert à montrer dans quelle tranche tombe un résultat, et un tri n’a pas de tranches. L’ordre croissant est le seul proposé — pour l’ordre décroissant, lisez la sortie de droite à gauche.

Comment trier une liste qui contient à la fois des négatifs et des décimales ?

Collez-la et laissez la page le faire — le séparateur peut être une virgule, un point-virgule ou un espace, et les trois peuvent se mélanger. Les négatifs et les décimales ne changent rien à la règle, qui est simplement qu’un nombre plus petit va plus à gauche. Le seul point à surveiller est que −20 est plus petit que −3 malgré ses chiffres plus nombreux, et que 12,5 est plus grand que 4 malgré son 1 initial. Comparer les valeurs plutôt que le texte des nombres, c’est toute la correction ici.

L’ordre dans lequel je tape les nombres a-t-il une importance ?

Aucune — la page trie ce qu’on lui donne, et le même ensemble de valeurs produit toujours la même sortie quel que soit l’ordre d’arrivée. C’est ce qui rend le résultat vérifiable : triez une liste, triez-la encore, la sortie est identique, parce qu’il n’existe qu’un seul ordre croissant pour un ensemble de valeurs donné. Les doublons sont le seul endroit où la forme de l’entrée survit, puisque 5 ; 5 ; 3 et 3 ; 5 ; 5 se trient tous deux en 3, 5, 5.

Les valeurs en double sont-elles supprimées ?

Non, et c’est délibéré. La sortie est l’entrée réarrangée, elle doit donc contenir exactement les nombres que vous avez donnés, chacun autant de fois que vous l’avez donné. Supprimer les répétitions serait une autre opération — cela s’appelle dédoublonner —, et cela change la réponse à toute question portant sur la liste, y compris le nombre de valeurs et la médiane. Si vous voulez une liste de valeurs distinctes, c’est une étape séparée, et elle doit être visible.

Pourquoi 12,50 est-il revenu en 12,5 ?

Parce que les zéros de fin ne font pas partie d’une valeur, et que la page imprime l’écriture canonique de chaque nombre plutôt que de recopier ce que vous avez tapé. La même normalisation transforme +7 en 7 et −0 en 0. C’est le seul endroit où la sortie n’est pas tout à fait une copie de l’entrée, et cela vaut la peine d’être su si la mise en forme de vos nombres porte un sens pour vous — pour un montant, par exemple, où 12,50 et 12,5 ne se lisent pas de la même façon même s’il s’agit du même nombre.

Puis-je trier du plus grand au plus petit ?

La page donne l’ordre croissant, et l’ordre décroissant n’est que cette même sortie lue de droite à gauche — il n’y a rien de plus à calculer, puisque inverser une liste triée donne immédiatement l’ordre inverse. La page ne propose qu’une direction parce que c’est celle dont toutes les statistiques en aval ont besoin : la médiane, les quartiles et l’étendue se définissent tous à partir de la liste croissante, et une liste décroissante devrait être inversée avant qu’on puisse en lire une seule.

Pourquoi ma colonne collée depuis un tableur a-t-elle été refusée ?

Presque certainement à cause des séparateurs de milliers. Sur cette page, une virgule suivie d’un espace sépare deux entrées, et une virgule entre deux chiffres sans espace après est lue comme un séparateur décimal ; la forme 1,500 n’est ni l’une ni l’autre, donc 1 500 et 1,5 ne peuvent pas être distingués et toute la liste est refusée plutôt que devinée. La notation exponentielle est refusée de la même façon : 1e5, et non 100 000. Retirez les séparateurs avant de coller.

• Sorting — the general problem of putting a collection in order, and why comparison-based sorting is its own field of study — Wolfram MathWorld (United States)
• Ordering — what a total order is, and the properties a comparison has to have before a list can be sorted by it at all — Wolfram MathWorld (United States)
• Real Line — the picture that makes 'least to greatest' mean left to right, including for negative numbers — Wolfram MathWorld (United States)
• Relation d’ordre — la définition d’un ordre total, les propriétés qu’une comparaison doit vérifier pour qu’une liste soit triable, et la comparaison des nombres sur la droite numérique — Wikipédia en français