What's the fastest way to alphabetize your bookshelf? - Chand John

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

Traducător: Denise RQ Corector: Robert Deliman

You work at the college library.

Lucrezi la biblioteca universității.

You're in the middle of a quiet afternoon

E o după-masă liniștită

when suddenly a shipment of 1,280 different books arrives.

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

The books have been dropped of in one long straight line,

but they're all out of order,

dar în dezordine

and the automatic sorting system is broken.

și sistemul de clasificare automată e stricat.

Pe deasupra, cursurile încep mâine

To make matters worse, classes start tomorrow,

which means that first thing in the morning,

cea ce înseamnă că de dimineață devreme

studenții vor veni în număr mare ca să-și caute cărțile.

students will show up in droves looking for these books.

How can you get them all sorted in time?

Cum le sortezi pe toate la timp ?

One way would be to start at one end of the line with the first pair of books.

O metodă ar fi începerea dintr-un capăt cu prima pereche de cărți.

If the first two books are in order, then leave them as they are.

Dacă primele două cărți sunt în ordine, lasă-le așa.

Otherwise, swap them.

Dacă nu, schimbă-le între ele.

Then, look at the second and third books,

Fă același lucru cu a doua și a treia carte, repetă procesul

repeat the process,

and continue until you reach the end of the line.

și continuă până când ajungi la capătul liniei.

At some point, you'll come across the book that should be last,

La un moment dat vei da de cartea care ar trebui să fie ultima

și continuă să le schimbi cu fiecare carte ce urmează,

and keep swapping it with every subsequent book,

moving it down the line until it reaches the end where it belongs.

mutându-le până ajung la locul lor.

Apoi ia-o de la început și repetă procesul

Then, start from the beginning and repeat the process

to get the second to last book in its proper place,

ordonând toate cărțile la locul lor

and keep going until all books are sorted.

și continuă așa până toate vor fi sortate.

This approach is called Bubble Sort.

Abordarea aceasta se numește metoda balonului.

It's simple but slow.

E simplă, dar lentă.

Ai face inițial 1.279 de comparații,

You'd make 1,279 comparisons in the first round,

then 1,278, and so on,

apoi 1.278 și tot așa,

adding up to 818,560 comparisons.

ajungând la 818.560 de comparații.

If each took just one second, the process would take over nine days.

Dacă fiecare ar lua o secundă, procesul ar dura peste nouă zile.

A second strategy would be to start by sorting just the first two books.

O altă strategie ar fi să începi cu sortarea primelor două cărți și atât.

Then, take the third book and compare it with the book in the second spot.

Apoi ia a treia carte și compar-o cu cea de-a doua.

If it belongs before the second book, swap them,

Dacă locul său e înaintea acesteia, schimbă-le între ele,

apoi compar-o cu cea de pe primul loc

then compare it with the book in the first spot,

and swap again if needed.

și schimbă iar dacă e nevoie.

Now you've sorted the first three books.

Acum ai sortat primele trei cărți.

Keep adding one book at a time to the sorted sub-line,

Continuă să adaugi câte o carte liniei deja ordonate,

comparing and swapping the new book with the one before it

comparând și plasând noua carte

until it's correctly placed among the books sorted so far.

acolo unde se potrivește.

Această ordonare se numește tehnica de inserție.

This is called Insertion Sort.

Unlike Bubble Sort, it usually doesn't require comparing every pair of books.

Comparativ cu cea inițială,

aceasta nu cere compararea fiecărei perechi de cărți.

On average, we'd expect to only need to compare each book

În medie, se așteaptă compararea fiecărei cărți

to half of the books that came before it.

cu jumătatea cărților ce urmează.

In that case, the total number of comparisons

În cazul ăsta, numărul total de comparații

would be 409,280,

ar fi 409 280,

taking almost five days.

durând cam cinci zile.

Încă faci prea multe comparații.

You're still doing way too many comparisons.

Here's a better idea.

Uite o idee mai bună.

First, pick a random book.

Întâi, ridică aleatoriu o carte.

Call it the partition and compare it to every other book.

Folosește-o ca separator și compar-o cu fiecare carte.

Then, divide the line

Apoi împarte linia

by placing all the books that come before the partition on its left

așezând cărțile dinaintea separatorului la stânga

and all the ones that come after it on its right.

și cele ce vin după, la dreapta.

You've just saved loads of time

Tocmai ai economisit o grămadă de timp

by not having to compare any of the books on the left

fără să fi nevoit să compari toate cărțile din stânga

to any of the ones on the right ever again.

cu oricare din dreapta.

Now, looking only at the books on the left,

Acum, uitându-te doar la cărțile din stânga,

you can again pick a random partition book

poți iar alege o partiție aleatorie

and separate those books that come before it from those that come after it.

și separă cărțile ce vin înaintea ei de cele ce vin după ea.

You can keep creating sub-partitions like this

Continui să împarți cărțile pe baza aceluiași principiu

until you have a bunch of small sub-lines,

până ajungi să formezi mici stive de cărți,

each of which you'd sort quickly using another strategy, like Insertion Sort.

fiecare ordonându-se rapid pe baza altei strategii, la de inserție.

Each round of partitioning requires about 1,280 comparisons.

Fiecare rundă de partiție numără cam 1 280 de comparații.

If your partitions are pretty balanced,

Dacă stivele conțin cam același număr de cărți,

dividing the books into 128 sub-lines of ten would take about seven rounds,

ar trebui să dea 128 de stive cu 10 cărți în fiecare grup,

or 8,960 seconds.

și durează cam 8 960 de secunde.

Sorting these sub-lines would add about 22 seconds each.

Sortarea acestor grupuri mai mici ar dura cam 22 de secunde fiecare.

All in all, this method known as QuickSort

Per total, cu această tehnică numită catalogarea rapidă

could sort the books in under three and a half hours.

poți ordona cărțile în mai puțin de trei ore și jumătate.

But there's a catch.

Dar există o hibă.

Your partitions could end up lopsided, saving no time at all.

Partițiile pot fi asimetrice, fiind cronofage.

Luckily, this rarely happens.

Din fericire se întâmplă rar.

That's why QuickSort is one of the most efficient strategies

De aceea catalogarea rapidă e una din cele mai eficiente strategii

used by programmers today.

folosite de programatorii de azi.

They use it for things like sorting items in an online store by price,

Se folosește la sortarea articolelor după preț în magazinele online

or creating a list of all the gas stations close to a given location

sau în crearea listelor stațiilor de benzină din vecinătatea unei locații

sorted by distance.

sortate după distanță.

In your case, you're done quick sorting with time to spare.

În cazul tău, ai sortat rapid și ți-a rămas și ceva timp liber.

Just another high-stakes day in the library.

Încă o zi cu miză mare la bibliotecă.