WEBVTT

00:00:06.551 --> 00:00:08.947
Você trabalha na biblioteca da faculdade.

00:00:08.947 --> 00:00:11.397
Bem no meio de uma tarde tranquila,

00:00:11.397 --> 00:00:17.031
de repente, chega um carregamento
com 1.280 livros diferentes.

00:00:17.681 --> 00:00:21.030
Os livros foram deixados numa linha reta,

00:00:21.350 --> 00:00:22.858
mas estão todos fora da ordem,

00:00:22.858 --> 00:00:26.271
e o sistema de seleção
automática está quebrado.

00:00:26.741 --> 00:00:29.667
Para piorar as coisas, 
as aulas começam amanhã,

00:00:29.667 --> 00:00:32.005
o que significa que logo de manhã cedinho

00:00:32.005 --> 00:00:35.747
vai aparecer um monte de estudantes
procurando por esses livros.

00:00:36.307 --> 00:00:38.753
Como você vai conseguir
organizá-los a tempo?

00:00:39.083 --> 00:00:44.199
Um jeito seria começar numa extremidade
da linha, com os dois primeiros livros.

00:00:44.479 --> 00:00:48.346
Se os dois primeiros livros estiverem
na ordem, então deixe-os onde estão.

00:00:48.426 --> 00:00:50.570
Caso contrário, troque-os entre si.

00:00:50.740 --> 00:00:53.216
Depois, olhe o segundo e o terceiro livro,

00:00:53.216 --> 00:00:54.879
repita o processo,

00:00:54.879 --> 00:00:57.415
e continue até chegar ao final da linha.

00:00:57.735 --> 00:01:01.185
A uma certa altura, você vai chegar
ao livro que deveria ser o último.

00:01:01.185 --> 00:01:04.480
Continue trocando-o de lugar
com os livros subsequentes,

00:01:04.550 --> 00:01:08.450
passando-o de livro em livro até chegar
ao fim da linha, onde é o lugar dele.

00:01:08.930 --> 00:01:12.225
A seguir, comece do início
e repita todo o processo

00:01:12.225 --> 00:01:15.510
para colocar do segundo
ao penúltimo livro nos lugares certos,

00:01:15.510 --> 00:01:18.401
e continue até que todos os livros
estejam organizados.

00:01:18.461 --> 00:01:21.422
Essa abordagem se chama "método da bolha".

00:01:21.682 --> 00:01:23.716
É simples, porém lento.

00:01:23.836 --> 00:01:28.931
Você teria de fazer 1.279 comparações
na primeira rodada,

00:01:29.121 --> 00:01:33.323
depois, 1.278, e assim por diante,

00:01:33.323 --> 00:01:38.042
chegando a 818.560 comparações.

00:01:38.542 --> 00:01:43.903
Se cada uma levar apenas um segundo,
o processo todo levará mais de nove dias.

00:01:44.273 --> 00:01:48.249
Uma segunda estratégia seria começar
ordenando apenas os dois primeiros livros.

00:01:48.569 --> 00:01:53.063
Depois, pegar o terceiro e comparar
com o livro na segunda posição.

00:01:53.323 --> 00:01:56.943
Se ele estiver na frente do segundo
livro, então troque os dois,

00:01:56.943 --> 00:01:59.641
depois compare-o com o livro
na primeira posição,

00:01:59.641 --> 00:02:01.682
e troque de novo, se necessário.

00:02:01.682 --> 00:02:03.880
Agora que ordenou
os primeiros três livros,

00:02:03.880 --> 00:02:07.732
continue a adicionar um livro
de cada vez ao subconjunto ordenado,

00:02:07.732 --> 00:02:11.809
comparando e trocando o novo livro
com o que estiver antes dele,

00:02:11.809 --> 00:02:15.714
até estar corretamente colocado
entre os livros ordenados até então.

00:02:15.714 --> 00:02:18.013
Isso se chama "ordenação por inserção".

