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

Qual a maneira mais rápida de ordenar alfabeticamente a biblioteca? — Chand John

Tradutor: Margarida Ferreira Revisora: António Ribeiro

You work at the college library.

Trabalhas na biblioteca da faculdade.

You're in the middle of a quiet afternoon

Estás no meio de uma tarde tranquila

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

quando, subitamente, chega um carregamento de 1280 livros diferentes.

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

Os livros foram descarregados numa longa linha reta

but they're all out of order,

mas estão todos fora de ordem,

and the automatic sorting system is broken.

e o sistema de classificação está avariado.

To make matters worse, classes start tomorrow,

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

which means that first thing in the morning,

o que significa que, logo de manhã cedo,

students will show up in droves looking for these books.

todos os estudantes vão aparecer à procura desses livros.

How can you get them all sorted in time?

Como é que podes ordenar todos os livros a tempo?

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

Uma forma seria começar pelos dois primeiros livros,

num dos extremos da fila.

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

Se os dois primeiros livros estiverem por ordem, deixa-os ficar onde eles estão.

Otherwise, swap them.

Caso contrário, troca-os de lugar.

Then, look at the second and third books,

Depois, observa o segundo e o terceiro livros.

repeat the process,

e repete o procedimento.

and continue until you reach the end of the line.

Continua até chegares ao fim da fila.

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

A certa altura, encontras o livro que devia ser o último.

and keep swapping it with every subsequent book,

Vai-o trocando sempre de lugar com os livros posteriores,

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

até ele chegar ao fim da fila, ao lugar que lhe pertence.

Then, start from the beginning and repeat the process

Volta a começar do princípio e repete o procedimento.

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

até colocar o penúltimo livro no seu devido lugar.

and keep going until all books are sorted.

Volta a repetir tudo até todos os livros estarem nos seus lugares.

This approach is called Bubble Sort.

Este método chama-se "Ordenação por Flutuação".

It's simple but slow.

É simples, mas lento.

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

Tens que fazer 1279 comparações na primeira ronda,

then 1,278, and so on,

depois, 1278, e assim sucessivamente,

adding up to 818,560 comparisons.

num total de 818 560 comparações.

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

Se cada uma delas demorar só um segundo, o processo demorará nove dias.

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

Uma segunda estratégia seria começar por ordenar os dois primeiros livros.

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

Depois, comparar o terceiro livro com o livro no segundo lugar.

If it belongs before the second book, swap them,

Se ele deve ficar antes do segundo livro, troca-os de lugar.

then compare it with the book in the first spot,

Depois compara-o com o livro no primeiro lugar

and swap again if needed.

e troca-os, se necessário.

Now you've sorted the first three books.

Tens os três primeiros livros ordenados.

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

Continua com um livro de cada vez

comparing and swapping the new book with the one before it

comparando e trocando o novo livro com os que estão antes dele

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

até ele ficar corretamente colocado entre os livros ordenados até aí.

This is called Insertion Sort.

Este método chama-se "Ordenação por Inserção".

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

Ao contrário da "Ordenação por Flutuação"

não exige que se comparem todos os pares de livros.

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

Em média, só precisamos de comparar cada livro

to half of the books that came before it.

com metade dos livros que estão antes dele.

In that case, the total number of comparisons

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

would be 409,280,

seria de 409 280,

taking almost five days.

o que levaria quase cinco dias.

You're still doing way too many comparisons.

Continuas a ter que fazer demasiadas comparações.

Here's a better idea.

Esta é uma ideia melhor.

First, pick a random book.

Primeiro, agarra num livro ao acaso.

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

Chama-lhe "partição" e compara-o com o outros livros todos.

Then, divide the line

Depois divide a fila

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

colocando à esquerda todos os livros que devem ficar antes da partição

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

e à direita, os que devem ficar depois da partição.

You've just saved loads of time

Poupaste imenso tempo

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

porque não precisas de comparar nenhum dos livros da esquerda

to any of the ones on the right ever again.

com os da direita.

Now, looking only at the books on the left,

Depois, olha só para os livros da esquerda.

you can again pick a random partition book

Podes voltar a agarrar num livro ao acaso, outra "partição"

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

e separar os livros antes dela dos livros depois dela.

You can keep creating sub-partitions like this

Podes continuar a criar subpartições como estas

until you have a bunch of small sub-lines,

até teres um grupo de pequenas sublinhas,

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

cada uma das quais podes ordenar rapidamente,

usando outra estratégia como a "Ordenação por Inserção".

Each round of partitioning requires about 1,280 comparisons.

Cada ronda de partição exige cerca de 1280 comparações.

If your partitions are pretty balanced,

Se as partições estiverem equilibradas,

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

dividir os livros em 128 sublinhas de 10, deve precisar de sete rondas,

or 8,960 seconds.

ou seja 8960 segundos.

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

Ordenar as sublinhas, demorará mais 22 segundos cada.

All in all, this method known as QuickSort

Ao todo, este método, conhecido por "Ordenação Rápida"

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

pode ordenar os livros em menos de três horas e meia.

But there's a catch.

Mas há um inconveniente.

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

As partições podem ficar desequilibradas, e não poupar tempo nenhum

Luckily, this rarely happens.

Felizmente, isso acontece raramente.

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

É por isso que a Ordenação Rápida é uma das estratégias mais eficazes

used by programmers today.

usadas hoje pelos programadores.

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

Usam-na para ordenar, por preço, os artigos numa loja online

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

ou para criar uma lista de todas as estações de gasolina

perto de uma dada localidade

sorted by distance.

ordenadas pela distância.

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

No teu caso, fizeste uma ordenação rápida, com tempo de sobra.

Just another high-stakes day in the library.

Mais um dia de sobressalto na biblioteca