Ordenação visual: bolha, seleção, inserção e intercalação passo a passo
ComputaçãoAlgoritmos e resolução de problemasIdades 13–14
Carregando…
Entre para usarUma sequência de números é desenhada como barras; escolha a ordenação por bolha (bubble sort), por seleção, por inserção ou por intercalação (merge sort) e aperte Passo ou Executar. Cada passo destaca o par sendo comparado, o par sendo trocado e a parte já ordenada, enquanto conta as comparações e as trocas; a linha correspondente do pseudocódigo também fica destacada. A intercalação divide as barras ao meio nível a nível e as junta de volta, e uma tabela e um gráfico comparam as comparações dos quatro algoritmos (n log n contra n²). Os alunos podem arrastar uma barra para mudar seu valor antes de executar.
Aula: Algoritmos de ordenação (bolha, seleção, inserção, intercalação), laços aninhados e dividir para conquistar
O que mostra
A ordenação por bolha, por seleção e por inserção usam laços aninhados, então com n elementos precisam de cerca de n²/2 comparações no pior caso. A seleção faz no máximo n − 1 trocas, a bolha pode parar após uma passada sem trocas e a inserção é muito rápida com dados quase ordenados. A ordenação por intercalação usa dividir para conquistar: parte a lista ao meio repetidamente até sobrarem elementos isolados e depois intercala as metades ordenadas. Seus cerca de log₂n níveis custam no máximo n comparações cada, então ela precisa de aproximadamente n·log₂n comparações, bem menos que n²/2 quando n é grande.
Como usar
Comece com cerca de 8 elementos e clique em Passo; peça aos alunos que prevejam cada comparação destacada acompanhando a linha de pseudocódigo. Clique em Executar e anote comparações e trocas; depois troque o Algoritmo e repita com as opções Decrescente e Quase ordenada. Escolha Ordenação por intercalação para ver as barras se dividirem nível a nível e se juntarem de volta; a tabela e o gráfico abaixo passam a mesma sequência pelos quatro algoritmos. Você também pode arrastar uma barra antes de executar.
Parâmetros que você pode mudar
- Número de elementos 4–30
- Algoritmo Ordenação por bolha, Ordenação por seleção, Ordenação por inserção, Ordenação por intercalação
- Sequência inicial Aleatória, Decrescente (pior caso), Quase ordenada
- Velocidade de execução 1–20 passos/s
- Mostrar a comparação dos quatro algoritmos
Perguntas para explorar
- Depois da primeira passada da ordenação por bolha, qual elemento com certeza já está na posição final?
- Qual algoritmo faz menos trocas em uma sequência decrescente, e por quê?
- Por que a ordenação por inserção termina tão rápido em uma sequência quase ordenada?
