Vous travaillez dans une bibliothèque universitaire.
C'est le milieu d'une après-midi calme
quand une livraison de 1 280 livres arrive.
Les livres ont été déposés en une seule ligne,
mais ils ne sont pas dans l'ordre
et le système de classement automatique est en panne.
Pour aggraver la situation, les cours commencent demain,
ce qui veut dire qu'à la première heure,
des étudiants vont venir en nombre à la recherche de ces livres.
Comment pouvez-vous les classer en temps et en heure ?
Une façon de procéder est de commencer par la première paire de livres
à l'une des extrémités de la ligne.
Si ces deux premiers livres sont dans l'ordre,
laissez-les tels quels.
Sinon, échangez leur place.
Faites de même avec le deuxième et troisième livre
et ainsi de suite, jusqu'à atteindre l'autre extrémité.
À un certain moment, vous aurez en main le livre
à ranger en dernière place
et vous l'échangez avec chaque livre qui suit,
le déplaçant ainsi le long de la ligne jusqu'à arriver au bout.
Revenez ensuite au début et répétez l'action
pour ranger le deuxième livre et ceux qui suivent
afin qu'ils soient tous à leur place respective.
Cette technique est appelée le tri à bulle.
C'est simple mais long.
Vous exécutez 1 279 comparaisons la première fois,
puis 1 278, et ainsi de suite,
pour un total de 818 560 comparaisons.
Si chaque comparaison dure une seconde, ranger prendra neuf jours.
Une deuxième technique est de commencer par classer les deux premiers livres,
puis comparer le troisième livre à celui en deuxième place.
S'il doit être en deuxième place, échangez-les
puis comparez-le avec le livre en première place,
et échangez-les si besoin.
Vous avez ainsi rangé les trois premiers livres.
Continuez d'ajouter un livre à la fois à ce sous-classement trié,
comparez et échangez le nouveau livre avec le précédent
jusqu'à ce qu'il soit correctement rangé parmi les livres déjà classés.
C'est la technique du tri par insertion.
Contrairement au tri à bulle,
cela ne nécessite généralement pas une comparaison de chaque paire de livres.
En moyenne, on ne compare chaque livre
qu'avec la moitié des livres le précédant.
En procédant ainsi, le nombre total de comparaisons
est de 409 280, soit presque cinq jours.
C'est encore trop de comparaisons.
Voici une meilleure méthode :
d'abord choisissez un livre au hasard, c'est votre séparateur,
puis comparez-le avec tout les autres livres.
Ensuite, divisez la ligne en plaçant tous les livres
qui viennent avant le séparateur à sa gauche
et ceux qui viennent après à sa droite.
Vous venez d'économiser du temps
en ne comparant aucun des livres situés à gauche
avec ceux situés à droite.
Maintenant, concentrez-vous sur les livres de gauche.
Choisissez à nouveau un livre séparateur
et séparez les livres devant le précéder de ceux qui doivent lui succéder.
Vous pouvez continuer à créer des sous-classements
jusqu'à avoir plusieurs sous-lignes, assez petites,
que vous rangez rapidement en utilisant une autre méthode,
comme le tri par insertion.
Chaque séquence de séparation compte environ 1 280 comparaisons.
Si vos séparations sont équilibrées,
répartir les livres en 128 sous-lignes de dix livres se fait en sept séquences,
ou 8 960 secondes.
Trier ces sous-lignes ajoute 22 secondes à chaque séquence.
Cette méthode s'appelle le tri rapide,
et permet de classer les livres en 3h30.
Mais il y a un piège :
vos séparations peuvent finir déséquilibrées
sans vous faire gagner de temps.
Heureusement, cela arrive très rarement.
C'est pourquoi aujourd'hui le tri rapide est l'une des meilleures méthodes
utilisée par les programmeurs.
Par exemple, ils emploient cette technique pour trier les articles d'un site par prix
ou pour créer une liste de toutes les stations d'essence
classées par distance.
Dans votre situation, vous avez fini votre tri rapide
et vous ainsi êtes libre.
Encore un autre jour crucial à la bibliothèque.