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.
Je werkt in de mediatheek. De middag verloopt rustig totdat er plotseling 1.280 verschillende soorten boeken worden gebracht. De boeken worden in een lange kaarsrechte rij afgeleverd, maar ze staan niet op alfabet en de automatische sorteermachine is buiten gebruik. Tot overmaat van ramp start morgen het nieuwe schoojaar en dat betekent dat morgenvroeg drommen studenten op zoek gaan naar deze boeken. Hoe ga je ze zo snel mogelijk ordenen? Begin aan de linkerkant met het eerste aantal boeken. Als de eerste twee boeken op alfabetische volgorde staan, laat ze dan zo. Zoniet, ruil ze dan om. Kijk vervolgens naar het tweede en derde boek, doe nu precies hetzelfde en herhaal dit tot het einde van de rij. Ergens kom je het boek tegen die op de laatste plek hoort te staan, ruil deze steeds om met elk daaropvolgende boek, richting het eind van de rij totdat het op de juiste plek staat. Begin vanaf het begin en herhaal het proces om het een-na-laatste boek op de juiste plek te krijgen en ga zo door totdat alle boeken geordend zijn. Dit heet de bubble-sort-methode. Het is een simpel maar traag proces. Je vergelijkt 1.279 boeken in de eerste ronde, daarna 1.278 en zo verder, wat resulteert in 818.560 vergelijkingen. Als elke vergelijking één seconde in beslag neemt, duurt het proces ruim negen dagen. Een tweede strategie is om alleen de eerste twee boeken te ordenen. Pak dan het derde boek en vergelijk deze met het tweede boek. Als het voor het tweede boek hoort te staan, ruil ze dan om, vergelijk het daarna met het eerste boek en ruil deze ook om, mocht het nodig zijn. Nu heb je de eerste drie boeken geordend. Voeg steeds een boek tegelijk toe aan de geordende sublijn, door het nieuwe met het vorige boek te vergelijken en om te ruilen totdat het op de juiste plek staat tussen de boeken die tot nu toe geordend zijn. Dit heet invoegsortering. Anders dan bij de bubble-sort-methode, wordt niet elk boek met elkaar vergeleken. Gemiddeld genomen hoeven we alleen elk boek te vergelijken met de helft van de voorgaande boeken. In dit geval komt dit totaal neer op 409.280 vergelijkingen wat ruim vijf dagen in beslag neemt. Dit zijn nog steeds te veel vergelijkingen. Er is een beter idee. Kies een willekeurig boek uit. Noem het de boekensteun en vergelijk het met elk ander boek. Verdeel daarna de rij door alle boeken die tot aan de boekensteun horen links te plaatsen en de rest van de boeken rechts te plaatsen. Je hebt ontzettend veel tijd bespaard doordat je de boeken aan de linkerkant nooit meer met de boeken aan de rechterkant hoeft te vergelijken. Als je alleen de boeken aan de linkerkant bekijkt, dan kan je weer een willekeurig boek als boekensteun gebruiken en deze boeken links of rechts ervan plaatsen. Je kan dit soort indelingen blijven maken totdat je een groep kleine sublijnen hebt, die je zo snel mogelijk ordent door een andere strategie toe te passen, zoals invoegsortering. Elke sorteerronde bestaat uit minstens 1.280 vergelijkingen. Als je indelingen behoorlijk evenwichtig zijn dan duurt het ruim zeven rondes om de boeken per tien stuks in 128 sublijnen in te delen of 8.960 secondes. Per sublijn worden er 22 secondes extra toegevoegd. Hoe dan ook, via deze quicksort-methode worden boeken binnen drieënhalf uur gesorteerd. Maar er zit een addertje. Je indelingen kunnen onevenwichtig zijn, waardoor er veel tijd verloren gaat. Gelukkig gebeurt dit zelden. Daarom is de quicksort-methode een van de meest efficiënte strategieën die momenteel door programmeurs worden toegepast. Ze passen deze methode toe om producten in een webwinkel op prijs te ordenen of om een overzicht te maken van de dichtstbijzijnde benzinepompen op basis van afstand. In jouw geval heb je snel geordend en genoeg tijd overgehouden. Gewoon weer een productieve dag in de mediatheek.