Δουλεύετε στη βιβλιοθήκη του πανεπιστημίου. Βρίσκεστε στη μέση ενός ήσυχου απογεύματος όταν ξαφνικά καταφτάνει ένα φορτίο 1.280 διαφορετικών βιβλίων. Τα βιβλία έχουν παραταχθεί σε μια μεγάλη ευθεία γραμμή, αλλά είναι όλα εκτός σειράς και το σύστημα αυτόματης ταξινόμησης είναι εκτός λειτουργίας. Για κακή σας τύχη, αύριο αρχίζουν τα μαθήματα, πράγμα που σημαίνει ότι αύριο πρωί - πρωί, θα εμφανιστούν ορδές φοιτητών προς αναζήτηση αυτών των βιβλίων. Πώς μπορείτε να τα ταξινομήσετε όλα εγκαίρως; Ένας τρόπος θα ήταν να ξεκινήσετε από τη μία άκρη της γραμμής, με τα πρώτα δύο βιβλία. Εάν τα δύο πρώτα βιβλία είναι στη σειρά, τότε τα αφήνετε ως έχουν. Αλλιώς, τα αντιμεταθέτετε. Έπειτα, ελέγχετε το δεύτερο και το τρίτο βιβλίο, επαναλαμβάνετε τη διαδικασία και συνεχίζετε έως ότου να φτάσετε στο τέλος της γραμμής. Κάποια στιγμή, θα βρείτε το βιβλίο που θα έπρεπε να είναι τελευταίο και συνεχίζοντας να το αντιμεταθέτετε με όλα τα επόμενα βιβλία, το μετακινείτε έως το τέλος της γραμμής, όπου είναι και η θέση του. Τότε, ξεκινάτε από την αρχή και επαναλαμβάνετε τη διαδικασία, για να βάλετε το προτελευταίο βιβλίο στη σωστή του θέση και συνεχίζετε μέχρι όλα τα βιβλία να είναι ταξινομημένα. Αυτή η προσέγγιση ονομάζεται «Ταξινόμηση Φυσαλίδας». Είναι απλή, αλλά αργή. Στον πρώτο γύρο, θα χρειαζόταν να πραγματοποιήσετε 1.279 συγκρίσεις, έπειτα 1.278 και ούτω καθεξής, πραγματοποιώντας συνολικά 818.560 συγκρίσεις. Εάν η κάθε μία έπαιρνε ένα δευτερόλεπτο, όλο αυτό θα διαρκούσε εννέα ημέρες. Μια δεύτερη στρατηγική θα ήταν να ξεκινούσατε ταξινομώντας απλώς τα πρώτα δύο βιβλία. Έπειτα, συγκρίνετε το τρίτο βιβλίο με αυτό στη δεύτερη θέση. Εάν ανήκει πριν το δεύτερο βιβλίο, τα αντιμεταθέτετε, και μετά το συγκρίνετε με το πρώτο βιβλίο, και τα αντιμεταθέτετε κι αυτά, εάν πρέπει. Τώρα έχετε ταξινομήσει τα πρώτα τρία βιβλία. Συνεχίζετε να προσθέτετε ένα βιβλίο τη φορά στα ήδη ταξινομημένα, συγκρίνοντας και αντιμεταθέτοντας το νέο βιβλίο με το ακριβώς προηγούμενο, μέχρι να είναι σωστά τοποθετημένο ανάμεσα στα έως τώρα ταξινομημένα βιβλία. Αυτή ονομάζεται «Ταξινόμηση με Εισαγωγή». Αντίθετα από την Ταξινόμηση Φυσαλίδας, συνήθως δεν χρειάζεται να συγκρίνουμε όλα τα ζεύγη βιβλίων. Κατά μέσο όρο, θα αναμέναμε να χρειαζόταν να συγκρίνουμε κάθε βιβλίο με τα μισά όσων βρίσκονταν πριν από αυτό. Σε αυτήν την περίπτωση, ο συνολικός αριθμός συγκρίσεων θα ανερχόταν στις 409.280, διαρκώντας σχεδόν πέντε ημέρες. Ακόμα πραγματοποιείτε υπερβολικά πολλές συγκρίσεις. Ορίστε μια καλύτερη ιδέα. Αρχικά, διαλέξτε ένα τυχαίο βιβλίο. Ονομάστε το στοιχείο διαχωρισμού και συγκρίνετέ το με κάθε άλλο βιβλίο. Στη συνέχεια, χωρίστε τη γραμμή τοποθετώντας όλα τα βιβλία που είναι πριν από αυτό, στα αριστερά του και όλα εκείνα που είναι μετά, στα δεξιά του. Μόλις γλιτώσατε πολύ χρόνο, καθώς δεν θα χρειαστεί ποτέ να συγκρίνετε κανένα βιβλίο στα αριστερά με κανένα από εκείνα που είναι στα δεξιά. Τώρα, κοιτώντας μόνο τα βιβλία στα αριστερά, μπορείτε να διαλέξετε εκ νέου ένα τυχαίο βιβλίο διαχωρισμού και να διαχωρίσετε τα βιβλία που είναι πριν από αυτό, από εκείνα που είναι μετά. Μπορείτε να συνεχίσετε να φτιάχνετε επιμέρους τμήματα έως ότου να έχετε αρκετές μικρές υποομάδες βιβλίων, που θα μπορούσατε να ταξινομήσετε γρήγορα χρησιμοποιώντας κάποια άλλη μέθοδο, όπως Ταξινόμηση με Εισαγωγή. Κάθε γύρος «τμηματοποίησης» απαιτεί περίπου 1.280 συγκρίσεις. Εάν τα τμήματά σας είναι αρκετά ισορροπημένα, το να χωρίσετε τα βιβλία σε 128 υποομάδες των δέκα θα χρειαζόταν περίπου επτά γύρους ή 8.960 δευτερόλεπτα. Το να ταξινομήσετε αυτές τις υποομάδες θα προσέθετε 22 δευτερόλεπτα για κάθε μία. Τελικά, αυτή η μέθοδος, γνωστή ως «Ταχεία Ταξινόμηση» θα μπορούσε να ταξινομήσει τα βιβλία σε λιγότερο από τρεισήμισι ώρες. Αλλά υπάρχει παγίδα. Τα τμήματα μπορεί να καταλήξουν ασύμμετρα, και να φάνε πολύ χρόνο. Ευτυχώς, αυτό σπανίως συμβαίνει. Για αυτό η Ταχεία Ταξινόμηση είναι από τις πιο αποδοτικές μεθόδους που χρησιμοποιούν οι προγραμματιστές σήμερα. Τη χρησιμοποιούν για ταξινόμηση προϊόντων ηλεκτρονικών μαγαζιών, βάσει τιμής ή για να δημιουργούν λίστες με όλα τα βενζινάδικα κοντά σε μια τοποθεσία ταξινομημένα με βάση την απόσταση. Εσείς, κάνατε μια γρήγορη ταξινόμηση και σας περίσσεψε και χρόνος. Άλλη μια «άγρια» μέρα στη βιβλιοθήκη.
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.