Autor: Pedro Luis Kantek Garcia Navarro


Antigamente, este era um dos primeiros algoritmos a serem aprendidos e usados. Com o passar do tempo, e o surgimento dos ADABAS e DBASES, este assunto foi perdendo importância. Será certo isso?

1 – A presença de linguagens de alto nível, não precisa ser pretexto para que os programadores tenham baixo nível de conhecimento.

2 – Este algoritmo é rodado milhares de vezes em qualquer CPU. Qualquer ganho que se consiga, será multiplicado pelo mesmo fator.

3 – Dois algoritmos parecidos podem ter complexidades (desempenhos), diferindo por várias ordens de grandeza ( centenas, milhares?). É preciso conhecer e estudar este assunto.

4 – É um capítulo fascinante da informática. Qualquer um que tenha gosto pela programação não pode deixar de se emocionar com a “inteligência em estado bruto” que estes algoritmos mostram.

Mas, chega de papo, e vamos ao tema. Só lembrando que um autor famoso disse “Um bom programador conhecerá diversas classificações, mas sempre usará a sua própria”.

Vamos analisar quatro métodos: a) bolha (por ser mais simples e difundido); b) seleção ( o mais intuitivo); c) inserção ( um belo exemplo de clareza e elegância) e d) quicksort (simplicidade + recursividade = eficiência).

No momento de analisar o desempenho, existirão quatro vetores. O vetor 1 já esta ordenado em ordem CRESCENTE. O vetor 2 tem seus elementos randomicamente estabelecido, ou seja, está fora de ordem. O vetor 3 está em ordem DECRESCENTE. Finalmente o vetor 4 em todos os elementos iguais a 55, com apenas o elemento central igual a 44. Os tempos estão em segundos em um PC com clock de 10 Mhz.

a) BOLHA

O princípio é simples. Pares são comparados. Se já estão na ordem desejada são deixados, senão são trocados. A cada passada o maior (menor) elemento é localizado e levado para o seu local. Acompanhe em português estruturado:

MÉTODO BOLHA – tempos de processamento em segundos

b) SELEÇÃO

Este algoritmo segue o seguinte princípio: “Acha-se o menor (maior) valor. Quando encontrado ele é trocado com o primeiro (último) elemento do vetor. Prossegue-se este processo até passar por todos os elementos, e ... o vetor

está classificado. “acompanhe em português estruturado:

MÉTODO SELEÇÃO – tempos de processamento em segundos

c) INSERÇÃO

Este método é engenhoso. Para cada elemento, que é inserido, o vetor é mantido classificado. A questão é achar o lugar definitivo de um elemento e abrir espaço para ele.

MÉTODO INSERÇÃO – tempos de processamento em segundo

d) QUICKSORT

Este algoritmo nasceu de uma pequena modificação do pior algoritmo até então conhecido ( o bolha), e passou a ser o melhor algoritmo que conhecemos. A modificação é simples: em vez de trocar vizinhos, vamos trocar os elementos o mais longe possível um do outro. Isto foi feito por C.R. Hoare, no início dos anos 60. Como este algoritmo tem paternidade conhecida, respeita-se o nome dado por seu inventor: quicksort ( classificação rápida). O grande detalhe é o uso da recursividade, o que pode limitar sua utilização em linguagens pobres ( COBOL, CLIPPER, BASIC, NATURAL etc) que não tenham este recurso. Outra alternativa seria programá-lo de maneira não recursiva, o que o torna um pouco mais complexo.

MÉTODO QUICKSORT – tempos de processamento em segundos

Observações finais:

1 – Para um vetor desordenado cm 5000 elementos, os resultados são: 674 (bolha), 355 (seleção), 233 (seleção) e 3 (quickssort). O algoritmo quicksort chega a ser 226 vezes mais rápido.

2 – Para vetores pequenos, não há diferenças significativas o que justifica a escolha de qualquer método ( provavelmente o mais fácil).

3 – Mediante um pequeno artifício, pode-se deixar o BOLHA bem melhor. Basta verificar se, a cada passada, alguma inversão foi feita. Se não foi feita, o processo está encerrado, independentemente de quantos elementos faltarem.

4 – Estes são os algoritmos que testamos. Entretanto existem outros. Uma lista (incompleta) inclui: shakesort ( parecido com o bolha, mas alternando a direção de classificação), heapsort ( ordenação através de uma árvore binária com ordenação central, na área de rascunho), shellsort ( inserção por incremento decrescente), inserção binária ( a pesquisa na inserção não é seqüencial, mas binária) ( a pesquisa na inserção não é seqüencial, mas binária ), radix sort, e os métodos externos: fusão direta, fusão natural, fusão balanceada multidirecional, classificação polifásica, etc

5 – Na GPT temos um programa PASCAL que implementa 5 algoritmos, e com o qual foram obtidos os tempos acima. O programa está à disposição dos interessados, para olhar, alterar e usar.

6 – Para saber mais leia: ALGORITMOS E ESTRUTURAS DE DADOS ( de N. Wirth); THE ART OF COMPUTER PROGRAMMING, volume 3 SORTING AND SEARCHING, de D. KNUTH; ALGORITHMS, de R. Sedgewick; ALGORITHMICS - The spirit of computing, de D. Harel; RECURSIVE PROGRAMMING TECHNIQUES, de W.H. Burge.