Quelle est la méthode la plus rapide pour ranger par ordre alphabétique votre bibliothèque ? - Chand John

Visionner la vidéo entière ici : http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

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. Comment pouvez-vous vite ranger les livres ? Chand John nous éclaire sur la manière dont les algorithmes aident les bibliothécaires et les moteurs de recherches à trier rapidement les informations.

Cours donné par Chand John, animation faite par Anton Trofimov.

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.