As aparências enganam (algorítimos de ordenação)

Ordenar de forma crescente ou decrescente um sequência de dados na memória de um microcontrolador ou em uma memória externa pode ser necessário uma hora, ainda mais se for usar a busca binária, ou pelo simples fato de você querer dados ordenados. Mas como fazer isto?
Procurando no Google por "sorting algorithms", achei uma página bem interessante que permite visualizar de forma gráfica o que acontece em cada algorítimo. Fui pesquisar como cada um funciona e, buscando o mais simples de programar, acabei no Bubble sorting. Após programar ele com sucesso no PC, resolvi escrever ele e rodar no PIC18F2550. Pra minha surpresa, quando fui organizar uma memória de 512 bytes (4Kbits), esta tarefa foi executada de forma absurdamente lenta (cerca de 10 minutos pra finalizar). Resolvi escrever outro, mas não fui procurar na internet (até procurei o Quick sort mas fiquei com preguiça por dar muito trabalho haha): resolvi pensar. Desenvolvi um algorítimo, mas depois descobri que era exatamente o Selection Sort. Desta vez, o mesmo trabalho que o Bubble levou 10 minutos, em cerca de 3 o Selection fez. "Ora, mas na página lá em cima ele se mostrava bem mais lento. O que houve?" Bem, vou deixar vcs curiosos pela resposta por enquanto. Agora vou mostrar como cada algorítimo realmente trabalha e mostrar os códigos pro PIC que fiz.


Bubble Sorting

Bem simples de programar, o Bubble Sorting consiste em trocar duplas de dados se n+1 > n (sendo n o índice do vetor). Vamos usar de exemplo um vetor de cinco posições com os números 1, 7, 3, 5 e 2. Observe a imagem abaixo que mostra uma iteração apenas (leia como um gibi):


Na próxima iteração, o algorítimo veria que 1 < 3, e portanto não os trocaria de lugar; 3 < 5 mesma coisa, até que por fim chega em 5 > 2, ou seja, trocaria ambos de lugar. Se os números forem iguais, ele não faz nada. O programa precisa repetir isto até todos estarem ordenados.
Abaixo segue um pseudocódigo como exemplo:




Selection Sorting

Tão simples de programar quanto o Bubble, este método surpreendeu ao se mostrar significantemente mais ágil com memórias externas. Este consiste em buscar e "pegar" os menores valores encontrados no vetor e os colocar na ordem crescente, fazendo isso cada vez avançando a partir do último número ordenado. A imagem abaixo exemplifica como isto deve ser feito:


Veja que quando os números forem iguais nada é feito. Creio que este método seja o mais intuitivo (mais próximo do que faríamos como pessoas). Tudo é feito em uma única "passada" pelo vetor.
Aqui segue o pseudocódigo:




Mas e a velocidade?

OK, matando sua curiosidade vamos lá: e a velocidade? A página e vídeos que demonstravam o funcionamento dos algorítimos estavam todos errados? Bem, sim e não.
O problema destes exemplos em animação ou vídeo é considerar que o tempo de leitura e escrita da memória e de comparação sejam todos iguais, mas sabemos que não é verdade. O PIC leva muito mais tempo lendo ou escrevendo uma memória do que simplesmente comparando dois valores da sua RAM. Em uma memória 24C64, por exemplo, a escrita leva cerca de 5 ms a mais do que a leitura, portanto, o algorítimo que menos escrever ganhará vantagem, e em um vetor enorme isto se torna muito relevante, como no exemplo que dei em que o Selection levou cerca de um terço do tempo do Bubble. Ainda mais, o algorítimo que menos escrever aumentará a vida útil da memória. Por isso devemos tomar cuidado com comparações fora do contexto, não só nestes algorítimos mas em qualquer outro. Precisamos pensar muito maior do que as coisas que nos são mostradas. Trago este caso pra que vocês reflitam como é importante considerar os diversos fatores em um programa e escolher métodos conforme a realidade com a qual está trabalhando.

Comentários

  1. muito bom amigo, uma sugestao para o proximo topico poderia ser usando o lcd 16x2 com pic pela comunicaçao spi ou i2c iria certamente ajudar muita gente.

    ResponderExcluir
    Respostas
    1. Opa, obrigado por comentar! Já estava achando que o blog estava esquecido!
      É uma ótima dica, mas como não tenho este módulo, não posso fazer nenhuma publicação sobre isto agora. Fique de olho: tem mais aula sobre módulos.

      Excluir
  2. Parabéns pela matéria, me agregou muito

    ResponderExcluir
    Respostas
    1. Obrigado pelo feedback! Sugiro que, caso não tenha lido, veja a finalização deste assunto em um post mais recente que fiz.

      Excluir

Postar um comentário