Esta é uma atividade em grupo que visa encontrar e descrever um receita, ou algoritmo, para realizar uma determinada tarefa, a saber, ordenar (colocar em ordem crescente) uma lista de 8 números.
Nesta atividade utilizamos um computador-a-cartolina, uma cartolina retangular, tamanho A4 ou similar, dobrada e grampeada de forma a formar uma bainha de cerca de 4 cm. ao longo de um lado maior. A bainha é dividida em 8 posições, e cada posição podemos colocar um pequena tira de papel, estreita o suficiente para ocupar uma posição da bainha, e alta o suficiente para ter uma extremidade fora da bainha, pela qual possa ser puxada e recolocada na bainha. Em cada uma das 8 tiras, na parte que fica dentro da bainha, escrevemos um número de dois algarismos, i.e. um número de 00 a 99. Pode haver (alguns) números repetidos.
Um elemento de cada grupo é designado o operador da lista. O operador sabe seguir apenas instruções que impliquem em
ME1 a ME8 , e/ou MD1 a MD8
ME-- , ME++ , MD-- , MD++
CT< , CT<= , CT== , CT!= , CT >= , CT >
O operador não pode memorizar os números na lista, acessando (vendo) apenas os números nas duas tiras que puxou. O operador não pode memorizar uma lista de instruções, ou realizar operações mais complexas que as acima mencionadas.
Cada grupo deve descrever uma receita, para ser lida para a operadora, que sirva para ordenar o 8 números da lista. Após trocar as receitas com outro grupo, cada grupo deve avaliar a receita que recebeu, dizendo se:
Alguns dos algoritmos conhecidos são:
.......
Ao fim do primeiro passo do algoritmo da Seleção Direta, colocamos (selecionamos) o menor (ou um dos menores, em caso de empate) dos números da lista na primeira posição. No segundo passo, trabalhamos apenas com a sub-lista das posições 2 a 8, e assim por diante.
.......
Este método deve seu nome a analogia com as bolhas em uma coluna de líqüidos imiscíveis subindo e descendo durante o processo de decantação. Podemos também fazer a analogia com o processo de ir avançando dentro do ônibus, com os passageiros sendo ordenados segundo o número do ponto em que saltarão. Ao fim do primeiro passo do algoritmo da Seleção Direta, colocamos (selecionamos) o menor (ou um dos menores, em caso de empate) dos números da lista na primeira posição. No segundo passo, trabalhamos apenas com a sub-lista das posições 2 a 8, e assim por diante.
A idéia básica deste método é a seguinte:
De posse de uma lista JÁ ordenada de N números, é fácil acrescentar mais um número a lista, obtendo a lista ordenada de tamanho N+1. Coloque o novo número na última, ou (N+1)-ésima posição, e compare todos os pares de posições consecutivas, da direita para a esquerda, trocando os números de posição caso o da esquerda seja maior que o da direita. Desta forma, inserimos o novo número na ordem correta. Este processo pode ser implementado com a seguinte seqüência de instruções:
ME(N) , MD(N+1) , CT> , ME(N-1) , MD(N) , CT> , ... , ME(2) , MD(3) , CT> , ME(1) , MD(2) , CT>
Note agora que uma lista de 1 posição JÁ esta ordenada, afinal, o menor (que também é o maior, e o único) elemento da lista esta na primeira posição. Assim, podemos começar com a lista ordenada contendo apenas o primeiro número da lista original. Em seguida inserimos nesta lista o segundo número da lista original, e assim por diante.
Gostaríamos de ter uma idéia da eficiência de cada algoritmo para ordenar uma lista de N números. Poderíamos para tanto medir o tempo que um operador leva para completar a tarefa, mas esta medida depende também da destreza do operador. Para evita a dependência em relação ao operador, poderíamos medir o número de operações básicas a serem efetuadas. Definindo a operação básica como sendo uma (1) comparação, todos os três algoritmos descritos necessitam 1+2+3+...+(N-2)+(N-1) = N*(N-1)/2 operações básicas para ordenar uma lista de tamanho N. Podemos também escrever N*(N-1)/2 como N^2/2 -N/2, isto é, um termo quadrático mais um termo linear. Para N grande, o termo linear é desprezível, de modo que dizemos que o algoritmo é quadrático em N, ou que o algoritmo é da ordem de N ao quadrado, o que denotamos como O(N^2). Qual seria por exemplo o número necessário de operações para ordenar os telefones dos aproximadamente 10M moradores da grande São Paulo?
Abreviaturas comuns: Kilo= 10^3 , Mega= 10^6 , Giga= 10^9 , Tera= 10^12
O algoritmo merge sort é análogo ao processo comunmente utilizado por duas pessoas tentando ordenar uma pilha de cartas: Cada uma ordena meia pilha, e então ambas as meia-pilhas são juntados em uma terceira pilha. Para juntar as duas meia-pilhas basta repetir a seguinte operação: Compare as cartas no topo de cada meia-pilha, e deposite a menor no topo da terceira pilha.
Esta idéia básica pode ser usada recursivamente. Pense que uma pessoa preguiçosa, tendo a incumbência de ordenar um pilha de cartas, pediu a seus dois filhos que ordenassem cada qual meia pilha, para posteriormente junta-las. Se a pilha original tinha N cartas, junta-las exigirá N operações, onde definimos uma operação como retirar uma carta de um meia pilha. Cada um dos filhos todavia, igualmente preguiçosos, convocou dois de seus próprios filhos, netos da primeira pessoa, dando a cada qual metade de sua meia pilha, e assim por diante. Cada um dos filhos deve juntar duas pilhas de tamanho N/4 em uma pilha de tamanho N/2. Assim cada filho executa N/2 operações. Como temos 2 filhos, temos que a geração dos filhos realiza 2*(N/2)=N operações. Analogamente, cada um dos 4 netos executa N/4 operações. Como convocamos 4 netos (dois filhos de cada filho) temos que a geração dos netos executou 4*(N/4)=N operações. Quando, após várias gerações algum descendente recebe uma pilha unitária, nada há a fazer. Assumindo que o número total de cartas é uma potência inteira de 2, isto é, N= 2^k, vemos que a k-ésima geração receberá pilhas unitárias, começando da 0-ésima geração. Como cada geração executa no total N operações, o algoritmo necessita N*k ou N*log(N) operações (em computação, tomamos o logaritmo sempre na base 2).
Cada grupo deve definir um pequeno conjunto de operações simples, e em seguida dar uma receita para ordenar 8 números usando o merge-sort. Neste exercício o operador manipula uma cartolina com duas bainhas, a bainha de cima e a de baixo. A cartolina pode também ter alguns clips para marcar posições.