WEBVTT

00:00:06.491 --> 00:00:08.947
Vous travaillez
dans une bibliothèque universitaire.

00:00:08.947 --> 00:00:11.397
C'est le milieu d'une après-midi calme

00:00:11.397 --> 00:00:17.031
quand une livraison
de 1 280 livres arrive.

00:00:17.701 --> 00:00:21.470
Les livres ont été déposés
en une seule ligne,

00:00:21.470 --> 00:00:23.138
mais ils ne sont pas dans l'ordre

00:00:23.138 --> 00:00:26.301
et le système de classement automatique
est en panne.

00:00:26.741 --> 00:00:29.667
Pour aggraver la situation,
les cours commencent demain,

00:00:29.667 --> 00:00:32.005
ce qui veut dire qu'à la première heure,

00:00:32.005 --> 00:00:35.797
des étudiants vont venir en nombre
à la recherche de ces livres.

00:00:36.297 --> 00:00:38.883
Comment pouvez-vous les classer
en temps et en heure ?

00:00:38.883 --> 00:00:42.179
Une façon de procéder est de commencer
par la première paire de livres

00:00:42.179 --> 00:00:44.249
à l'une des extrémités de la ligne.

00:00:44.429 --> 00:00:46.749
Si ces deux premiers livres
sont dans l'ordre,

00:00:46.749 --> 00:00:48.426
laissez-les tels quels.

00:00:48.426 --> 00:00:50.290
Sinon, échangez leur place.

00:00:50.480 --> 00:00:53.249
Faites de même
avec le deuxième et troisième livre

00:00:53.249 --> 00:00:57.275
et ainsi de suite,
jusqu'à atteindre l'autre extrémité.

00:00:57.705 --> 00:00:59.975
À un certain moment,
vous aurez en main le livre

00:00:59.975 --> 00:01:01.235
à ranger en dernière place

00:01:01.235 --> 00:01:04.350
et vous l'échangez
avec chaque livre qui suit,

00:01:04.350 --> 00:01:08.420
le déplaçant ainsi le long de la ligne
jusqu'à arriver au bout.

00:01:09.020 --> 00:01:12.225
Revenez ensuite au début
et répétez l'action

00:01:12.225 --> 00:01:15.180
pour ranger le deuxième livre
et ceux qui suivent

00:01:15.180 --> 00:01:18.091
afin qu'ils soient tous
à leur place respective.

00:01:18.571 --> 00:01:21.242
Cette technique est appelée
le tri à bulle.

00:01:21.522 --> 00:01:23.596
C'est simple mais long.

00:01:23.866 --> 00:01:28.691
Vous exécutez 1 279 comparaisons
la première fois,

00:01:29.001 --> 00:01:33.323
puis 1 278, et ainsi de suite,

00:01:33.323 --> 00:01:37.852
pour un total de 818 560 comparaisons.

00:01:38.542 --> 00:01:43.773
Si chaque comparaison dure une seconde,
ranger prendra neuf jours.

00:01:43.973 --> 00:01:48.319
Une deuxième technique est de commencer
par classer les deux premiers livres,

00:01:48.319 --> 00:01:52.883
puis comparer le troisième livre
à celui en deuxième place.

00:01:53.443 --> 00:01:56.833
S'il doit être en deuxième place,
échangez-les

00:01:56.833 --> 00:01:59.361
puis comparez-le avec le livre
en première place,

00:01:59.361 --> 00:02:01.172
et échangez-les si besoin.

00:02:01.392 --> 00:02:03.880
Vous avez ainsi rangé
les trois premiers livres.

00:02:03.880 --> 00:02:07.732
Continuez d'ajouter un livre à la fois
à ce sous-classement trié,

00:02:07.732 --> 00:02:11.809
comparez et échangez le nouveau livre
avec le précédent

00:02:11.809 --> 00:02:15.614
jusqu'à ce qu'il soit correctement rangé
parmi les livres déjà classés.

00:02:15.614 --> 00:02:18.003
C'est la technique du tri par insertion.

00:02:18.003 --> 00:02:19.404
Contrairement au tri à bulle,

