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.
Tu lavori nella biblioteca universitaria. Sei nel bel mezzo di un placido pomeriggio quando all'improvviso arriva un carico di 1.280 libri diversi. I libri sono stati consegnati in una singola, lunga fila, ma sono tutti in disordine, e il sistema di classificazione automatica è rotto. Come se non bastasse, le lezioni ricominciano domani, il che vuol dire che di prima mattina gli studenti si presenteranno in massa alla ricerca dei loro libri. Come puoi catalogarli tutti in tempo? Un modo sarebbe cominciare da un capo della fila con il primo paio di libri. Se i primi due sono in ordine, lasciali come sono. Altrimenti, scambiali. Poi guarda il secondo e il terzo libro, ripeti il procedimento e continua fino alla fine della linea. Ad un certo punto arriverai a quello che dovrebbe essere l'ultimo, continua a scambiarlo con i libri seguenti, facendolo scorrere finché non raggiunge la fine, il suo posto. Poi, comincia dall'inizio e ripeti il procedimento per mettere a posto il penultimo libro, e continua finché tutti i libri non sono catalogati. Questo metodo si chiama <i>Bubble Sort</i>. È semplice ma lento. Dovresti fare 1.279 confronti nel primo giro, poi 1,278 e così via, per un totale di 818.560 confronti. Se ogni confronto durasse un secondo, l'intero processo durerebbe nove giorni. Una seconda strategia sarebbe di iniziare a catalogare solo i primi due libri. Poi prendi il terzo libro e lo confronti con il libro al secondo posto. Se deve stare prima del secondo, scambiali, poi confrontalo con il libro al primo posto e scambiali di nuovo se necessario. Ora hai catalogato i primi tre libri. Prosegui aggiungendo un libro alla volta alla pila già catalogata, confrontando e scambiando il nuovo libro con quello che lo precede finché non si trova al posto giusto tra i libri finora catalogati. Questo si chiama <i>Insertion Sort</i>. A differenza del Bubble Sort, non bisogna confrontare ciascun paio di libri. In media, dovremmo solo confrontare ogni libro con la metà dei libri che lo precedono. In questo caso, il numero totale di confronti sarebbe 409.280, e richiederebbe quasi cinque giorni. Stiamo facendo ancora troppi confronti. Ecco un'idea migliore. Prendi un libro a caso. Questo è il <i>divisorio</i> e lo confronterai con ogni altro libro. Poi, dividi la fila mettendo tutti i libri prima del divisorio a sinistra e quello dopo a destra. Hai appena risparmiato un sacco di tempo non confrontando nessun libro a sinistra con quelli della destra. Guardando i libri sulla sinistra, scegli un altro libro <i>divisorio</i> a caso e separa i libri che vengono prima da quelli che vengono dopo. Continua a creare sotto-divisori così finché non hai tante mini pile di libri, ognuna delle quali puoi catalogare con un'altra strategia, come l'Insertion. Ogni ciclo di ripartizioni richiede circa 1.280 confronti. Se i divisori sono ben equilibrati, dividere i libri in 128 file di dieci richiederebbe sette cicli, o 8.960 secondi. Catalogare queste sotto-file richiederebbe 22 secondi circa. In tutto, questo metodo, conosciuto come <i>QuickSort</i>, potrebbe catalogare i libri in meno di tre ore e mezza. Ma c'è un inghippo. I divisori possono essere sbilanciati e non ti farebbero risparmiare tempo. Per fortuna, accade raramente. Ecco perché QuickSort è una della strategie più efficaci usata oggi dai programmatori di computer. È usata ad esempio nei negozi online per catalogare oggetti in base al prezzo, o per elencare i benzinai vicini ad un dato luogo in base alla distanza. Nel tuo caso, hai finito la catalogazione in men che non si dica. Un'altra giornata da brividi in biblioteca.