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

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

Trabalhas na biblioteca da faculdade. Estás no meio de uma tarde tranquila quando, subitamente, chega um carregamento de 1280 de livros diferentes. Os livros foram descarregados numa longa linha reta mas estão todos fora de ordem, e o sistema de classificação está avariado. Como podes ordenar os livros rapidamente? Chand John mostra como é possível, lançando luz em como os algoritmos ajudam bibliotecários e motores de busca a ordenar rapidamente informações.

Trabalhas na biblioteca da faculdade.

Estás no meio de uma tarde tranquila

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

Os livros foram descarregados
numa longa linha reta

mas estão todos fora de ordem,

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

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

o que significa que,
logo de manhã cedo,

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

Como é que podes ordenar
todos os livros a tempo?

Uma forma seria começar
pelos dois primeiros livros,

num dos extremos da fila.

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

Caso contrário, troca-os de lugar.

Depois, observa o segundo
e o terceiro livros.

e repete o procedimento.

Continua até chegares ao fim da fila.

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

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

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

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

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

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

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

É simples, mas lento.

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

depois, 1278, e assim sucessivamente,

num total de 818 560 comparações.

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

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

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

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

Depois compara-o com o livro
no primeiro lugar

e troca-os, se necessário.

Tens os três primeiros livros
ordenados.

Continua com um livro de cada vez

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

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

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

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

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

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

com metade dos livros
que estão antes dele.

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

seria de 409 280,

o que levaria quase cinco dias.

Continuas a ter que fazer
demasiadas comparações.

Esta é uma ideia melhor.

Primeiro, agarra num livro ao acaso.

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

Depois divide a fila

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

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

Poupaste imenso tempo

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

com os da direita.

Depois, olha só
para os livros da esquerda.

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

e separar os livros antes dela
dos livros depois dela.

Podes continuar a criar subpartições
como estas

até teres um grupo de pequenas sublinhas,

cada uma das quais
podes ordenar rapidamente,

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

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

Se as partições estiverem equilibradas,

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

ou seja 8960 segundos.

Ordenar as sublinhas,
demorará mais 22 segundos cada.

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

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

Mas há um inconveniente.

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

Felizmente, isso acontece raramente.

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

usadas hoje pelos programadores.

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

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

perto de uma dada localidade

ordenadas pela distância.

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

Mais um dia de sobressalto na biblioteca