00:02:19.404 --> 00:02:23.134
cela ne nécessite généralement pas
une comparaison de chaque paire de livres.

00:02:23.134 --> 00:02:26.954
En moyenne,
on ne compare chaque livre

00:02:26.954 --> 00:02:29.094
qu'avec la moitié des livres le précédant.

00:02:29.094 --> 00:02:32.123
En procédant ainsi,
le nombre total de comparaisons

00:02:32.123 --> 00:02:37.303
est de 409 280,
soit presque cinq jours.

00:02:37.775 --> 00:02:40.314
C'est encore trop de comparaisons.

00:02:40.624 --> 00:02:42.355
Voici une meilleure méthode :

00:02:42.355 --> 00:02:46.475
d'abord choisissez un livre au hasard,
c'est votre séparateur,

00:02:46.475 --> 00:02:49.106
puis comparez-le
avec tout les autres livres.

00:02:49.106 --> 00:02:52.115
Ensuite, divisez la ligne
en plaçant tous les livres

00:02:52.115 --> 00:02:55.156

qui viennent avant le séparateur
à sa gauche

00:02:55.396 --> 00:02:58.275
et ceux qui viennent après
à sa droite.

00:02:58.485 --> 00:03:00.415
Vous venez d'économiser du temps

00:03:00.415 --> 00:03:03.715
en ne comparant aucun des livres
situés à gauche

00:03:03.715 --> 00:03:06.675
avec ceux situés à droite.

00:03:06.915 --> 00:03:09.665
Maintenant,
concentrez-vous sur les livres de gauche.

00:03:09.665 --> 00:03:12.542
Choisissez à nouveau
un livre séparateur

00:03:12.542 --> 00:03:16.946
et séparez les livres devant le précéder
de ceux qui doivent lui succéder.

00:03:16.946 --> 00:03:19.736
Vous pouvez continuer
à créer des sous-classements

00:03:19.736 --> 00:03:22.384
jusqu'à avoir plusieurs sous-lignes,
assez petites,

00:03:22.384 --> 00:03:25.644
que vous rangez rapidement
en utilisant une autre méthode,

00:03:25.644 --> 00:03:27.294
comme le tri par insertion.

00:03:27.504 --> 00:03:32.656
Chaque séquence de séparation
compte environ 1 280 comparaisons.

00:03:33.186 --> 00:03:35.466
Si vos séparations sont équilibrées,

00:03:35.466 --> 00:03:40.976
répartir les livres en 128 sous-lignes
de dix livres se fait en sept séquences,

00:03:41.256 --> 00:03:43.597
ou 8 960 secondes.

00:03:43.947 --> 00:03:48.096
Trier ces sous-lignes ajoute 22 secondes
à chaque séquence.

00:03:48.516 --> 00:03:51.427
Cette méthode s'appelle le tri rapide,

00:03:51.437 --> 00:03:54.403
et permet de classer les livres
en 3h30.

00:03:54.633 --> 00:03:55.717
Mais il y a un piège :

00:03:55.717 --> 00:03:57.777
vos séparations
peuvent finir déséquilibrées

00:03:57.777 --> 00:03:59.445
sans vous faire gagner de temps.

00:03:59.445 --> 00:04:01.477
Heureusement,
cela arrive très rarement.

00:04:01.477 --> 00:04:04.950
C'est pourquoi aujourd'hui le tri rapide
est l'une des meilleures méthodes

00:04:04.950 --> 00:04:06.856
utilisée par les programmeurs.

00:04:06.856 --> 00:04:10.847
Par exemple, ils emploient cette technique
pour trier les articles d'un site par prix

00:04:10.847 --> 00:04:13.508
ou pour créer une liste
de toutes les stations d'essence

00:04:13.508 --> 00:04:15.818
classées par distance.

00:04:16.228 --> 00:04:18.709
Dans votre situation,
vous avez fini votre tri rapide

00:04:18.709 --> 00:04:19.997
et vous ainsi êtes libre.

00:04:20.427 --> 00:04:22.627
Encore un autre jour crucial
à la bibliothèque.