Qu’est-ce que l’ordre; qu’est-ce que le désordre ? Au-delà des questions philosophiques, on se demande comment trier une collection et comment la mélanger.
Des problèmes similaires…
À première vue, il semble que la génération d’ordre et de désordre dans un ensemble soient des problèmes similaires. En effet, créer de l’ordre revient à trier les éléments de l’ensemble pour en faire une liste ordonnée. Pour y générer du désordre, on mélange l’ordre des objets dans la liste; puis on peut revenir à une liste ordonnée en la triant. Puisque mélanger une liste ordonnée puis la trier revient à ne rien faire, on peut se demander en quoi ces problèmes sont vraiment différents. Après tout, dans les deux cas, on ne fait que changer l’ordre d’une collection d’objets.
La solution à ces deux problèmes est également similaire : dans les deux cas, on utilise des algorithmes, soit des procédures répétitives qu’on applique à notre ensemble pour changer l’ordre de ses éléments.
D’un point de vue mathématique, ces deux opérations sont radicalement différentes !
Malgré leur apparente similarité, les algorithmes de mélange et de tri se distinguent nettement.
D’abord l’algorithme de tri est déterministe, c’est-à-dire qu’il n’y a qu’un résultat possible. En revanche, l’algorithme de mélange cherche à rendre possible n’importe quelle configuration de la liste, ce qui est l’opposé d’un algorithme déterministe.
De plus, on peut vérifier qu’une liste est bien triée en la lisant. Il est cependant impossible de vérifier si une liste est bien mélangée en la regardant, puisque chaque configuration doit être possible. Un truc souvent utilisé par les magiciennes est d’ailleurs de placer un paquet de cartes dans un ordre qu’elles connaissent, mais qui n’est pas naturel, puis de vous faire « vérifier » que le paquet est bien mélangé. Vous confirmerez que c’est le cas si vous ne reconnaissez pas l’ordre du paquet !
Pourquoi cherche-t-on à créer de l’ordre ?
Créer de l’ordre permet d’accélérer énormément la recherche dans la collection. Dans une collection désordonnée, la seule façon de chercher est de parcourir toute la collection jusqu’à ce qu’on trouve l’objet recherché. Dans une collection ordonnée (une bibliothèque publique, un dictionnaire, etc.), on peut faire une fouille binaire (voir encadré), ce qui nous permet d’économiser énormément de temps !
Trier la bibliothèque, est-ce que ça en vaut la peine ?
Voilà que vous emménagez dans un manoir avec une immense bibliothèque; plus d’un million de livres !1 Vous découvrez avec désarroi que l’ancien propriétaire était une personne désorganisée qui n’a jamais trié ces livres. Bien qu’il y ait un fichier avec tous les titres des livres (donc vous savez précisément si un livre se trouve dans la bibliothèque), vous n’avez aucun moyen de savoir où se trouve un livre sans vous mettre à lire les titres de tous les livres de la bibliothèque.
Ce n’est pas si grave, puisque vous avez beaucoup de temps à votre disposition; au moins assez de temps pour lire un livre par jour! Chaque matin, vous choisissez un livre que vous aimeriez lire, puis vous le cherchez dans la collection. Une fois que vous avez trouvé votre livre du jour, vous le lisez, puis choisissez votre livre du lendemain. Mais vous avez toujours cette arrière-pensée : serait-ce plus rapide de prendre quelques jours sans lire, trier tous les livres, puis repérer rapidement les livres par la suite ? Pour vous aider à prendre une décision, vous formulez cette question
Si je vais chercher un livre par jour pendant un certain nombre de jours, aurais-je avantage à trier la bibliothèque d’abord ?
Vous découvrez ainsi la complexité algorithmique : c’est la mesure du nombre d’étapes nécessaires pour compléter une opération donnée (trier la bibliothèque, chercher un mot dans le dictionnaire, etc.) par un algorithme. Pour répondre à votre question, vous calculez le nombre d’étapes pour trier une collection selon un tri efficace et le nombre d’étapes pour aller chercher un livre selon la fouille linéaire ou la fouille binaire.
Pour que la comparaison soit raisonnable, vous chercherez à effectuer chaque opération de manière optimale. Heureusement, dans votre bibliothèque se trouve un livre sur les algorithmes de tri. Vous vous en emparez, et découvrez trois façons de trier votre bibliothèque.
Recherche dans le dictionnaire
Supposons que vous cherchiez un mot dans un dictionnaire illustré d’une langue inconnue. En particulier, vous connaissez l’ordre alphabétique de cette langue, mais n’avez aucune idée combien de mots de cette langue commencent par chaque lettre. Pour trouver un mot donné, deux stratégies sont possibles :
- La fouille linéaire consiste à lire chaque mot du dictionnaire, en espérant que notre mot approche. En moyenne, nous devrons lire la moitié des mots du dictionnaire pour trouver le mot désiré !
- La fouille binaire tire profit de l’ordre des mots dans le dictionnaire. Ainsi, nous ouvrirons le dictionnaire à la page centrale, puis comparerons notre mot au premier mot de la page centrale.
Si notre mot précède ce dernier, nous répétons cette procédure avec la première moitié des mots du dictionnaire. À chaque étape, nous réduisons de moitié la taille de la section dans laquelle nous recherchons un mot. Ainsi, si nous avons \(2^m=n\) mots dans le dictionnaire, on aura besoin de faire \(m\) comparaisons. Il suffit donc de \(\log_2(n)\) comparaisons pour trouver le mot désiré dans un dictionnaire de \(n\) mots. C’est très rapide !
Une première méthode
Le tri par insertion est celui qu’on ferait naturellement pour trier une petite bibliothèque.
- Les premiers livres sur l’étagère sont triés. Les autres ne le sont pas encore.
- On prend le premier livre qui n’est pas à sa place, et on l’insère à sa place dans la partie triée.
- On répète jusqu’à ce qu’on ait placé tous les livres sur l’étagère.
Ce tri est rapide si l’insertion se fait rapidement. Par exemple, sur une étagère, on peut pousser tous les livres sur une petite distance vers la droite, et cela se fait rapidement. Par contre, s’il y a des séparateurs sur l’étagère pour délimiter les sections, on doit retirer les livres un à la fois et les placer de l’autre côté du séparateur. L’insertion devient alors une opération coûteuse, puisque chaque insertion nous force à déplacer tous les livres subséquents de l’autre côté des séparateurs, un à un; le tri par insertion devient alors un tri lent.
Le tri postal à la rescousse
Le tri postal tire son nom du fait de son utilisation dans les bureaux de poste. Supposons que vous vous trouviez au bureau de poste de Trois-Rivières. Certaines lettres doivent être envoyées à Montréal, d’autres à Sept-Îles ou à Val-d’Or. Un certain tri doit être fait pour mettre les lettres à destination d’une même ville dans le même camion, mais il n’y a nul besoin de trier avec précision, à Trois-Rivières, les lettres à destination de Sept-Îles.
La première étape consiste donc à trier, dans différents bacs, les lettres devant être envoyées à un même endroit.
Une seconde étape se fait au bureau de poste le plus près de la destination. À ce moment, un véritable tri se fait pour que la factrice distribue les lettres rapidement lors de sa tournée des maisons.
Un exemple de tri postal qu’on effectue dans la vie de tous les jours est lors du tri d’un paquet de cartes : on trie d’abord les cartes par couleur (carreau, cœur, pique et trèfle), puis on trie les cartes de chacune des couleurs par ordre croissant.
Une façon efficace de trier la bibliothèque serait de d’abord effectuer un tri postal pour envoyer chaque livre dans la bonne section (ou devant son étagère finale), puis d’effectuer un tri rapide.
Un tri rapide : le tri fusion
Le tri fusion est un exemple de tri rapide, moins intuitif que le tri par insertion. Il consiste à créer plusieurs petites piles de deux cartes, puis à les fusionner deux-à-deux : on prend alors deux piles (déjà triées), et on forme une nouvelle pile en plaçant au bas la plus petite valeur. Puisque cette valeur est forcément au bas d’une des deux piles, il n’y a qu’une comparaison à faire pour chaque valeur ajoutée à la nouvelle pile. On écoule ainsi les deux piles en ne créant qu’une pile, aussi triée.
À chaque étape de fusion, on doit changer chacun des livres de pile. Puisque le nombre de piles est réduit de moitié à chaque étape, pour \(2^m\) livres, on aura besoin de \(m\) étapes. Ainsi, pour n objets à trier, on a besoin de \(\log_2(n)\) étapes. Le nombre de déplacements de livres, en tout, est \(n \times \log_2(n)\). C’est un tri parmi les plus rapides.
Alors, on trie ou pas ?
Retournons à la question posée ci-dessus. Est-ce plus efficace de trier la bibliothèque une fois pour toutes, puis d’aller chercher un livre par jour, ou de naïvement chercher à chaque jour ?
Maintenant que vous connaissez quelques algorithmes de tri, vous pouvez calculer le nombre d’étapes nécessaires pour trier votre bibliothèque. Puisque vous souhaitez dédier un maximum de temps à la lecture des livres de votre bibliothèque (et donc un minimum de temps à trier et chercher des livres), vous choisissez la fouille binaire lorsque c’est possible, et vous effectuez le tri fusion. Vous obtenez alors un nombre d’étapes qui dépend du nombre de livres au total dans votre bibliothèque. Le nombre d’étapes pour la recherche dépend du nombre de jours (noté \(j\)) durant lesquels vous allez à la recherche d’un livre.
On constate que pour rentabiliser l’effort de tri, il faut que le nombre \(j\) de jours soit supérieur ou égal à
\[\frac{2n\log_2(n)}{n-2\log_2(n)},\]
(voir le tableau ci-dessous.)
Pour 10 livres, cela représente dix-neuf jours. En revanche, lorsqu’on a un million de livres \((n=1\,000\, 000),\) il est plus rapide de trier d’abord la bibliothèque, puis de chercher les livres si vous devez aller chercher (successivement) aussi peu que quarante livres. Pensez à tous ces livres en plus que vous pourrez lire si vous dédiez quelques heures au tri de votre bibliothèque dès aujourd’hui !
Pourquoi cherche-t-on à créer du désordre ?
Il arrive qu’on cherche à brouiller les pistes. Les jeux de hasard sont un exemple de situations où l’on cherche à créer du désordre. Dans la plupart des jeux de cartes, on cherche à mélanger du mieux que l’on peut le paquet de cartes avant chaque manche afin de rendre le jeu équitable.
Dans tout algorithme, on cherche à connaître le moment où l’algorithme se termine. Dans le cas de l’algorithme de tri, on sait précisément lorsque notre collection est triée; on n’a qu’à la lire pour vérifier qu’on y est parvenu. Par contre, c’est beaucoup plus compliqué pour le mélange.
Si la personne qui mélange le jeu va participer au jeu de hasard qui va suivre, elle ne peut regarder le paquet à la fin du mélange pour s’assurer que le mélange a bel et bien été effectué; elle aurait alors toute l’information sur l’ordre du paquet, annulant tous les bienfaits du mélange! Même en regardant, c’est incroyablement difficile de savoir si un paquet est bien mélangé. Ce qu’on peut faire, cependant, c’est chercher des indices du jeu tel qu’il était avant le mélange. Si on vient de jouer, il est fort probable que le jeu contienne des événements peu probables, comme de nombreuses paires de cartes de même valeur, ou des grands groupes de cartes de la même couleur. Si ces événements peu probables sont encore très présents dans le paquet de cartes après le mélange, c’est qu’on doit continuer de mélanger encore un certain temps.
Pour déterminer avec exactitude le nombre d’étapes nécessaire au mélange du paquet de cartes, il est nécessaire de modéliser le mélange, c’est-à-dire de créer une représentation la plus fidèle possible de notre mélange en termes mathématiques. Une fois le modèle établi, on calcule la probabilité d’obtenir chaque configuration du paquet de cartes après un certain nombre d’itérations du mélange. Si celles-ci sont à peu près égales (une définition rigoureuse de ceci existe), on aura donc bien mélangé. Des modèles mathématiques ont permis de déterminer, par exemple, que pour un paquet de 52 cartes manipulé par un joueur habile et honnête, il suffit d’effectuer le mélange par battage 7 fois, mais qu’il faut effectuer le mélange par-dessus la main environ 13 000 fois ! C’est particulièrement inefficace…
Algorithmes de mélange
Le mélange par battage
C’est le mélange de cartes le plus utilisé par les joueurs expérimentés. Pour l’effectuer, on sépare d’abord le paquet en deux plus petits paquets de tailles presque égales (on le fait à l’œil – mathématiquement, on dirait qu’on le sépare en deux parties selon une loi binomiale)2. Ensuite, on mélange les cartes en construisant un nouveau paquet qui respecte l’ordre de chacun des petits paquets : cette construction se fait carte par carte, en choisissant de façon aléatoire, à chaque étape, de quel petit paquet on extrait la carte suivante. Ce choix du petit paquet est indépendant de la valeur de la carte. Le processus est alors similaire à l’étape de fusion du tri fusion. C’est un mélange de cartes rapide (le plus rapide connu). Un motif qui est toujours dans le paquet, cependant, est les suites croissantes : ce sont des cartes qui étaient adjacentes avant le mélange et qui se trouvent dans le même ordre dans les paquets initial et final. Une fois le paquet mélangé, ces suites de cartes peuvent être entrecoupées d’autres cartes. Dans l’exemple ci-contre, 1, 2, 3, 4, 5 apparaît en ordre croissant une fois le mélange effectué, tout comme 6, 7, 8, 9, 10, 11. En effectuant le mélange par battage une seule fois, on crée seulement deux suites croissantes, une pour chaque petit paquet. À chaque itération, ce nombre peut doubler (tout au plus). Si l’on souhaite diviser un paquet de 52 cartes bien mélangées en suites croissantes, on doit en moyenne créer 26 suites croissantes.
Le mélange par-dessus la main
Il s’agit d’un mélange lent, souvent pratiqué par les joueurs débutants. On l’effectue en prenant tout le paquet dans une main, puis en laissant tomber dans l’autre main des petits paquets, successivement. Le résultat contient souvent des groupes de cartes qui étaient déjà adjacentes avant le mélange.
Conclusion
Si mettre de l’ordre dans une bibliothèque peut sembler une opération toute simple, y parvenir rapidement est beaucoup plus compliqué. Heureusement, on peut utiliser la complexité algorithmique pour faire des choix optimaux. En revanche, créer un niveau satisfaisant de désordre est loin d’être facile !
Pour en s\(\alpha\)voir plus !
Persi Diaconis et Ron L. Graham. Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks, Princeton University Press, 2011, 264 pages.
- À titre comparatif, c’est le nombre de livres qu’on trouve à la Grande Bibliothèque. ↩
- Pour un paquet de 52 cartes, ceci veut dire que la probabilité que le premier paquet contient m cartes est la même que la probabilité d’obtenir \(m\) fois un résultat « pile » en lançant 52 fois une pièce de monnaie. ↩
