Atividade 7: O mais leve e o mais pesado — Algoritmos de Ordenação

Apresentação

Os computadores são muitas vezes utilizados para colocar listas em algum tipo de ordem, por exemplo, nomes em ordem alfabética, compromissos ou e-mails por data, ou itens em ordem numérica. Classificar listas nos ajuda a encontrar as coisas rapidamente, e também facilita a identificação dos valores extremos. Se você classificar as notas de uma prova em ordem numérica, a nota mais baixa e a mais alta tornam-se evidentes.

Se você usar o método errado, pode demorar muito tempo para ordenar uma lista grande, mesmo em um computador rápido. Felizmente, vários métodos rápidos de ordenação são conhecidos. Nesta atividade, as crianças descobrirão métodos diferentes para ordenação e verão como um método inteligente pode executar a tarefa muito mais rapidamente do que um método simples.

Disciplinas e conteúdos relacionados

• Matemática: comparação e ordenação;

• Computação: ordenação, algoritmo e eficiência;

Habilidades

• (EF03MA01) Ler, escrever e comparar números naturais de até a ordem de unidade de milhar, estabelecendo relações entre os registros numéricos e em língua materna;

• (EF04MA01) Ler, escrever e ordenar números naturais até a ordem de dezenas de milhar;

• (EF05MA01) Ler, escrever e ordenar números naturais até a ordem das centenas de milhar com compreensão das principais características do sistema de numeração decimal.

• (EF07MA03) Comparar e ordenar números inteiros em diferentes contextos, incluindo o histórico, associá-los a pontos da reta numérica e utilizá-los em situações que envolvam adição e subtração.

• (EF07MA05) Resolver um mesmo problema utilizando diferentes algoritmos.

Nível de Ensino

• Anos Iniciais e Finais do Ensino Fundamental.

Material

Cada grupo de crianças precisará de:

• Um conjunto de 8 recipientes do mesmo tamanho, mas de pesos diferentes (ex: caixas de leite ou garrafas com areia ou água);

• Uma balança de braço (uma daquelas balanças antigas que não mede o peso dos objetos, mas sim compara o peso dos objetos em cada um dos braços);

• Folhas de atividades disponibilizadas abaixo.

O mais leve e o mais pesado

Discussão

Frequentemente, os computadores devem ordenar listas de coisas. Pense em todas as situações nas quais colocar as coisas em ordem seja importante. O que aconteceria se estas coisas não estivessem em ordem?

Os computadores geralmente comparam apenas dois valores por vez. A atividade seguinte usa essa restrição para dar às crianças uma ideia do que se trata.

Atividade

1. Divida os estudantes em grupos.

2. Cada grupo precisará de cópias das Folhas de Atividade e seus próprios pesos e balança.

3. Peça aos estudantes para fazerem as atividades e, depois, discuta os resultados.

Variações e extensões

Existem diversos métodos de ordenação. Você pode tentar ordenar os pesos através dos seguintes métodos.

A ordenação por inserção remove cada objeto de um grupo desordenado e o insere na sua posição correta em numa lista crescente (veja a figura abaixo). A cada inserção, o grupo de objetos desordenados diminui e a lista ordenada aumenta até que, finalmente, toda a lista esteja ordenada. Jogadores de cartas muitas vezes usam esse método para ordenar as cartas em suas mãos.

A ordenação por borbulhamento ou método da bolha (Bubble sort) percorre a lista diversas vezes trocando quaisquer objetos adjacentes que não estejam na ordem correta. A lista está ordenada assim que não ocorre mais nenhuma troca durante uma passagem pela lista. Este método não é muito eficiente, mas algumas pessoas o consideram mais fácil de compreender do que os outros métodos.

