Esteira da Ordenação
Caixas de alturas diferentes em três esteiras: bolha, seleção e inserção ordenam lado a lado, contando comparações e trocas. Aposte qual algoritmo faz menos operações.
Como usar
As esteiras: as três esteiras recebem as mesmas caixas, na mesma ordem. Cada uma é ordenada por um algoritmo diferente, da caixa mais baixa para a mais alta: bolha (compara vizinhas e troca se estiverem fora de ordem), seleção (procura a menor e leva para o começo) e inserção (pega a próxima caixa e encaixa no lugar certo entre as que já passaram).
As cores: amarelo é uma comparação acontecendo, vermelho é uma troca, rosa é a menor caixa encontrada até agora na seleção e verde é a caixa que já está no lugar final. Cada esteira conta quantas comparações e quantas trocas fez.
Experimente: escolha a ordem inicial, faça sua aposta e use “Passo” para ir devagar ou “Rodar” para ver a corrida. As três esteiras andam no mesmo ritmo: uma comparação ou uma troca por vez. Quem faz menos operações termina primeiro.
Arraste o fundo da cena para girar; use a roda do mouse ou dois dedos para aproximar. Pelo teclado: Tab até a cena, setas giram e as teclas + e − aproximam. Todos os comandos também estão nos botões, e a tabela abaixo da cena mostra os mesmos números.
| Algoritmo | Comparações | Trocas | Situação |
|---|
Caixas
Sua aposta
- comparando
- trocando
- menor até agora (seleção)
- no lugar final
Desafios
- Aposte antes de começar qual algoritmo fará menos comparações e acerte.
- Rode a ordem invertida até o fim e descubra qual algoritmo fez mais trocas.
- Encontre uma ordem inicial em que a seleção faz mais que o dobro das comparações da inserção.
- Termine 3 corridas com ordens diferentes e compare as trocas da bolha e da inserção. O que se repete?
Para o professor
O que está por trás: ordenar é a operação clássica sobre listas, e contar comparações e trocas é a forma mais simples de medir o custo de um algoritmo sem cronômetro. Com n caixas, a seleção sempre faz n(n − 1)/2 comparações (28 para 8 caixas), esteja a lista bagunçada ou não, mas faz no máximo n − 1 trocas. A bolha e a inserção fazem exatamente o mesmo número de trocas: cada troca entre vizinhas desfaz um par fora de ordem (uma “inversão”), e as duas só trocam vizinhas. A diferença está nas comparações: a inserção para de comparar assim que encontra o lugar da caixa, por isso brilha em listas quase ordenadas (com a lista já em ordem, faz só n − 1 comparações). A bolha desta página para quando passa pela lista inteira sem trocar nada, que é a versão mais comum nos livros.
Metodologia sugerida: ordenação desplugada antes da tela. Em trios, os alunos ordenam 8 cartas numeradas com cada algoritmo: um executa, outro conta comparações e outro conta trocas. Depois abrem a página, conferem as contagens com a mesma ordem inicial (anotem a semente) e fazem as apostas.
- Por que a seleção faz sempre o mesmo número de comparações, mesmo quando a lista já está em ordem?
- Na ordem invertida, a bolha e a inserção fazem quantas trocas? Tente achar uma fórmula para n caixas.
- Se trocar uma caixa custasse muito mais que comparar (caixas pesadas de verdade, numa fábrica), qual algoritmo vocês escolheriam? E se comparar fosse o caro?
- Um aplicativo recebe todo dia uma lista que já chega quase em ordem. Qual algoritmo combina com essa situação?
Para a aula completa, use o plano Listas, recursão e algoritmos de ordenação; a ficha Ordenar e buscar com cartões leva a atividade para o papel, e a Estante da Busca Binária mostra para que serve uma lista ordenada.
Habilidades: EF08CO02 e EF08CO03. Material concreto equivalente: 8 caixas ou garrafas de alturas diferentes em fila sobre a mesa, ou cartas de baralho, com dois alunos anotando as contagens na lousa.