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

Qual a forma mais rápida de colocar em ordem alfabética sua estante de livros? Chand John

Tradutor: Raissa Mendes Revisor: Ruy Lopes Pereira

You work at the college library.

Você trabalha na biblioteca da faculdade.

Bem no meio de uma tarde tranquila,

You're in the middle of a quiet afternoon

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

de repente, chega um carregamento com 1.280 livros diferentes.

Os livros foram deixados numa linha reta,

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

but they're all out of order,

mas estão todos fora da ordem,

e o sistema de seleção automática está quebrado.

and the automatic sorting system is broken.

Para piorar as coisas, as aulas começam amanhã,

To make matters worse, classes start tomorrow,

which means that first thing in the morning,

o que significa que logo de manhã cedinho

students will show up in droves looking for these books.

vai aparecer um monte de estudantes procurando por esses livros.

How can you get them all sorted in time?

Como você vai conseguir organizá-los a tempo?

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

Um jeito seria começar numa extremidade da linha, com os dois primeiros livros.

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

Se os dois primeiros livros estiverem na ordem, então deixe-os onde estão.

Otherwise, swap them.

Caso contrário, troque-os entre si.

Then, look at the second and third books,

Depois, olhe o segundo e o terceiro livro,

repeat the process,

repita o processo,

and continue until you reach the end of the line.

e continue até chegar ao final da linha.

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

A uma certa altura, você vai chegar ao livro que deveria ser o último.

and keep swapping it with every subsequent book,

Continue trocando-o de lugar com os livros subsequentes,

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

passando-o de livro em livro até chegar ao fim da linha, onde é o lugar dele.

A seguir, comece do início e repita todo o processo

Then, start from the beginning and repeat the process

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

para colocar do segundo ao penúltimo livro nos lugares certos,

and keep going until all books are sorted.

e continue até que todos os livros estejam organizados.

This approach is called Bubble Sort.

Essa abordagem se chama "método da bolha".

It's simple but slow.

É simples, porém lento.

Você teria de fazer 1.279 comparações na primeira rodada,

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

then 1,278, and so on,

depois, 1.278, e assim por diante,

adding up to 818,560 comparisons.

chegando a 818.560 comparações.

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

Se cada uma levar apenas um segundo, o processo todo levará mais de nove dias.

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

Uma segunda estratégia seria começar ordenando apenas os dois primeiros livros.

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

Depois, pegar o terceiro e comparar com o livro na segunda posição.

If it belongs before the second book, swap them,

Se ele estiver na frente do segundo livro, então troque os dois,

depois compare-o com o livro na primeira posição,

then compare it with the book in the first spot,

and swap again if needed.

e troque de novo, se necessário.

Now you've sorted the first three books.

Agora que ordenou os primeiros três livros,

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

continue a adicionar um livro de cada vez ao subconjunto ordenado,

comparing and swapping the new book with the one before it

comparando e trocando o novo livro com o que estiver antes dele,

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

até estar corretamente colocado entre os livros ordenados até então.

Isso se chama "ordenação por inserção".

This is called Insertion Sort.

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

Diferente do método bolha, ele em geral não exige que se compare cada par.

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

Em média, espera-se ser necessário comparar cada livro somente

to half of the books that came before it.

com a metade dos livros que vieram antes dele.

In that case, the total number of comparisons

Nesse caso, o número total de comparações

would be 409,280,

seria de 409.280, o que levaria quase 5 dias.

taking almost five days.

Você ainda teria comparações demais a fazer.

You're still doing way too many comparisons.

Here's a better idea.

Eis aqui uma ideia melhor.

First, pick a random book.

Primeiro, pegue um livro qualquer.

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

Chame-o de "a divisória" e compare-o com todos os outros livros.

Then, divide the line

Depois, divida a linha,

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

colocando todos os livros que vêm antes da divisória à esquerda desta,

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

e todos aqueles que vêm depois dela, à sua direita.

You've just saved loads of time

Você acabou de economizar um tempão

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

ao não ter de comparar nenhum dos livros da esquerda

to any of the ones on the right ever again.

com nenhum dos livros da direita.

Now, looking only at the books on the left,

Bem, olhando agora apenas os livros da esquerda,

you can again pick a random partition book

você pode, de novo, eleger um "livro divisória" qualquer

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

e separar os livros que vêm antes dele daqueles que vêm depois.

You can keep creating sub-partitions like this

Continue a criar subdivisões assim

until you have a bunch of small sub-lines,

até ter um monte de subconjuntos,

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

que você ordenará rapidamente usando outra estratégia: ordenação por inserção.

Each round of partitioning requires about 1,280 comparisons.

Cada rodada de divisão dessa requer cerca de 1.280 comparações.

If your partitions are pretty balanced,

Se suas divisões forem bem equilibradas,

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

dividir os livros em 128 subconjuntos de 10 levaria cerca de 7 rodadas,

or 8,960 seconds.

ou 8.960 segundos.

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

Ordenar esses subconjuntos adicionaria cerca de 22 segundos para cada um.

All in all, this method known as QuickSort

No final das contas, esse método, conhecido como Quicksort,

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

poderia ordenar livros em menos de três a quatro horas.

But there's a catch.

Mas tem um porém.

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

Se as divisões ficarem desproporcionais, não haverá nenhuma economia de tempo.

Luckily, this rarely happens.

Felizmente, isso raramente acontece.

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

E essa é a razão por que o Quicksort é uma das estratégias mais eficientes

used by programmers today.

usadas por programadores hoje em dia.

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

Eles a usam para coisas como ordenar itens por preço numa loja on-line,

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

ou criar uma lista dos postos de gasolina perto de um determinado lugar,

sorted by distance.

de acordo com a distância.

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

No seu caso, você terminou o "quick sorting" com tempo de sobra.

Just another high-stakes day in the library.

E lá se vai mais um dia eletrizante na biblioteca.