Busca e ordenação
Na introdução são estudados os algoritmos mais elementares de busca e ordenação. São os menos eficientes, mas são mais simples de entender. Os mais rápidos dependem de conhecimentos mais avançados que não fazem parte de uma introdução. Há diversas questões de probabilidade e combinatória que envolvem tais algoritmos, mas isso não é estudado numa introdução.
O modo usual de ensino desses algoritmos é mostrando uma sequência de valores e realizando uma ordenação ou uma busca na prática, pensando apenas no que é feito. Em seguida estuda-se a sequência lógica de operações que é feita para se chegar a um algoritmo, passo a passo. Ao final é possível fazer uma análise simplificada de desempenho do algoritmo, nada que exija domínio de formalismo matemático, apenas uma avaliação sobre o pior caso (maior número de operações), melhor caso (menor número de operações) e uma estimativa do caso médio.
Na análise de desempenho se faz uma estimativa proporcional. Isto é, não importa a velocidade com que o algoritmo é executado já que isto depende do processador. O que importa é o número de operações feitas.
- Busca sequencial
/* Recebe um vetor, a quantidade de elementos do vetor e um valor x.
Se encontrar o x no vetor, devolva 1.
Senão, devolva -1 */
int busca (int vetor[], int n, int x) {
int i;
for (i = 0; i < n; i++)
if (vetor[i] == x)
return 1;
return -1;
}
Temos um grupo de valores, queremos saber se um x esta ou não nesse conjunto. Suponha que o conjunto não tem organização. A distribuição dos elementos é aleatória. A única forma de saber se um x faz ou não parte do conjunto é procurando por todos os elementos um a um. Este é o pior caso de busca de um valor num conjunto de valores.
Melhor caso: uma operação. O elemento é o primeiro e é achado na primeira tentativa.
Pior caso: n operações, tantas quantos forem os elementos do conjunto. O elemento é o último ou após procurar em todos, nenhum é o procurado.
Média: [math]\displaystyle{ 1 + 2 + ... (n - 1) + n = \frac{n(n - 1)}{2} }[/math]. A prova é por indução.
- Busca binária (depende da sequência estar previamente ordenada!)
/* Recebe um vetor, o número de elementos e um valor x para procurar.
Se achou, devolve o índice do elemento
Senão, devolve -1 */
int buscabinaria(int a[], int n, int x) {
int inicio = 0,
final = n - 1,
meio;
while (inicio <= final) {
meio = (inicio + final) / 2;
if (a[meio] == x) return meio;
if (a[meio] > x) final = meio - 1;
else inicio = meio + 1;
}
return -1;
}
A decisão "se meio for maior, vá para a esquerda" pode ser trocada "se meio for menor, vá para a direita", tanto faz. O algoritmo não inclui um contador de tentativas de busca feitas, mas é bem fácil colocar um. Porém, note que para isso precisamos de um ponteiro, pois a função não pode devolver "achei" ou "não achei" e mais o número de tentativas feitas ao mesmo tempo.
Vamos procurar o número 39 num vetor de 9 elementos:
- Primeiro passo, some o primeiro e o último índice e divida por dois
| (0 + 8) / 2 | ||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 4 | 6 | 8 | 9 | 11 | 39 | 56 | 78 |
- Segundo passo, 39 > 9, então o número não pode estar à esquerda de 9, continue para a direita e já descarte o elemento da comparação anterior, no caso o 9
| (0 + 8) / 2 | ||||||||
| 5 | 6 | 7 | 8 | |||||
| 11 | 39 | 56 | 78 |
Basta utilizar este processo repetidas vezes para qualquer elemento procurado. Quando a média não é inteira, não arredonde, trunque, ou simplesmente considere apenas a parte inteira da média. A busca acaba quando chegamos a (n + n)/2 ou inicio = final, isso vale tanto para um elemento procurado que esta na última posição quanto um elemento que não esta em lugar nenhum.
Obs.: alguém pode ter olhado para a tabela e pensado que os espaços em branco representam uma operação de apagar valores do vetor. Não! É apenas para mostrar que na busca estamos ignorando valores que não são o que estamos procurando. Não estamos apagando nada do vetor.
Melhor caso: uma operação. O elemento procurado está no meio.
Pior caso: [math]\displaystyle{ 1 + \log_2{n} }[/math] operações. O elemento procurado é o último ou não esta em lugar nenhum. Façamos uma rápida dedução (visualize no papel!): comece com qualquer quantidade de elementos. Dobre a quantidade. O número de comparações cresce de apenas uma unidade. Tente um aumento maior, eleve a quantidade de elementos ao quadrado. O número de comparações aumenta apenas de dois (o aumento foi proporcional ao aumento do expoente da potência). Perceba, enquanto o crescimento da quantidade de elementos é geométrico, o crescimento da quantidade de comparações é linear, muito menor.
Façamos o mesmo raciocínio, mas "ao contrário": a cada etapa da busca binária metade da tabela é descartada, o que evidencia uma progressão geométrica [math]\displaystyle{ n/2 }[/math], [math]\displaystyle{ n/4 }[/math], ..., [math]\displaystyle{ n/2^k }[/math]. O limite da busca é 1, pois quando a tabela tiver 1 elemento, cessam as divisões. Temos então que [math]\displaystyle{ n/2^k }[/math] é no máximo 1, ou [math]\displaystyle{ n/2^k \le 1 }[/math]. Façamos uma manipulação algébrica: [math]\displaystyle{ n \le 2^k }[/math]. Aplicamos agora a definição do log e obtemos: [math]\displaystyle{ \log_2{n} \le k }[/math]. Onde n é o número de elementos e k o número de operações de comparação.
Média: [math]\displaystyle{ \log_2{n} }[/math] operações.
Uma analogia: um dicionário é uma sequência ordenada de palavras. Se procurássemos uma palavra usando a busca sequencial, sempre seríamos obrigados a folhear o dicionário página por página até encontrar a palavra procurada. Com a busca binária podemos abrir o dicionário diretamente na primeira letra do alfabeto da palavra procurada. A partir daí procuramos apenas na lista daquela letra, já sabemos que a palavra não está em todo o resto do dicionário. Repetimos o mesmo critério para a segunda letra da palavra, pulamos várias páginas para frente ou para trás dependendo da segunda letra ser do início ou do fim do alfabeto. Numericamente, o algoritmo tem um comportamento de uma progressão geométrica de razão 1/2. Como o princípio do algoritmo se baseia em dividir em dois e procurar para frente ou para trás, dividir em três ou mais partes não é possível.
- Ordenação por seleção
/* recebe o endereço de memória de duas variáveis e faz a troca
de um pelo outro */
void troca (int *pa, int *pb) {
int temp;
temp = *pa;
*pa = *pb;
*pb = temp;
}
/* Recebe um vetor e um número de elementos.
Ordena o número dado de elementos em ordem crescente */
void SelectSort (int a[], int n) {
int i, j, imin;
for (i = 0; i < n - 1; i++) {
imin = i;
for (j = i + 1; j < n; j++)
if (a[imin] > a[j]) imin = j;
troca (&a[imin], &a[i]);
}
}
Vamos ordenar uma sequência de 6 valores:
| índice | início | 1° troca | 2° troca | final |
| 0 | 12 | 1 | 1 | 1 |
| 1 | 5 | 5 | 5 | 5 |
| 2 | 8 | 8 | 6 | 6 |
| 3 | 33 | 33 | 33 | 8 |
| 4 | 1 | 12 | 12 | 12 |
| 5 | 6 | 6 | 8 | 33 |
Primeiro passo: procure o menor elemento a partir do segundo, troque com o primeiro da lista.
Segundo passo: procure o menor elemento a partir do terceiro, troque com o segundo da lista.
Continue até terminar a ordenação. No exemplo, duas trocas foram suficientes para ordenar o vetor.
Se houverem repetições o algoritmo troca o primeiro elemento repetido encontrado. Note que nem todas as iterações do laço implicam em operações de troca, por exemplo, na primeira iteração trocamos 1 com 12, na segunda, o número 5 já é o segundo menor valor e já está na posição correta.
Tanto faz simular na horizontal ou na vertical, fica ao seu gosto.
Melhor caso: a sequência já está ordenada. Note que só há como saber se a sequência precisa ou não ser ordenada comparando todos os elementos, o algoritmo não consegue saber se precisa ou não de pelo menos uma troca sem ler todo o vetor primeiro.
Pior caso: a sequência esta invertida, [math]\displaystyle{ n/2 }[/math] operações de troca. Mas, mesmo assim, temos ainda [math]\displaystyle{ (n - 1) + (n - 2) + ... 1 + 2 = \frac{n(n - 1)}{2} }[/math] operações de comparação para decidir se troca ou não.
Média: o algoritmo, com uma sequência ordenada ou não, lê todos os elementos, pulando o primeiro, depois o segundo, assim por diante. Portanto, temos [math]\displaystyle{ (n - 1) + (n - 2) + ... 1 + 2 = \frac{n(n - 1)}{2} }[/math] operações de comparação. A prova é por indução.
Tempo proporcional: em todos os três casos o tempo é proporcional a [math]\displaystyle{ n^2 }[/math].
- Ordenação por bolha
/* Recebe um vetor e um número de elementos.
Ordena com o método da bolha */
void bubble(int a[], int n) {
int i, j;
for (i = 1; i < n; i++) {
j = i;
while (j > 0 && a[j] < a[j - 1]) {
troca(&a[j], &a[j - 1]);
j--;
}
}
}
Vamos ordenar a mesma sequência de antes, mas com o método da bolha:
| indice | início | 1° troca | 2° troca | 3° troca | 4° troca | 5° troca | 6° troca | 7° troca | 8° troca | final |
| 0 | 12 | 5 | 5 | 5 | 5 | 5 | 1 | 1 | 1 | 1 |
| 1 | 5 | 12 | 8 | 8 | 8 | 1 | 5 | 5 | 5 | 5 |
| 2 | 8 | 8 | 12 | 12 | 1 | 8 | 8 | 8 | 8 | 6 |
| 3 | 33 | 33 | 33 | 1 | 12 | 12 | 12 | 12 | 6 | 8 |
| 4 | 1 | 1 | 1 | 33 | 33 | 33 | 33 | 6 | 12 | 12 |
| 5 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 33 | 33 | 33 |
Primeiro passo: compare o primeiro elemento com o segundo, se o segundo for menor, troque de lugar. Senão, não acontece nada.
Segundo passo: compare o segundo com o terceiro, se o terceiro for menor, troque. Se o primeiro for maior, o elemento sobe mais uma posição. Senão, fica onde está.
Continue o processo até terminar. Cuidado! O algoritmo não sobe mais do que um elemento por vez, uma vez que um elemento começou a subir, ele continua até que o elemento acima deste seja menor ou quando chegou ao início da sequência.
Uma outra maneira de ver o algoritmo funcionando. Simule o algoritmo "ao contrário": considere a sequência 1 2 3 4 5. Pegue o número um e "afunde" até a última posição. Ficamos com 5 2 3 4 1. Quantas posições o número um "desceu"? Quatro. Repita com o número dois, mas não o coloque no lugar do um, serão três trocas.
Melhor caso: a sequência já está ordenada. Note que só há como saber se a sequência precisa ou não ser ordenada comparando todos os elementos, o algoritmo não consegue saber se precisa ou não de pelo menos uma troca sem ler todo o vetor primeiro.
Pior caso: a sequência esta invertida. São [math]\displaystyle{ (n - 1) + (n - 2) + ... 1 + 2 = \frac{n(n - 1)}{2} }[/math] operações de troca. Perceba que comparativamente ao método da seleção, o método da bolha realiza tantas operações de troca quanto operações de comparação do método da seleção.
Média: o algoritmo, com uma sequência ordenada ou não, lê todos os elementos, trocando um elemento sempre em posições sequências até achar o seu lugar. A média é igual ao pior caso.
Tempo proporcional: em todos os três casos o tempo é proporcional a [math]\displaystyle{ n^2 }[/math].
