Introdução
O processo feito dentro de um programa pode ter diferenças em desempenho, em consumo de memória e em várias coisas que iremos conversar adiante, quando analisarmos os algoritmos. O mais importante é entender que todo algoritmo tem uma entrada e uma saída. Para o algoritmo estar certo, toda entrada precisa resultar em uma saída correta.
Reduzindo um problema a outro
Nós resolvemos o problema da ordenação com duas soluções diferentes:
selecionando quem deveria ficar em cada posição
encontrando a posição onde deveríamos inserir um elemento.
As duas formas são utilizadas naturalmente pelas pessoas, sem que elas percebam que fizeram a escolha entre uma maneira e a outra, em situações diferentes. Porém, como são inventados algoritmos como estes? Será que existem apenas os dois já conhecidos e ninguém mais tenha inventado outra maneira? A verdade é que existem diversos outros. E o processo de inventar um algoritmo é um processo difícil. Além de criá-lo, precisamos provar que ele funciona e que ele é rápido... É uma tarefa trabalhosa.
Por isso, ao ser dado um problema, optamos muitas vezes por analisá-lo e tentamos identificar uma solução conhecida: "esse é um problema de ordenação.. então, vou usar aquele algoritmo que é muito bom para ordenar!"
Olhar com outros olhos o problema... Por exemplo, se quero descobrir quais foram os políticos mais votados em uma eleição, posso verificar qual é o algoritmo que irá identificar quais receberam um maior número de votos. Para isto, basta olhar para os elementos e ver a necessidade de uma ordenação.
Nesse mesmo exemplo, se quero saber quais foram os quatro políticos com maior votação em uma eleição, basta ordená-los e em seguida selecionar os quatro primeiros elementos. Analisei a questão com outros outros olhos, ao invés de me limitar ao problema aparente "tenho que encontrar os quatro maiores". Pensamos de outra maneira: ao ordenar todos os candidatos, foi possível identificar os quatro com maior número de votos.
Além de observar por outros ângulos, nós reduzimos o problema a outro, cuja solução já era conhecida. Sabíamos como solucionar uma ordenação, então apenas foi preciso selecionar os quatro maiores. Podemos também definir outros critérios: os cinco piores ou os três maiores. E os simplifico em uma ordenação...
Sempre que alguém nos pedir os 15 candidatos mais votados ou os três cursos com maior nota... Ordenaremos todos os cursos e pronto, estará acabado. Podemos identificar este tipo de informação. Sem grandes dificuldades, implementamos a ordenação, depois a executamos e informamos rapidamente quais são os três primeiros elementos. Fica ainda mais fácil se a quantidade de itens for pequena.
A grande sacada está em reduzir o problema. Por exemplo, se simplificarmos a questão em uma ordenação, já saberemos que é possível resolvê-lo com o Selection Sort - que foi reduzido a uma busca do menor.
Como analisar o desempenho de algoritmos?
Considerando que analisamos diversos algoritmos e já sabemos implementá-los... O que é preciso para compará-los? Como podemos dizer qual está bom e qual não está? Se alguém desejar seguir a carreira de Ciências da Computação e quiser criar novos algoritmos, como poderá afirmar que o seu algoritmo de ordenação é melhor do que outro já existente? Precisamos ter algum critério de comparação entre eles. Existem diversos critérios de comparação de algoritmos, por exemplo dois: consumo de memória e o tempo para resolução do problema.
Em relação ao primeiro critério: Quanto o algoritmo precisa processar o nosso computador? Quantas contas ele precisa fazer? Quantas operações o algoritmo precisa fazer para terminar e retornar o resultado? Dada a entrada, veremos a saída. Isto significa que poderemos comparar o quanto de memória os algoritmos consomem e com base nisto, determinar: "Esse é o melhor, porque consome menos memória."
O tipo mais famoso de comparação que podemos fazer é o de desempenho de velocidade, que nos informa o quão rápido pode ser um algoritmo. Porém, vamos com calma... Como iremos medir a velocidade? Em segundos, em minutos ou em horas?
Então, qual unidade iremos usar? O computador é capaz de fazer contas, por isso iremos medir a velocidade a partir da quantidade de operações que o computador precisa fazer para encontrar a resolução de um algoritmo. Se precisarmos fazer 10 ou 9 operações, não faz muita diferença na velocidade. No entanto, se a variação for entre 10 e 1 bilhão de operações, a diferença será enorme!
É desta forma que iremos avaliar o desempenho dos dois algoritmos. Analisando dessa forma: "nesse precisamos realizar poucas operações, já nesse precisamos fazer inúmeras..." Nós queremos descobrir como comparar diversos algoritmos. Temos três aqui para analisarmos:
buscaMenor
selectionSort
insertionSort
Vamos observá-los:
Busca Menor Valor:
private static int buscaMenor(Produto[] produtos, int inicio, int termino) { int maisBarato = inicio; for(int atual = inicio; atual <= termino; atual++) { if(produtos[atual].getPreco() < produtos[maisBarato].getPreco()) { maisBarato = atual; } } return maisBarato;}
selectionSort:
private static void selectionSort(Produto[] produtos, int quantidadeDeElementos) for(int atual = 0; atual < quantidadeDeElementos -1; atual++) { int menor = buscaMenor(produtos, atual, quantidadeDeElementos -1); troca(produtos, atual, menor); }}
insertionSort:
private static void insertionSort(Produto[] produtos, int quantidadeDeElementos) { for (int atual = 1; atual < quantidadeDeElementos; atual++) { System.out.println("Estou na casinha " + atual); int analise = atual; while(analise > ) && produtos[analise].getPreco() < produtos[analise -1] { troca(produtos, analise, analise -1); analise--; } }}
Qual deles é o mais rápido ou o mais devagar? Qual é a sua opinião?
Cada um pode ser utilizado em diferente situaçõess. O buscaMenor serve para encontrarmos o menor (ou o maior) de todos.
Já o insertionSort e o selectionSort são algoritmos que ordenam o nosso array. Qual deles parece ser mais rápido e qual parece ser o mais devagar?