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.
Lucrezi la biblioteca universității. E o după-masă liniștită când deodată vine o livrare de 1.280 de cărți. Cărțile au fost livrate într-o linie lungă și continuă, dar în dezordine și sistemul de clasificare automată e stricat. Pe deasupra, cursurile încep mâine cea ce înseamnă că de dimineață devreme studenții vor veni în număr mare ca să-și caute cărțile. Cum le sortezi pe toate la timp ? O metodă ar fi începerea dintr-un capăt cu prima pereche de cărți. Dacă primele două cărți sunt în ordine, lasă-le așa. Dacă nu, schimbă-le între ele. Fă același lucru cu a doua și a treia carte, repetă procesul și continuă până când ajungi la capătul liniei. La un moment dat vei da de cartea care ar trebui să fie ultima și continuă să le schimbi cu fiecare carte ce urmează, mutându-le până ajung la locul lor. Apoi ia-o de la început și repetă procesul ordonând toate cărțile la locul lor și continuă așa până toate vor fi sortate. Abordarea aceasta se numește metoda balonului. E simplă, dar lentă. Ai face inițial 1.279 de comparații, apoi 1.278 și tot așa, ajungând la 818.560 de comparații. Dacă fiecare ar lua o secundă, procesul ar dura peste nouă zile. O altă strategie ar fi să începi cu sortarea primelor două cărți și atât. Apoi ia a treia carte și compar-o cu cea de-a doua. Dacă locul său e înaintea acesteia, schimbă-le între ele, apoi compar-o cu cea de pe primul loc și schimbă iar dacă e nevoie. Acum ai sortat primele trei cărți. Continuă să adaugi câte o carte liniei deja ordonate, comparând și plasând noua carte acolo unde se potrivește. Această ordonare se numește tehnica de inserție. Comparativ cu cea inițială, aceasta nu cere compararea fiecărei perechi de cărți. În medie, se așteaptă compararea fiecărei cărți cu jumătatea cărților ce urmează. În cazul ăsta, numărul total de comparații ar fi 409 280, durând cam cinci zile. Încă faci prea multe comparații. Uite o idee mai bună. Întâi, ridică aleatoriu o carte. Folosește-o ca separator și compar-o cu fiecare carte. Apoi împarte linia așezând cărțile dinaintea separatorului la stânga și cele ce vin după, la dreapta. Tocmai ai economisit o grămadă de timp fără să fi nevoit să compari toate cărțile din stânga cu oricare din dreapta. Acum, uitându-te doar la cărțile din stânga, poți iar alege o partiție aleatorie și separă cărțile ce vin înaintea ei de cele ce vin după ea. Continui să împarți cărțile pe baza aceluiași principiu până ajungi să formezi mici stive de cărți, fiecare ordonându-se rapid pe baza altei strategii, la de inserție. Fiecare rundă de partiție numără cam 1 280 de comparații. Dacă stivele conțin cam același număr de cărți, ar trebui să dea 128 de stive cu 10 cărți în fiecare grup, și durează cam 8 960 de secunde. Sortarea acestor grupuri mai mici ar dura cam 22 de secunde fiecare. Per total, cu această tehnică numită catalogarea rapidă poți ordona cărțile în mai puțin de trei ore și jumătate. Dar există o hibă. Partițiile pot fi asimetrice, fiind cronofage. Din fericire se întâmplă rar. De aceea catalogarea rapidă e una din cele mai eficiente strategii folosite de programatorii de azi. Se folosește la sortarea articolelor după preț în magazinele online sau în crearea listelor stațiilor de benzină din vecinătatea unei locații sortate după distanță. În cazul tău, ai sortat rapid și ți-a rămas și ceva timp liber. Încă o zi cu miză mare la bibliotecă.