[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:06.95,0:00:09.28,Default,,0000,0000,0000,,Trabalhas na biblioteca da faculdade.
Dialogue: 0,0:00:09.28,0:00:11.66,Default,,0000,0000,0000,,Estás no meio de uma tarde tranquila
Dialogue: 0,0:00:11.66,0:00:17.31,Default,,0000,0000,0000,,quando, subitamente, chega um carregamento\Nde 1280 livros diferentes.
Dialogue: 0,0:00:18.56,0:00:21.11,Default,,0000,0000,0000,,Os livros foram descarregados\Nnuma longa linha reta
Dialogue: 0,0:00:21.69,0:00:23.43,Default,,0000,0000,0000,,mas estão todos fora de ordem,
Dialogue: 0,0:00:23.43,0:00:26.48,Default,,0000,0000,0000,,e o sistema de classificação\Nestá avariado.
Dialogue: 0,0:00:27.03,0:00:29.76,Default,,0000,0000,0000,,Para piorar as coisas,\Nas aulas começam amanhã
Dialogue: 0,0:00:29.76,0:00:32.50,Default,,0000,0000,0000,,o que significa que,\Nlogo de manhã cedo,
Dialogue: 0,0:00:32.50,0:00:35.95,Default,,0000,0000,0000,,todos os estudantes vão aparecer\Nà procura desses livros.
Dialogue: 0,0:00:36.56,0:00:38.96,Default,,0000,0000,0000,,Como é que podes ordenar\Ntodos os livros a tempo?
Dialogue: 0,0:00:39.49,0:00:42.79,Default,,0000,0000,0000,,Uma forma seria começar\Npelos dois primeiros livros,
Dialogue: 0,0:00:42.79,0:00:44.67,Default,,0000,0000,0000,,num dos extremos da fila.
Dialogue: 0,0:00:44.78,0:00:48.63,Default,,0000,0000,0000,,Se os dois primeiros livros estiverem\Npor ordem, deixa-os ficar onde eles estão.
Dialogue: 0,0:00:48.63,0:00:50.92,Default,,0000,0000,0000,,Caso contrário, troca-os de lugar.
Dialogue: 0,0:00:50.92,0:00:53.30,Default,,0000,0000,0000,,Depois, observa o segundo\Ne o terceiro livros.
Dialogue: 0,0:00:53.30,0:00:54.97,Default,,0000,0000,0000,,e repete o procedimento.
Dialogue: 0,0:00:55.51,0:00:58.04,Default,,0000,0000,0000,,Continua até chegares ao fim da fila.
Dialogue: 0,0:00:58.04,0:01:01.18,Default,,0000,0000,0000,,A certa altura, encontras o livro\Nque devia ser o último.\N
Dialogue: 0,0:01:01.18,0:01:04.81,Default,,0000,0000,0000,,Vai-o trocando sempre de lugar\Ncom os livros posteriores,
Dialogue: 0,0:01:04.81,0:01:08.90,Default,,0000,0000,0000,,até ele chegar ao fim da fila,\Nao lugar que lhe pertence.
Dialogue: 0,0:01:09.32,0:01:12.41,Default,,0000,0000,0000,,Volta a começar do princípio\Ne repete o procedimento.
Dialogue: 0,0:01:12.41,0:01:15.44,Default,,0000,0000,0000,,até colocar o penúltimo livro\Nno seu devido lugar.
Dialogue: 0,0:01:15.51,0:01:18.88,Default,,0000,0000,0000,,Volta a repetir tudo até todos os livros\Nestarem nos seus lugares.
Dialogue: 0,0:01:18.88,0:01:21.86,Default,,0000,0000,0000,,Este método chama-se \N"Ordenação por Flutuação".
Dialogue: 0,0:01:21.86,0:01:24.16,Default,,0000,0000,0000,,É simples, mas lento.
Dialogue: 0,0:01:24.16,0:01:28.91,Default,,0000,0000,0000,,Tens que fazer 1279 comparações\Nna primeira ronda,
Dialogue: 0,0:01:29.33,0:01:33.49,Default,,0000,0000,0000,,depois, 1278, e assim sucessivamente,
Dialogue: 0,0:01:33.63,0:01:38.51,Default,,0000,0000,0000,,num total de 818 560 comparações.
Dialogue: 0,0:01:38.54,0:01:43.70,Default,,0000,0000,0000,,Se cada uma delas demorar só um segundo,\No processo demorará nove dias.
Dialogue: 0,0:01:44.27,0:01:48.57,Default,,0000,0000,0000,,Uma segunda estratégia seria começar\Npor ordenar os dois primeiros livros.
Dialogue: 0,0:01:48.72,0:01:53.53,Default,,0000,0000,0000,,Depois, comparar o terceiro livro\Ncom o livro no segundo lugar.
Dialogue: 0,0:01:53.73,0:01:57.17,Default,,0000,0000,0000,,Se ele deve ficar antes do segundo livro,\Ntroca-os de lugar.
Dialogue: 0,0:01:57.17,0:01:59.64,Default,,0000,0000,0000,,Depois compara-o com o livro\Nno primeiro lugar
Dialogue: 0,0:01:59.64,0:02:01.68,Default,,0000,0000,0000,,e troca-os, se necessário.
Dialogue: 0,0:02:01.68,0:02:03.88,Default,,0000,0000,0000,,Tens os três primeiros livros\Nordenados.
Dialogue: 0,0:02:04.18,0:02:07.95,Default,,0000,0000,0000,,Continua com um livro de cada vez\N
Dialogue: 0,0:02:07.95,0:02:11.81,Default,,0000,0000,0000,,comparando e trocando o novo livro\Ncom os que estão antes dele
Dialogue: 0,0:02:11.81,0:02:15.86,Default,,0000,0000,0000,,até ele ficar corretamente colocado\Nentre os livros ordenados até aí.
Dialogue: 0,0:02:16.00,0:02:18.28,Default,,0000,0000,0000,,Este método chama-se\N"Ordenação por Inserção".
Dialogue: 0,0:02:18.28,0:02:20.43,Default,,0000,0000,0000,,Ao contrário da "Ordenação por Flutuação"
Dialogue: 0,0:02:20.43,0:02:23.55,Default,,0000,0000,0000,,não exige que se comparem\Ntodos os pares de livros.
Dialogue: 0,0:02:23.55,0:02:26.99,Default,,0000,0000,0000,,Em média, só precisamos\Nde comparar cada livro
Dialogue: 0,0:02:26.99,0:02:29.55,Default,,0000,0000,0000,,com metade dos livros\Nque estão antes dele.
Dialogue: 0,0:02:29.55,0:02:32.36,Default,,0000,0000,0000,,Neste caso, o número total de comparações
Dialogue: 0,0:02:32.36,0:02:35.98,Default,,0000,0000,0000,,seria de 409 280,
Dialogue: 0,0:02:35.98,0:02:37.95,Default,,0000,0000,0000,,o que levaria quase cinco dias.
Dialogue: 0,0:02:38.14,0:02:40.73,Default,,0000,0000,0000,,Continuas a ter que fazer\Ndemasiadas comparações.
Dialogue: 0,0:02:40.73,0:02:42.64,Default,,0000,0000,0000,,Esta é uma ideia melhor.
Dialogue: 0,0:02:42.64,0:02:44.88,Default,,0000,0000,0000,,Primeiro, agarra num livro ao acaso.
Dialogue: 0,0:02:45.11,0:02:49.12,Default,,0000,0000,0000,,Chama-lhe "partição" e compara-o\Ncom o outros livros todos.
Dialogue: 0,0:02:49.61,0:02:51.59,Default,,0000,0000,0000,,Depois divide a fila
Dialogue: 0,0:02:51.59,0:02:55.67,Default,,0000,0000,0000,,colocando à esquerda todos os livros\Nque devem ficar antes da partição
Dialogue: 0,0:02:55.67,0:02:58.82,Default,,0000,0000,0000,,e à direita, os que devem ficar\Ndepois da partição.
Dialogue: 0,0:02:58.82,0:03:00.62,Default,,0000,0000,0000,,Poupaste imenso tempo
Dialogue: 0,0:03:00.62,0:03:03.92,Default,,0000,0000,0000,,porque não precisas de comparar\Nnenhum dos livros da esquerda
Dialogue: 0,0:03:03.92,0:03:06.24,Default,,0000,0000,0000,,com os da direita.
Dialogue: 0,0:03:07.24,0:03:09.66,Default,,0000,0000,0000,,Depois, olha só\Npara os livros da esquerda.
Dialogue: 0,0:03:09.78,0:03:12.77,Default,,0000,0000,0000,,Podes voltar a agarrar num livro\Nao acaso, outra "partição"
Dialogue: 0,0:03:12.77,0:03:17.27,Default,,0000,0000,0000,,e separar os livros antes dela\Ndos livros depois dela.
Dialogue: 0,0:03:17.27,0:03:19.74,Default,,0000,0000,0000,,Podes continuar a criar subpartições\Ncomo estas
Dialogue: 0,0:03:19.74,0:03:22.48,Default,,0000,0000,0000,,até teres um grupo de pequenas sublinhas,
Dialogue: 0,0:03:22.48,0:03:24.90,Default,,0000,0000,0000,,cada uma das quais\Npodes ordenar rapidamente,
Dialogue: 0,0:03:24.90,0:03:27.81,Default,,0000,0000,0000,,usando outra estratégia\Ncomo a "Ordenação por Inserção".
Dialogue: 0,0:03:27.81,0:03:32.66,Default,,0000,0000,0000,,Cada ronda de partição exige\Ncerca de 1280 comparações.
Dialogue: 0,0:03:33.30,0:03:35.65,Default,,0000,0000,0000,,Se as partições estiverem equilibradas,
Dialogue: 0,0:03:35.65,0:03:41.30,Default,,0000,0000,0000,,dividir os livros em 128 sublinhas de 10,\Ndeve precisar de sete rondas,
Dialogue: 0,0:03:41.30,0:03:43.95,Default,,0000,0000,0000,,ou seja 8960 segundos.
Dialogue: 0,0:03:44.26,0:03:48.17,Default,,0000,0000,0000,,Ordenar as sublinhas, \Ndemorará mais 22 segundos cada.
Dialogue: 0,0:03:48.74,0:03:51.99,Default,,0000,0000,0000,,Ao todo, este método,\Nconhecido por "Ordenação Rápida"
Dialogue: 0,0:03:51.99,0:03:54.77,Default,,0000,0000,0000,,pode ordenar os livros\Nem menos de três horas e meia.
Dialogue: 0,0:03:54.77,0:03:56.24,Default,,0000,0000,0000,,Mas há um inconveniente.
Dialogue: 0,0:03:56.24,0:03:59.46,Default,,0000,0000,0000,,As partições podem ficar desequilibradas,\Ne não poupar tempo nenhum
Dialogue: 0,0:03:59.58,0:04:01.90,Default,,0000,0000,0000,,Felizmente, isso acontece raramente.
Dialogue: 0,0:04:02.13,0:04:05.39,Default,,0000,0000,0000,,É por isso que a Ordenação Rápida\Né uma das estratégias mais eficazes
Dialogue: 0,0:04:05.39,0:04:07.51,Default,,0000,0000,0000,,usadas hoje pelos programadores.
Dialogue: 0,0:04:07.51,0:04:10.97,Default,,0000,0000,0000,,Usam-na para ordenar, por preço,\Nos artigos numa loja online
Dialogue: 0,0:04:10.97,0:04:13.71,Default,,0000,0000,0000,,ou para criar uma lista de todas\Nas estações de gasolina
Dialogue: 0,0:04:13.71,0:04:15.39,Default,,0000,0000,0000,,perto de uma dada localidade
Dialogue: 0,0:04:15.39,0:04:16.76,Default,,0000,0000,0000,,ordenadas pela distância.
Dialogue: 0,0:04:16.76,0:04:20.53,Default,,0000,0000,0000,,No teu caso, fizeste uma ordenação rápida,\Ncom tempo de sobra.
Dialogue: 0,0:04:20.53,0:04:23.22,Default,,0000,0000,0000,,Mais um dia de sobressalto na biblioteca