00:02:18.013 --> 00:02:22.944
Diferente do método bolha, ele em geral
não exige que se compare cada par.

00:02:22.944 --> 00:02:26.954
Em média, espera-se ser necessário
comparar cada livro somente

00:02:26.954 --> 00:02:29.414
com a metade dos livros
que vieram antes dele.

00:02:29.414 --> 00:02:32.123
Nesse caso, o número total de comparações

00:02:32.123 --> 00:02:37.313
seria de 409.280,
o que levaria quase 5 dias.

00:02:37.745 --> 00:02:40.624
Você ainda teria comparações
demais a fazer.

00:02:40.624 --> 00:02:42.515
Eis aqui uma ideia melhor.

00:02:42.515 --> 00:02:44.885
Primeiro, pegue um livro qualquer.

00:02:44.885 --> 00:02:49.356
Chame-o de "a divisória"
e compare-o com todos os outros livros.

00:02:49.446 --> 00:02:51.515
Depois, divida a linha,

00:02:51.515 --> 00:02:55.366
colocando todos os livros que vêm
antes da divisória à esquerda desta,

00:02:55.526 --> 00:02:58.295
e todos aqueles que vêm
depois dela, à sua direita.

00:02:58.435 --> 00:03:00.415
Você acabou de economizar um tempão

00:03:00.415 --> 00:03:03.845
ao não ter de comparar
nenhum dos livros da esquerda

00:03:03.845 --> 00:03:07.025
com nenhum dos livros da direita.

00:03:07.245 --> 00:03:09.665
Bem, olhando agora apenas
os livros da esquerda,

00:03:09.665 --> 00:03:12.542
você pode, de novo, eleger
um "livro divisória" qualquer

00:03:12.542 --> 00:03:17.016
e separar os livros que vêm antes
dele daqueles que vêm depois.

00:03:17.166 --> 00:03:19.736
Continue a criar subdivisões assim

00:03:19.736 --> 00:03:22.384
até ter um monte de subconjuntos,

00:03:22.384 --> 00:03:27.504
que você ordenará rapidamente usando
outra estratégia: ordenação por inserção.

00:03:27.574 --> 00:03:32.926
Cada rodada de divisão dessa
requer cerca de 1.280 comparações.

00:03:33.356 --> 00:03:35.466
Se suas divisões forem bem equilibradas,

00:03:35.466 --> 00:03:41.256
dividir os livros em 128 subconjuntos
de 10 levaria cerca de 7 rodadas,

00:03:41.256 --> 00:03:43.947
ou 8.960 segundos.

00:03:44.097 --> 00:03:48.326
Ordenar esses subconjuntos adicionaria
cerca de 22 segundos para cada um.

00:03:48.516 --> 00:03:51.817
No final das contas, esse método,
conhecido como Quicksort,

00:03:51.817 --> 00:03:54.503
poderia ordenar livros
em menos de três a quatro horas.

00:03:54.503 --> 00:03:55.717
Mas tem um porém.

00:03:55.717 --> 00:03:59.575
Se as divisões ficarem desproporcionais,
não haverá nenhuma economia de tempo.

00:03:59.575 --> 00:04:01.477
Felizmente, isso raramente acontece.

00:04:01.477 --> 00:04:05.000
E essa é a razão por que o Quicksort
é uma das estratégias mais eficientes

00:04:05.000 --> 00:04:06.916
usadas por programadores hoje em dia.

00:04:06.916 --> 00:04:10.847
Eles a usam para coisas como ordenar
itens por preço numa loja on-line,

00:04:10.847 --> 00:04:14.858
ou criar uma lista dos postos de gasolina
perto de um determinado lugar,

00:04:14.858 --> 00:04:16.379
de acordo com a distância.

00:04:16.379 --> 00:04:20.407
No seu caso, você terminou
o "quick sorting" com tempo de sobra.

00:04:20.407 --> 00:04:22.938
E lá se vai mais um dia
eletrizante na biblioteca.