Le point de départ a été une activité faite avec alcoffeethmique sur l’approximation normale d’une loi binomiale. Le cours sur la loi normale ayant déjà été fait, les élèves étaient familiarisés avec la forme de la célèbre courbe en cloche. Il s’agissait donc de leur faire représenter graphiquement des lois binomiales de paramètre N croissant (avec p voisin de 0,5) jusqu’à ce que la forme de cloche leur paraisse évidente [1]. Pour cela, la version d’alcoffeethmique ci-dessous a été utilisée :

L’algorithme utilisé pour représenter graphiquement une loi binomiale avec alcoffeethmique est celui-ci :

N = 8
p = 0.4
loi = (binomiale N, p, k for k in [0..N])
diagrammeBatonsTrie loi, 1

Rédigé ainsi, il suffit de modifier la première ligne pour avoir d’autres valeurs de N (mais il faut ajuster le dernier paramètre à la quatrième ligne pour que le graphique soit bien dimensionné). On peut décrire l’algorithme ainsi :

1. On affecte la variable N à 8 (taille de l’échantillon).
2. On affecte la variable p à 0,4 (probabilité de succès).
3. On crée un tableau loi contenant les probabilités que le nombre de succès soit k pour toutes valeur de k allant de 0 à N.
4. On dessine le diagramme en bâtons de la loi binomiale, en triant les valeurs de k au passage (ceci est nécessaire au cas où ces valeurs n’auraient pas été introduites dans l’ordre croissant).

On obtient alors le diagramme en bâtons suivant :

Mais pas toujours : Le graphique ci-dessus a été obtenu avec le navigateur Mozilla Firefox. Mais le même alcoffeethmique avec le même script produit sous Google Chrome un graphique visiblement assez différent :

Comme alcoffeethmique est programmé en CoffeeScript, il est relativement aisé de chercher dans son code source comment sont dessinés les diagrammes en bâtons :

diagrammeBatonsTrie = (dico, ech=400) ->
    nombreBatons = (x for x of dico when x<Infinity).length
    dicotrie=(parseFloat x for x of dico when x<Infinity).sort (x,y)-> x>y
    effaceDessin()
    dessineSegment 20, 440, 620, 440, 'black'
    abscisse = 40-600/nombreBatons
    for x in dicotrie
        abscisse += 600/nombreBatons
        hauteur = 400/ech*dico[x]
        dessineRectangle abscisse, 440-hauteur, 5, hauteur, 'blue'
        dessineTexte x.toString().replace(".",","), abscisse, 460, 'black'

C’est donc la troisième ligne qui effectue le tri croissant selon les valeurs du caractère, qui est responsable du mélange des bâtons. Elle crée, à partir de la liste dico des valeurs du caractère, une sous-liste formée par les seuls éléments qui soient à la fois numériques et finis [2]

La variante suivante du script en haut de page, donne un tri correct par Chrome :

N = 16
tableau = [0..N]
tableau.sort()
alert tableau

Ainsi, par défaut, Chrome trie les nombres dans l’ordre croissant. Mais si on lui demande explicitement de le faire, il ne le fait plus... Et un autre problème surgit alors : cette fois-ci, c’est Firefox qui donne un résultat surprenant :

0,1,10,11,12,13,14,15,16,2,3,4,5,6,7,8,9

Au secours, ils sont tous fous !!! Non, en fait il y a une logique dans l’ordre choisi par Firefox : c’est l’ordre lexicographique. Et c’est parce que les informations dans une page html sont essentiellement textuelles, que les développeurs de chez Mozilla ont fait ce choix. Il est donc nécessaire, hors Google Chrome, de préciser que les nombres doivent être rangés dans l’ordre croissant et non dans l’ordre lexicographique, en fournissant à sort (trier) la relation d’ordre choisie :

N = 16
tableau = [0..N]
tableau.sort (x,y) -> x>y
alert tableau

Cet aspect de la fonction sort (tri de JavaScript est, du point de vue mathématique, une porte ouverte vers un univers vaste d’exercices de statistiques : les notions de médiane et de quartiles ne dépendant que du tri, ces notions peuvent très bien s’étendre à d’autres relations d’ordre que l’ordre naturel des nombres. Par exemple, avec l’ordre alphabétique, la notion de mot médian d’un dictionnaire a du sens et même un sens assez concret...

En fait, il semble que les différents navigateurs internet utilisent différents algorithmes de tri. Ainsi :

• Safari utiliserait un algorithme de tri par sélection, inefficace sur de grands tableaux puisque le temps de tri d’un tableau de taille n est proportionnel à n² ;
• Firefox aurait plutôt opté pour le tri fusion, proportionnel à n ln(n) ;
• Chrome fait plus compliqué : Selon la taille du tableau et la nature de ses éléments, il choisit entre
  • le tri rapide ;
  • introsort ;
  • le tri fusion ;
  • le tri par sélection ;
  • un algorithme de tri basé sur un arbre AVL...
• Quant à Internet Explorer, comme ce n’est pas un logiciel libre, on ne peut pas savoir comment il trie les éléments ; on peut cependant supposer que c’est le tri rapide, puisque son auteur Charles Antony Richard Hoare travaille chez Microsoft qui est propriétaire de Internet Explorer.

En fait, il n’est (heureusement) pas nécessaire de détecter la nature du navigateur et appliquer un algorithme différent selon le navigateur. Il suffit, au lieu d’une fonction booléenne comme relation d’ordre

(x,y) -> 
    x>y

d’appliquer une fonction numérique

(x,y) -> 
    x-y

Ce qui a pour effet de réconcilier les navigateurs, Firefox continuant à interpréter la relation d’ordre comme booléenne (un nombre positif étant assimilé à true) et Chrome acceptant enfin de ranger les nombres dans l’ordre croissant. La modification [4] sera faite dans la prochaine version d’alcoffeethmique...

Ainsi, on peut tester en haut de cette page la version universelle du tri d’entiers déjà triés :

N = 16
tableau = [0..N]
tableau.sort (x,y) -> x-y
alert tableau

Celle-ci donne l’ordre croissant quel que soit le navigateur, même dans le triangle des Bermudes...

Cependant, même si on sait comment faire pour que Chrome trie les nombres dans l’ordre correct, tout ceci n’explique pas comment il trie les entiers avec la version en haut de cette page. Et comme Chrome n’est pas un logiciel libre, on ne peut pas consulter son code source pour voir comment est effectué ce tri mystérieux venu d’ailleurs...