You work at the college library. You're in the middle of a quiet afternoon when suddenly a shipment of 1,280 different books arrives. The books have been dropped of in one long straight line, but they're all out of order, and the automatic sorting system is broken. To make matters worse, classes start tomorrow, which means that first thing in the morning, students will show up in droves looking for these books. How can you get them all sorted in time? One way would be to start at one end of the line with the first pair of books. If the first two books are in order, then leave them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you reach the end of the line. At some point, you'll come across the book that should be last, and keep swapping it with every subsequent book, moving it down the line until it reaches the end where it belongs. Then, start from the beginning and repeat the process to get the second to last book in its proper place, and keep going until all books are sorted. This approach is called Bubble Sort. It's simple but slow. You'd make 1,279 comparisons in the first round, then 1,278, and so on, adding up to 818,560 comparisons. If each took just one second, the process would take over nine days. 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. If it belongs before the second book, swap them, then compare it with the book in the first spot, and swap again if needed. Now you've sorted the first three books. Keep adding one book at a time to the sorted sub-line, comparing and swapping the new book with the one before it until it's correctly placed among the books sorted so far. This is called Insertion Sort. Unlike Bubble Sort, it usually doesn't require comparing every pair of books. On average, we'd expect to only need to compare each book to half of the books that came before it. In that case, the total number of comparisons would be 409,280, taking almost five days. You're still doing way too many comparisons. Here's a better idea. First, pick a random book. Call it the partition and compare it to every other book. Then, divide the line by placing all the books that come before the partition on its left and all the ones that come after it on its right. You've just saved loads of time by not having to compare any of the books on the left to any of the ones on the right ever again. Now, looking only at the books on the left, you can again pick a random partition book and separate those books that come before it from those that come after it. You can keep creating sub-partitions like this until you have a bunch of small sub-lines, each of which you'd sort quickly using another strategy, like Insertion Sort. Each round of partitioning requires about 1,280 comparisons. If your partitions are pretty balanced, dividing the books into 128 sub-lines of ten would take about seven rounds, or 8,960 seconds. Sorting these sub-lines would add about 22 seconds each. All in all, this method known as QuickSort could sort the books in under three and a half hours. But there's a catch. Your partitions could end up lopsided, saving no time at all. Luckily, this rarely happens. That's why QuickSort is one of the most efficient strategies used by programmers today. They use it for things like sorting items in an online store by price, or creating a list of all the gas stations close to a given location sorted by distance. In your case, you're done quick sorting with time to spare. Just another high-stakes day in the library.
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.