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ă.