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