Nome:Turma:Data:
Computação · 8º ano · Algoritmos clássicos

Ordenar e buscar com cartões

BNCC: EF08CO03 Utilizar algoritmos clássicos de manipulação sobre listas.

Para ordenar, a ordenação por seleção acha o menor item e troca com o primeiro, depois acha o menor do resto e troca com o segundo, e assim por diante. Para buscar numa lista ordenada, a busca binária olha o meio e descarta metade a cada pergunta.

1. Ordenação por seleção

Recorte os cartões, coloque na ordem abaixo e ordene. Anote a lista depois de cada passo e se houve troca.

83617254
PassoLista depois do passoHouve troca?
início8 3 6 1 7 2 5 4—
1
2
3
4
5
6
7

Total de trocas: ______

2. Busca binária

Na lista ordenada, procure o número 7 pela busca binária. Anote cada pergunta.

PerguntaItem do meioÉ o 7? Maior ou menor?Parte que sobra

Quantas perguntas a busca binária fez? ____   E a busca linear (do começo ao fim)? ____

3. Quanto mais itens...

Itens na lista8161.0001.000.000
Máximo de perguntas da busca binária3
Gabarito e orientações para o professor

Condução (40 min): faça primeiro com oito estudantes em fila segurando os cartões, contando as trocas em voz alta. Depois cada dupla repete com os cartões recortados.

Gabarito. 1) Passo 1: 1 3 6 8 7 2 5 4 (troca); 2: 1 2 6 8 7 3 5 4 (troca); 3: 1 2 3 8 7 6 5 4 (troca); 4: 1 2 3 4 7 6 5 8 (troca); 5: 1 2 3 4 5 6 7 8 (troca); 6 e 7: sem troca. Total: 5 trocas. 2) Lista 1 a 8: meio na posição 3 (o 4), 7 é maior, sobra 5 6 7 8; meio o 6, 7 é maior, sobra 7 8; meio o 7, achou. 3 perguntas pela busca binária e 7 pela linear. 3) 16: 4; 1.000: 10; 1.000.000: 20 (cada pergunta divide a lista ao meio; 2¹⁰ = 1.024 e 2²⁰ passa de um milhão).

Use junto com: 📋 Listas, recursão e algoritmos de ordenação