Care este cel mai rapid mod de a aranja în ordine alfabetică biblioteca dvs.? - Chand John

Vezi lecția completă: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

Lucrezi la biblioteca universității. E o după-amiază liniștită, când deodată vin 1.280 de cărți. Cărțile sunt așezate într-o linie dreaptă, dar nu în ordine și sistemul de clasificare automată nu funcționează. Cum le sortezi rapid pe toate? Chand Ioan îți arată cum să faci acest lucru și-ți explică algoritmii pe care bibliotecarii și motoarele de căutare le utilizează pentru a organiza informațiile rapid.

Lecție de Chand John, animație de Anton Trofimov.

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