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.
Pracujesz w bibliotece uniwersyteckiej. Jest środek spokojnego popołudnia, kiedy nagle przybywa dostawa 1280 książek. Książki zostały ułożone w jednym, długim rzędzie w losowej kolejności, a automatyczny system do segregacji jest zepsuty. Co gorsza, jutro zaczynają się zajęcia, co oznacza, że z samego rana książek będą szukać tłumy studentów. Jak posortować je na czas? Jeden ze sposobów to rozpoczęcie od pierwszej pary książek z jednego końca. Jeśli dwie pierwsze książki są dobrze ułożone, zostaw je bez zmian. W przeciwnym razie zamień je miejscami. Teraz spójrz na drugą i trzecią książkę, powtórz proces i kontynuuj, aż dotrzesz do końca linii. W końcu natkniesz się na książkę, która powinna być ostatnia. Zamieniaj ją z każdą kolejną książką, przesuwając wzdłuż rzędu aż na koniec. Następnie zacznij od początku i powtórz cały proces, żeby umieścić przedostatnią książkę na swoim miejscu. Kontynuuj, aż książki będą posortowane. Ten sposób to sortowanie bąbelkowe. Jest łatwe, ale powolne. W pierwszej rundzie byłoby 1279 porównań, w kolejnej 1278 i tak dalej, co w sumie daje 818 560 porównań. Gdyby każde zajęło tylko sekundę, proces potrwałby ponad dziewięć dni. Inny sposób rozpoczyna się od ułożenia tylko dwóch pierwszych książek. Następnie weź trzecią książkę i porównaj do tej stojącej na drugim miejscu. Jeśli powinna znaleźć się przed nią, zamień je. Potem porównaj ją do pierwszej książki i jeśli trzeba, zamień miejscami. Trzy pierwsze książki są już posortowane. Dodawaj po jednej nowej książce do posortowanej grupy, porównując ją i zamieniając z książką stojącą przed nią, aż trafi na właściwe miejsce. Ten sposób to sortowanie przez wstawianie. W odróżnieniu od sortowania bąbelkowego nie trzeba porównywać każdej pary książek. Każdą książkę będzie trzeba porównać średnio tylko z połową tych, stojących przed nią. W tym przypadku całkowita liczba porównań wyniosłaby 409 280, co zajęłoby prawie pięć dni. To wciąż zbyt wiele porównań. Oto lepszy pomysł. Najpierw wybierz przypadkową książkę. Nazwijmy ją przegrodą i porównajmy z pozostałymi książkami. Następnie podzielmy rząd, umieszczając wszystkie książki, które mają znaleźć się przed przegrodą po jej lewej, a te, które powinny stanąć za nią, po jej prawej stronie. Właśnie oszczędziliśmy mnóstwo czasu. Już nie będzie trzeba porównywać żadnej z książek po lewej do tych po prawej stronie. Teraz patrząc tylko na książki po lewej stronie, można wybrać przypadkową przegrodę i oddzielić książki, mające stać przed, od tych, które powinny stanąć za nią. Można dalej tworzyć takie przegrody, aż uzyska się wiele małych grup, z których każdą posortuje się, używając innej strategii. Każde rozdzielenie wymaga około 1280 porównań. Jeśli segmenty są w miarę równe, podzielenie książek na 128 grup po 10 będzie wymagało około siedmiu rund albo 8960 sekund. Posortowanie każdej grupy zajmie wtedy około 22 sekund. Tak czy inaczej ta metoda znana jako sortowanie szybkie może posortować książki w mniej niż 3,5 godziny. Ale jest haczyk. Segmenty mogą okazać się niesymetryczne, co oznacza brak oszczędności czasu. Na szczęście rzadko się to zdarza. Dlatego sortowanie szybkie to jedna z najbardziej wydajnych strategii używanych przez dzisiejszych programistów. Korzysta się z niej do sortowania towarów w sklepie internetowym według ceny albo tworzenia listy pobliskich stacji benzynowych, ułożonych według odległości. Właśnie udało się skończyć szybkie sortowanie przed czasem. Za tobą kolejny pracowity dzień w bibliotece.