Qual a maneira mais rápida de ordenar alfabeticamente a biblioteca? — Chand John
-
0:07 - 0:09Trabalhas na biblioteca da faculdade.
-
0:09 - 0:12Estás no meio de uma tarde tranquila
-
0:12 - 0:17quando, subitamente, chega um carregamento
de 1280 livros diferentes. -
0:19 - 0:21Os livros foram descarregados
numa longa linha reta -
0:22 - 0:23mas estão todos fora de ordem,
-
0:23 - 0:26e o sistema de classificação
está avariado. -
0:27 - 0:30Para piorar as coisas,
as aulas começam amanhã -
0:30 - 0:32o que significa que,
logo de manhã cedo, -
0:32 - 0:36todos os estudantes vão aparecer
à procura desses livros. -
0:37 - 0:39Como é que podes ordenar
todos os livros a tempo? -
0:39 - 0:43Uma forma seria começar
pelos dois primeiros livros, -
0:43 - 0:45num dos extremos da fila.
-
0:45 - 0:49Se os dois primeiros livros estiverem
por ordem, deixa-os ficar onde eles estão. -
0:49 - 0:51Caso contrário, troca-os de lugar.
-
0:51 - 0:53Depois, observa o segundo
e o terceiro livros. -
0:53 - 0:55e repete o procedimento.
-
0:56 - 0:58Continua até chegares ao fim da fila.
-
0:58 - 1:01A certa altura, encontras o livro
que devia ser o último. -
1:01 - 1:05Vai-o trocando sempre de lugar
com os livros posteriores, -
1:05 - 1:09até ele chegar ao fim da fila,
ao lugar que lhe pertence. -
1:09 - 1:12Volta a começar do princípio
e repete o procedimento. -
1:12 - 1:15até colocar o penúltimo livro
no seu devido lugar. -
1:16 - 1:19Volta a repetir tudo até todos os livros
estarem nos seus lugares. -
1:19 - 1:22Este método chama-se
"Ordenação por Flutuação". -
1:22 - 1:24É simples, mas lento.
-
1:24 - 1:29Tens que fazer 1279 comparações
na primeira ronda, -
1:29 - 1:33depois, 1278, e assim sucessivamente,
-
1:34 - 1:39num total de 818 560 comparações.
-
1:39 - 1:44Se cada uma delas demorar só um segundo,
o processo demorará nove dias. -
1:44 - 1:49Uma segunda estratégia seria começar
por ordenar os dois primeiros livros. -
1:49 - 1:54Depois, comparar o terceiro livro
com o livro no segundo lugar. -
1:54 - 1:57Se ele deve ficar antes do segundo livro,
troca-os de lugar. -
1:57 - 2:00Depois compara-o com o livro
no primeiro lugar -
2:00 - 2:02e troca-os, se necessário.
-
2:02 - 2:04Tens os três primeiros livros
ordenados. -
2:04 - 2:08Continua com um livro de cada vez
-
2:08 - 2:12comparando e trocando o novo livro
com os que estão antes dele -
2:12 - 2:16até ele ficar corretamente colocado
entre os livros ordenados até aí. -
2:16 - 2:18Este método chama-se
"Ordenação por Inserção". -
2:18 - 2:20Ao contrário da "Ordenação por Flutuação"
-
2:20 - 2:24não exige que se comparem
todos os pares de livros. -
2:24 - 2:27Em média, só precisamos
de comparar cada livro -
2:27 - 2:30com metade dos livros
que estão antes dele. -
2:30 - 2:32Neste caso, o número total de comparações
-
2:32 - 2:36seria de 409 280,
-
2:36 - 2:38o que levaria quase cinco dias.
-
2:38 - 2:41Continuas a ter que fazer
demasiadas comparações. -
2:41 - 2:43Esta é uma ideia melhor.
-
2:43 - 2:45Primeiro, agarra num livro ao acaso.
-
2:45 - 2:49Chama-lhe "partição" e compara-o
com o outros livros todos. -
2:50 - 2:52Depois divide a fila
-
2:52 - 2:56colocando à esquerda todos os livros
que devem ficar antes da partição -
2:56 - 2:59e à direita, os que devem ficar
depois da partição. -
2:59 - 3:01Poupaste imenso tempo
-
3:01 - 3:04porque não precisas de comparar
nenhum dos livros da esquerda -
3:04 - 3:06com os da direita.
-
3:07 - 3:10Depois, olha só
para os livros da esquerda. -
3:10 - 3:13Podes voltar a agarrar num livro
ao acaso, outra "partição" -
3:13 - 3:17e separar os livros antes dela
dos livros depois dela. -
3:17 - 3:20Podes continuar a criar subpartições
como estas -
3:20 - 3:22até teres um grupo de pequenas sublinhas,
-
3:22 - 3:25cada uma das quais
podes ordenar rapidamente, -
3:25 - 3:28usando outra estratégia
como a "Ordenação por Inserção". -
3:28 - 3:33Cada ronda de partição exige
cerca de 1280 comparações. -
3:33 - 3:36Se as partições estiverem equilibradas,
-
3:36 - 3:41dividir os livros em 128 sublinhas de 10,
deve precisar de sete rondas, -
3:41 - 3:44ou seja 8960 segundos.
-
3:44 - 3:48Ordenar as sublinhas,
demorará mais 22 segundos cada. -
3:49 - 3:52Ao todo, este método,
conhecido por "Ordenação Rápida" -
3:52 - 3:55pode ordenar os livros
em menos de três horas e meia. -
3:55 - 3:56Mas há um inconveniente.
-
3:56 - 3:59As partições podem ficar desequilibradas,
e não poupar tempo nenhum -
4:00 - 4:02Felizmente, isso acontece raramente.
-
4:02 - 4:05É por isso que a Ordenação Rápida
é uma das estratégias mais eficazes -
4:05 - 4:08usadas hoje pelos programadores.
-
4:08 - 4:11Usam-na para ordenar, por preço,
os artigos numa loja online -
4:11 - 4:14ou para criar uma lista de todas
as estações de gasolina -
4:14 - 4:15perto de uma dada localidade
-
4:15 - 4:17ordenadas pela distância.
-
4:17 - 4:21No teu caso, fizeste uma ordenação rápida,
com tempo de sobra. -
4:21 - 4:23Mais um dia de sobressalto na biblioteca
- Title:
- Qual a maneira mais rápida de ordenar alfabeticamente a biblioteca? — Chand John
- Speaker:
- Chand John
- Description:
-
Vejam a lição completa: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john
Trabalhas na biblioteca da faculdade. Estás no meio de uma tarde tranquila quando, subitamente, chega um carregamento de 1280 de 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. Como podes ordenar os livros rapidamente? Chand John mostra como é possível, lançando luz em como os algoritmos ajudam bibliotecários e motores de busca a ordenar rapidamente informações.
- Video Language:
- English
- Team:
- closed TED
- Project:
- TED-Ed
- Duration:
- 04:39
Margarida Ferreira approved Portuguese subtitles for What's the fastest way to alphabetize your bookshelf? | ||
António Ribeiro accepted Portuguese subtitles for What's the fastest way to alphabetize your bookshelf? | ||
António Ribeiro edited Portuguese subtitles for What's the fastest way to alphabetize your bookshelf? | ||
Margarida Ferreira edited Portuguese subtitles for What's the fastest way to alphabetize your bookshelf? | ||
Margarida Ferreira edited Portuguese subtitles for What's the fastest way to alphabetize your bookshelf? |