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

Veja a lição completa: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

Você trabalha na biblioteca da faculdade. No meio de uma tarde tranquila, chega, de repente, um carregamento com 1.280 livros diferentes. Os livros foram descarregados numa linha reta, mas estão todos fora de ordem, e o sistema de seleção automática está quebrado. Como fazer para organizar os livros rapidamente? Chand John nos mostra como, explicando como os algoritmos ajudam os bibliotecários e os mecanismos de busca a organizar rapidamente a informação.

Lição de Chand John; animação de Anton Trofimov.

Você trabalha na biblioteca da faculdade.

Bem no meio de uma tarde tranquila,

de repente, chega um carregamento
com 1.280 livros diferentes.

Os livros foram deixados numa linha reta,

mas estão todos fora da ordem,

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

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

o que significa que logo de manhã cedinho

vai aparecer um monte de estudantes
procurando por esses livros.

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

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

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

Caso contrário, troque-os entre si.

Depois, olhe o segundo e o terceiro livro,

repita o processo,

e continue até chegar ao final da linha.

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

Continue trocando-o de lugar
com os livros subsequentes,

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

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

e continue até que todos os livros
estejam organizados.

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

É simples, porém lento.

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

depois, 1.278, e assim por diante,

chegando a 818.560 comparações.

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

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

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

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

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

e troque de novo, se necessário.

Agora que ordenou
os primeiros três livros,

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

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

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

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

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

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

com a metade dos livros
que vieram antes dele.

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

seria de 409.280,
o que levaria quase 5 dias.

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

Eis aqui uma ideia melhor.

Primeiro, pegue um livro qualquer.

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

Depois, divida a linha,

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

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

Você acabou de economizar um tempão

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

com nenhum dos livros da direita.

Bem, olhando agora apenas
os livros da esquerda,

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

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

Continue a criar subdivisões assim

até ter um monte de subconjuntos,

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

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

Se suas divisões forem bem equilibradas,

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

ou 8.960 segundos.

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

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

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

Mas tem um porém.

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

Felizmente, isso raramente acontece.

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

usadas por programadores hoje em dia.

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

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

de acordo com a distância.

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

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