What's the fastest way to alphabetize your bookshelf? - Chand John

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

Traducteur: Marie Moriceau Relecteur: Olga Stratila

You work at the college library.

Vous travaillez dans une bibliothèque universitaire.

C'est le milieu d'une après-midi calme

You're in the middle of a quiet afternoon

when suddenly a shipment of 1,280 different books arrives.

quand une livraison de 1 280 livres arrive.

Les livres ont été déposés en une seule ligne,

The books have been dropped of in one long straight line,

but they're all out of order,

mais ils ne sont pas dans l'ordre

and the automatic sorting system is broken.

et le système de classement automatique est en panne.

Pour aggraver la situation, les cours commencent demain,

To make matters worse, classes start tomorrow,

which means that first thing in the morning,

ce qui veut dire qu'à la première heure,

students will show up in droves looking for these books.

des étudiants vont venir en nombre à la recherche de ces livres.

How can you get them all sorted in time?

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

One way would be to start at one end of the line with the first pair of books.

à l'une des extrémités de la ligne.

If the first two books are in order, then leave them as they are.

Si ces deux premiers livres sont dans l'ordre,

laissez-les tels quels.

Otherwise, swap them.

Sinon, échangez leur place.

Then, look at the second and third books,

Faites de même avec le deuxième et troisième livre

repeat the process,

et ainsi de suite, jusqu'à atteindre l'autre extrémité.

and continue until you reach the end of the line.

At some point, you'll come across the book that should be last,

À un certain moment, vous aurez en main le livre

à ranger en dernière place

and keep swapping it with every subsequent book,

et vous l'échangez avec chaque livre qui suit,

moving it down the line until it reaches the end where it belongs.

le déplaçant ainsi le long de la ligne jusqu'à arriver au bout.

Then, start from the beginning and repeat the process

Revenez ensuite au début et répétez l'action

to get the second to last book in its proper place,

pour ranger le deuxième livre et ceux qui suivent

and keep going until all books are sorted.

afin qu'ils soient tous à leur place respective.

This approach is called Bubble Sort.

Cette technique est appelée le tri à bulle.

It's simple but slow.

C'est simple mais long.

Vous exécutez 1 279 comparaisons la première fois,

You'd make 1,279 comparisons in the first round,

then 1,278, and so on,

puis 1 278, et ainsi de suite,

adding up to 818,560 comparisons.

pour un total de 818 560 comparaisons.

If each took just one second, the process would take over nine days.

Si chaque comparaison dure une seconde, ranger prendra neuf jours.

Une deuxième technique est de commencer par classer les deux premiers livres,

A second strategy would be to start by sorting just the first two books.

Then, take the third book and compare it with the book in the second spot.

puis comparer le troisième livre à celui en deuxième place.

If it belongs before the second book, swap them,

S'il doit être en deuxième place, échangez-les

puis comparez-le avec le livre en première place,

then compare it with the book in the first spot,

and swap again if needed.

et échangez-les si besoin.

Now you've sorted the first three books.

Vous avez ainsi rangé les trois premiers livres.

Keep adding one book at a time to the sorted sub-line,

Continuez d'ajouter un livre à la fois à ce sous-classement trié,

comparing and swapping the new book with the one before it

comparez et échangez le nouveau livre avec le précédent

until it's correctly placed among the books sorted so far.

jusqu'à ce qu'il soit correctement rangé parmi les livres déjà classés.

C'est la technique du tri par insertion.

This is called Insertion Sort.

Unlike Bubble Sort, it usually doesn't require comparing every pair of books.

Contrairement au tri à bulle,

cela ne nécessite généralement pas une comparaison de chaque paire de livres.

On average, we'd expect to only need to compare each book

En moyenne, on ne compare chaque livre

to half of the books that came before it.

qu'avec la moitié des livres le précédant.

In that case, the total number of comparisons

En procédant ainsi, le nombre total de comparaisons

would be 409,280,

est de 409 280, soit presque cinq jours.

taking almost five days.

C'est encore trop de comparaisons.

You're still doing way too many comparisons.

Here's a better idea.

Voici une meilleure méthode :

First, pick a random book.

d'abord choisissez un livre au hasard, c'est votre séparateur,

Call it the partition and compare it to every other book.

puis comparez-le avec tout les autres livres.

Then, divide the line

Ensuite, divisez la ligne en plaçant tous les livres

by placing all the books that come before the partition on its left

and all the ones that come after it on its right.

et ceux qui viennent après à sa droite.

You've just saved loads of time

Vous venez d'économiser du temps

by not having to compare any of the books on the left

en ne comparant aucun des livres situés à gauche

to any of the ones on the right ever again.

avec ceux situés à droite.

Maintenant, concentrez-vous sur les livres de gauche.

Now, looking only at the books on the left,

you can again pick a random partition book

Choisissez à nouveau un livre séparateur

and separate those books that come before it from those that come after it.

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

You can keep creating sub-partitions like this

until you have a bunch of small sub-lines,

jusqu'à avoir plusieurs sous-lignes, assez petites,

each of which you'd sort quickly using another strategy, like Insertion Sort.

que vous rangez rapidement en utilisant une autre méthode,

comme le tri par insertion.

Each round of partitioning requires about 1,280 comparisons.

Chaque séquence de séparation compte environ 1 280 comparaisons.

If your partitions are pretty balanced,

Si vos séparations sont équilibrées,

dividing the books into 128 sub-lines of ten would take about seven rounds,

répartir les livres en 128 sous-lignes de dix livres se fait en sept séquences,

or 8,960 seconds.

ou 8 960 secondes.

Sorting these sub-lines would add about 22 seconds each.

Trier ces sous-lignes ajoute 22 secondes à chaque séquence.

All in all, this method known as QuickSort

Cette méthode s'appelle le tri rapide,

could sort the books in under three and a half hours.

et permet de classer les livres en 3h30.

But there's a catch.

Mais il y a un piège :

Your partitions could end up lopsided, saving no time at all.

vos séparations peuvent finir déséquilibrées

sans vous faire gagner de temps.

Luckily, this rarely happens.

Heureusement, cela arrive très rarement.

That's why QuickSort is one of the most efficient strategies

C'est pourquoi aujourd'hui le tri rapide est l'une des meilleures méthodes

used by programmers today.

utilisée par les programmeurs.

They use it for things like sorting items in an online store by price,

Par exemple, ils emploient cette technique pour trier les articles d'un site par prix

or creating a list of all the gas stations close to a given location

ou pour créer une liste de toutes les stations d'essence

classées par distance.

sorted by distance.

In your case, you're done quick sorting with time to spare.

Dans votre situation, vous avez fini votre tri rapide

et vous ainsi êtes libre.

Just another high-stakes day in the library.

Encore un autre jour crucial à la bibliothèque.