1
00:00:06,947 --> 00:00:09,277
Trabalhas na biblioteca da faculdade.

2
00:00:09,277 --> 00:00:11,660
Estás no meio de uma tarde tranquila

3
00:00:11,660 --> 00:00:17,311
quando, subitamente, chega um carregamento
de 1280 livros diferentes.

4
00:00:18,560 --> 00:00:21,108
Os livros foram descarregados
numa longa linha reta

5
00:00:21,690 --> 00:00:23,433
mas estão todos fora de ordem,

6
00:00:23,433 --> 00:00:26,485
e o sistema de classificação
está avariado.

7
00:00:27,031 --> 00:00:29,757
Para piorar as coisas,
as aulas começam amanhã

8
00:00:29,757 --> 00:00:32,500
o que significa que,
logo de manhã cedo,

9
00:00:32,500 --> 00:00:35,947
todos os estudantes vão aparecer
à procura desses livros.

10
00:00:36,557 --> 00:00:38,965
Como é que podes ordenar
todos os livros a tempo?

11
00:00:39,493 --> 00:00:42,788
Uma forma seria começar
pelos dois primeiros livros,

12
00:00:42,788 --> 00:00:44,669
num dos extremos da fila.

13
00:00:44,779 --> 00:00:48,626
Se os dois primeiros livros estiverem
por ordem, deixa-os ficar onde eles estão.

14
00:00:48,626 --> 00:00:50,920
Caso contrário, troca-os de lugar.

15
00:00:50,920 --> 00:00:53,297
Depois, observa o segundo
e o terceiro livros.

16
00:00:53,297 --> 00:00:54,969
e repete o procedimento.

17
00:00:55,510 --> 00:00:58,035
Continua até chegares ao fim da fila.

18
00:00:58,035 --> 00:01:01,185
A certa altura, encontras o livro
que devia ser o último.


19
00:01:01,185 --> 00:01:04,810
Vai-o trocando sempre de lugar
com os livros posteriores,

20
00:01:04,810 --> 00:01:08,898
até ele chegar ao fim da fila,
ao lugar que lhe pertence.

21
00:01:09,316 --> 00:01:12,406
Volta a começar do princípio
e repete o procedimento.

22
00:01:12,406 --> 00:01:15,437
até colocar o penúltimo livro
no seu devido lugar.

23
00:01:15,510 --> 00:01:18,875
Volta a repetir tudo até todos os livros
estarem nos seus lugares.

24
00:01:18,875 --> 00:01:21,862
Este método chama-se 
"Ordenação por Flutuação".

25
00:01:21,862 --> 00:01:24,156
É simples, mas lento.

26
00:01:24,156 --> 00:01:28,912
Tens que fazer 1279 comparações
na primeira ronda,

27
00:01:29,331 --> 00:01:33,486
depois, 1278, e assim sucessivamente,

28
00:01:33,632 --> 00:01:38,510
num total de 818 560 comparações.

29
00:01:38,542 --> 00:01:43,700
Se cada uma delas demorar só um segundo,
o processo demorará nove dias.

30
00:01:44,273 --> 00:01:48,569
Uma segunda estratégia seria começar
por ordenar os dois primeiros livros.

31
00:01:48,723 --> 00:01:53,533
Depois, comparar o terceiro livro
com o livro no segundo lugar.

32
00:01:53,733 --> 00:01:57,173
Se ele deve ficar antes do segundo livro,
troca-os de lugar.

33
00:01:57,173 --> 00:01:59,641
Depois compara-o com o livro
no primeiro lugar

34
00:01:59,641 --> 00:02:01,682
e troca-os, se necessário.

35
00:02:01,682 --> 00:02:03,880
Tens os três primeiros livros
ordenados.

36
00:02:04,180 --> 00:02:07,950
Continua com um livro de cada vez


37
00:02:07,950 --> 00:02:11,809
comparando e trocando o novo livro
com os que estão antes dele

38
00:02:11,809 --> 00:02:15,858
até ele ficar corretamente colocado
entre os livros ordenados até aí.

39
00:02:16,004 --> 00:02:18,284
Este método chama-se
"Ordenação por Inserção".

40
00:02:18,284 --> 00:02:20,434
Ao contrário da "Ordenação por Flutuação"

