0:00:06.947,0:00:09.277
Trabalhas na biblioteca da faculdade.

0:00:09.277,0:00:11.660
Estás no meio de uma tarde tranquila

0:00:11.660,0:00:17.311
quando, subitamente, chega um carregamento[br]de 1280 livros diferentes.

0:00:18.560,0:00:21.108
Os livros foram descarregados[br]numa longa linha reta

0:00:21.690,0:00:23.433
mas estão todos fora de ordem,

0:00:23.433,0:00:26.485
e o sistema de classificação[br]está avariado.

0:00:27.031,0:00:29.757
Para piorar as coisas,[br]as aulas começam amanhã

0:00:29.757,0:00:32.500
o que significa que,[br]logo de manhã cedo,

0:00:32.500,0:00:35.947
todos os estudantes vão aparecer[br]à procura desses livros.

0:00:36.557,0:00:38.965
Como é que podes ordenar[br]todos os livros a tempo?

0:00:39.493,0:00:42.788
Uma forma seria começar[br]pelos dois primeiros livros,

0:00:42.788,0:00:44.669
num dos extremos da fila.

0:00:44.779,0:00:48.626
Se os dois primeiros livros estiverem[br]por ordem, deixa-os ficar onde eles estão.

0:00:48.626,0:00:50.920
Caso contrário, troca-os de lugar.

0:00:50.920,0:00:53.297
Depois, observa o segundo[br]e o terceiro livros.

0:00:53.297,0:00:54.969
e repete o procedimento.

0:00:55.510,0:00:58.035
Continua até chegares ao fim da fila.

0:00:58.035,0:01:01.185
A certa altura, encontras o livro[br]que devia ser o último.[br]

0:01:01.185,0:01:04.810
Vai-o trocando sempre de lugar[br]com os livros posteriores,

0:01:04.810,0:01:08.898
até ele chegar ao fim da fila,[br]ao lugar que lhe pertence.

0:01:09.316,0:01:12.406
Volta a começar do princípio[br]e repete o procedimento.

0:01:12.406,0:01:15.437
até colocar o penúltimo livro[br]no seu devido lugar.

0:01:15.510,0:01:18.875
Volta a repetir tudo até todos os livros[br]estarem nos seus lugares.

0:01:18.875,0:01:21.862
Este método chama-se [br]"Ordenação por Flutuação".

0:01:21.862,0:01:24.156
É simples, mas lento.

0:01:24.156,0:01:28.912
Tens que fazer 1279 comparações[br]na primeira ronda,

0:01:29.331,0:01:33.486
depois, 1278, e assim sucessivamente,

0:01:33.632,0:01:38.510
num total de 818 560 comparações.

0:01:38.542,0:01:43.700
Se cada uma delas demorar só um segundo,[br]o processo demorará nove dias.

0:01:44.273,0:01:48.569
Uma segunda estratégia seria começar[br]por ordenar os dois primeiros livros.

0:01:48.723,0:01:53.533
Depois, comparar o terceiro livro[br]com o livro no segundo lugar.

0:01:53.733,0:01:57.173
Se ele deve ficar antes do segundo livro,[br]troca-os de lugar.

0:01:57.173,0:01:59.641
Depois compara-o com o livro[br]no primeiro lugar

0:01:59.641,0:02:01.682
e troca-os, se necessário.

0:02:01.682,0:02:03.880
Tens os três primeiros livros[br]ordenados.

0:02:04.180,0:02:07.950
Continua com um livro de cada vez[br]

0:02:07.950,0:02:11.809
comparando e trocando o novo livro[br]com os que estão antes dele

0:02:11.809,0:02:15.858
até ele ficar corretamente colocado[br]entre os livros ordenados até aí.

0:02:16.004,0:02:18.284
Este método chama-se[br]"Ordenação por Inserção".

0:02:18.284,0:02:20.434
Ao contrário da "Ordenação por Flutuação"

0:02:20.434,0:02:23.552
não exige que se comparem[br]todos os pares de livros.

0:02:23.552,0:02:26.990
Em média, só precisamos[br]de comparar cada livro

0:02:26.990,0:02:29.550
com metade dos livros[br]que estão antes dele.

0:02:29.550,0:02:32.359
Neste caso, o número total de comparações

0:02:32.359,0:02:35.983
seria de 409 280,

0:02:35.983,0:02:37.953
o que levaria quase cinco dias.

0:02:38.135,0:02:40.733
Continuas a ter que fazer[br]demasiadas comparações.

0:02:40.733,0:02:42.642
Esta é uma ideia melhor.

0:02:42.642,0:02:44.885
Primeiro, agarra num livro ao acaso.

0:02:45.112,0:02:49.115
Chama-lhe "partição" e compara-o[br]com o outros livros todos.

0:02:49.606,0:02:51.587
Depois divide a fila

0:02:51.587,0:02:55.666
colocando à esquerda todos os livros[br]que devem ficar antes da partição

0:02:55.666,0:02:58.825
e à direita, os que devem ficar[br]depois da partição.

0:02:58.825,0:03:00.615
Poupaste imenso tempo

0:03:00.615,0:03:03.917
porque não precisas de comparar[br]nenhum dos livros da esquerda

0:03:03.917,0:03:06.235
com os da direita.

0:03:07.245,0:03:09.665
Depois, olha só[br]para os livros da esquerda.

0:03:09.783,0:03:12.769
Podes voltar a agarrar num livro[br]ao acaso, outra "partição"

0:03:12.769,0:03:17.266
e separar os livros antes dela[br]dos livros depois dela.

0:03:17.266,0:03:19.736
Podes continuar a criar subpartições[br]como estas

0:03:19.736,0:03:22.484
até teres um grupo de pequenas sublinhas,

0:03:22.484,0:03:24.900
cada uma das quais[br]podes ordenar rapidamente,

0:03:24.900,0:03:27.809
usando outra estratégia[br]como a "Ordenação por Inserção".

0:03:27.809,0:03:32.662
Cada ronda de partição exige[br]cerca de 1280 comparações.

0:03:33.298,0:03:35.647
Se as partições estiverem equilibradas,

0:03:35.647,0:03:41.301
dividir os livros em 128 sublinhas de 10,[br]deve precisar de sete rondas,

0:03:41.301,0:03:43.947
ou seja 8960 segundos.

0:03:44.256,0:03:48.172
Ordenar as sublinhas, [br]demorará mais 22 segundos cada.

0:03:48.736,0:03:51.989
Ao todo, este método,[br]conhecido por "Ordenação Rápida"

0:03:51.989,0:03:54.773
pode ordenar os livros[br]em menos de três horas e meia.

0:03:54.773,0:03:56.242
Mas há um inconveniente.

0:03:56.242,0:03:59.456
As partições podem ficar desequilibradas,[br]e não poupar tempo nenhum

0:03:59.575,0:04:01.895
Felizmente, isso acontece raramente.

0:04:02.130,0:04:05.391
É por isso que a Ordenação Rápida[br]é uma das estratégias mais eficazes

0:04:05.391,0:04:07.506
usadas hoje pelos programadores.

0:04:07.506,0:04:10.974
Usam-na para ordenar, por preço,[br]os artigos numa loja online

0:04:10.974,0:04:13.712
ou para criar uma lista de todas[br]as estações de gasolina

0:04:13.712,0:04:15.388
perto de uma dada localidade

0:04:15.388,0:04:16.760
ordenadas pela distância.

0:04:16.760,0:04:20.534
No teu caso, fizeste uma ordenação rápida,[br]com tempo de sobra.

0:04:20.534,0:04:23.220
Mais um dia de sobressalto na biblioteca