O método de fusão (Mergesort) utiliza a técnica de “dividir e conquistar” para ordenar uma lista de elementos. Primeiro, divide-se a lista aleatoriamente em duas listas de tamanhos iguais (ou quase iguais, se houver um número ímpar de elementos). Cada uma das duas listas é ordenada e, em seguida, as listas são intercaladas entre si. É fácil mesclar duas listas ordenadas: basta retirar repetidamente o menor dos dois elementos que estão no início das duas listas. Na figura abaixo, os pesos de 40 e 60 gramas estão no início das listas. Portanto, o próximo elemento a ser adicionado é o peso de 40 gramas. Como devemos ordenar as listas menores? Simples, basta usar o método de fusão! Todas as listas serão finalmente divididas em elementos individuais. Portanto, não é preciso se perguntar quando parar.

Folhas de Atividades e Materiais Adicionais

Você também pode baixar todas as folhas de atividade e materiais adicionais em formato editável aqui.

Do que se trata tudo isso?

É muito mais fácil encontrar uma informação em uma lista ordenada. Listas telefônicas, dicionários e índices de livros utilizam a ordem alfabética, e a vida seria muito mais difícil se eles não o fizessem. Se uma lista de números (como uma lista de despesas) for ordenada, os pontos extremos são fáceis de ver porque eles estão no começo e no fim da lista. As duplicatas também são fáceis de encontrar porque acabam ficando juntas.

Os computadores gastam muito tempo ordenando as coisas. Portanto, os cientistas da computação devem descobrir métodos rápidos e eficientes para fazer isto. Alguns dos métodos mais lentos tais como a ordenação por inserção, ordenação por seleção e método da bolha podem ser úteis em situações especiais, porém os métodos mais rápidos, a exemplo do quicksort, são geralmente utilizados.

O método quicksort usa um conceito chamado recursão. Isso significa que você permanece dividindo uma lista em partes menores e, em seguida, realiza o mesmo tipo de ordenação em cada uma das partes da lista. Esta abordagem, em particular, é chamada de dividir e conquistar. A lista é dividida repetidamente até que se torne pequena o suficiente para resolver o problema (conquistar). No quicksort, as listas são divididas até que contenham apenas um elemento. É trivial ordenar um elemento! Embora isto pareça muito demorado, na prática, é drasticamente mais rápido do que os outros métodos.

Para saber mais

O experimento Baralho Mágico da coleção Matemática Multimídia usa um procedimento similar ao do quicksort para criar um truque de mágica, desses de adivinhar a carta escolhida. O experimento foi criado para estudantes do Ensino Médio (relacionando a mágica com logaritmos), mas certamente pode ser usado com os Anos Finais do Ensino Fundamental.

Soluções e Dicas

Ordenando pesos

3. A melhor maneira de encontrar o peso mais leve é ir, de objeto em objeto, marcando qual o mais leve até aquele ponto. Ou seja, comparar dois objetos e ficar com o mais leve. Então, compare com outro, ficando com o mais leve da comparação. Repita esse procedimento até ter utilizado todos os objetos.

4. Compare os pesos na balança. Isso pode ser facilmente realizado com três comparações e, às vezes, duas bastam — se os estudantes perceberem que a operação de comparação é transitiva (Isto é, se A é mais leve que B e B é mais leve que C, então A tem de ser mais leve que C).

Desafio:

Esse é um atalho para totalizar o número de comparações da ordenação por seleção.

Para encontrar o menor entre dois objetos, você precisa de uma comparação, três objetos precisam de duas, quatro precisam de três e assim por diante. Ordenar oito objetos com a ordenação por seleção requer sete comparações para encontrar o primeiro, seis para encontrar o próximo, cinco para o próximo e assim sucessivamente. Isso nos fornece:

7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 comparações.

n objetos precisariam de 1 + 2 + 3 + 4 +… + n – 1 comparações para serem ordenados.

Totalizar esses números é fácil se os reagruparmos.

Por exemplo, para somar os números 1 + 2 + 3 + … + 20, os reagrupamos como

(1 + 20) + (2 + 19) + (3 + 18) + (4 + 17) + (5 + 16) + (6 + 15) + (7 + 14) + (8 + 13) + (9 + 12) + (10 + 11)

= 21 × 10

= 210

Em geral, a soma 1 + 2 + 3 + 4 … + n – 1 = n(n – 1)/2.