41
00:02:20,434 --> 00:02:23,552
não exige que se comparem
todos os pares de livros.

42
00:02:23,552 --> 00:02:26,990
Em média, só precisamos
de comparar cada livro

43
00:02:26,990 --> 00:02:29,550
com metade dos livros
que estão antes dele.

44
00:02:29,550 --> 00:02:32,359
Neste caso, o número total de comparações

45
00:02:32,359 --> 00:02:35,983
seria de 409 280,

46
00:02:35,983 --> 00:02:37,953
o que levaria quase cinco dias.

47
00:02:38,135 --> 00:02:40,733
Continuas a ter que fazer
demasiadas comparações.

48
00:02:40,733 --> 00:02:42,642
Esta é uma ideia melhor.

49
00:02:42,642 --> 00:02:44,885
Primeiro, agarra num livro ao acaso.

50
00:02:45,112 --> 00:02:49,115
Chama-lhe "partição" e compara-o
com o outros livros todos.

51
00:02:49,606 --> 00:02:51,587
Depois divide a fila

52
00:02:51,587 --> 00:02:55,666
colocando à esquerda todos os livros
que devem ficar antes da partição

53
00:02:55,666 --> 00:02:58,825
e à direita, os que devem ficar
depois da partição.

54
00:02:58,825 --> 00:03:00,615
Poupaste imenso tempo

55
00:03:00,615 --> 00:03:03,917
porque não precisas de comparar
nenhum dos livros da esquerda

56
00:03:03,917 --> 00:03:06,235
com os da direita.

57
00:03:07,245 --> 00:03:09,665
Depois, olha só
para os livros da esquerda.

58
00:03:09,783 --> 00:03:12,769
Podes voltar a agarrar num livro
ao acaso, outra "partição"

59
00:03:12,769 --> 00:03:17,266
e separar os livros antes dela
dos livros depois dela.

60
00:03:17,266 --> 00:03:19,736
Podes continuar a criar subpartições
como estas

61
00:03:19,736 --> 00:03:22,484
até teres um grupo de pequenas sublinhas,

62
00:03:22,484 --> 00:03:24,900
cada uma das quais
podes ordenar rapidamente,

63
00:03:24,900 --> 00:03:27,809
usando outra estratégia
como a "Ordenação por Inserção".

64
00:03:27,809 --> 00:03:32,662
Cada ronda de partição exige
cerca de 1280 comparações.

65
00:03:33,298 --> 00:03:35,647
Se as partições estiverem equilibradas,

66
00:03:35,647 --> 00:03:41,301
dividir os livros em 128 sublinhas de 10,
deve precisar de sete rondas,

67
00:03:41,301 --> 00:03:43,947
ou seja 8960 segundos.

68
00:03:44,256 --> 00:03:48,172
Ordenar as sublinhas, 
demorará mais 22 segundos cada.

69
00:03:48,736 --> 00:03:51,989
Ao todo, este método,
conhecido por "Ordenação Rápida"

70
00:03:51,989 --> 00:03:54,773
pode ordenar os livros
em menos de três horas e meia.

71
00:03:54,773 --> 00:03:56,242
Mas há um inconveniente.

72
00:03:56,242 --> 00:03:59,456
As partições podem ficar desequilibradas,
e não poupar tempo nenhum

73
00:03:59,575 --> 00:04:01,895
Felizmente, isso acontece raramente.

74
00:04:02,130 --> 00:04:05,391
É por isso que a Ordenação Rápida
é uma das estratégias mais eficazes

75
00:04:05,391 --> 00:04:07,506
usadas hoje pelos programadores.

76
00:04:07,506 --> 00:04:10,974
Usam-na para ordenar, por preço,
os artigos numa loja online

77
00:04:10,974 --> 00:04:13,712
ou para criar uma lista de todas
as estações de gasolina

78
00:04:13,712 --> 00:04:15,388
perto de uma dada localidade

79
00:04:15,388 --> 00:04:16,760
ordenadas pela distância.

80
00:04:16,760 --> 00:04:20,534
No teu caso, fizeste uma ordenação rápida,
com tempo de sobra.

81
00:04:20,534 --> 00:04:23,220
Mais um dia de sobressalto na biblioteca