Para trazer ordem ao caos foram criados os algoritmos de ordenação e pesquisa. Os algoritmos de ordenação nos trazem a oportunidade de ordenar os dados, para que tenhamos resposta às perguntas do tipo... "quais os clientes que mais compraram esse ano?", "quais são os funcinários que tem maior ordenado?", etc...
Os algoritmos de pesquisa nos permitem que encontremos um determinado dado no meio de um milhão de dados.
Mas, por mais rápidos que sejam os computadores hoje, esse processo
pode ser bastante demorado. Para isso, esse trabalho trás formas
de otimizar esses processos, fazendo o maior número de operações
com um mínimo de esforço possível do microprocessador.
Como já foi dito antes, a ordenação de dados
é de extrema importância em um banco de dados. Tomemos por
exemplo o seguinte banco de dados:
Cliente Vendas (R$)
A 12.856
B 13.423
C 17.366
D 15.352
E 13.432
F 17.382
G 17.432
H 12.423
I 10.324
J 13.312
K 14.353
L 17.435
E por aí vai... Todos os dados deste banco são semelhantes
e nenhum deles nos salta à vista. De que forma faríamos a
ordenação destes dados?
O primeiro modo que nos vem à cabeça é fazer o seguinte: percorrer toda a lista e colocar o maior dado no topo. Logo a seguir fazer isso de novo, e de novo, e tantas vezes quantas forem o número de registros da lista.
Como veremos a seguir, no entanto, esse método pode ser bastante ineficiente. A eficiência de um método ou algoritmo de ordenação pode ser medida por duas variáveis: o número de comparações e o número de trocas, e quanto maior forem estes, mais ineficiente é o algoritmo.
A lista acima, por exemplo, tem 12 registros. Como temos que passar
12 vezes pela lista, fazendo uma comparação para cada registro
da lista, chegamos a um total de 144 comparações, e de, no
máximo, 144 trocas. Não parece muito, considerando que os
computadores hoje podem fazer milhares de operações por segundo.
Mas observe a segunite tabela:
Registros ComparaçõesE todos sabemos que muitas tabelas podem facilmente chegar a mais de 1 milhão de registros.
5 25
25 625
500 250.000
2.000 4.000.000
50.000 2.500.000.000
Para exemplificar os métodos de ordenação, vamos criar um algoritmo em Pascal onde iremos estudar os métodos de ordenação mais comuns.
A base do programa seria a seguinte:
A constante TL é o tamanho da lista. Iremos usar 15 no caso, para que todos os valores caibam em uma linha do monitor. Poderia usar qualquer valor que não estourasse o longint, até 2.147.483.648 valores.
program ordenacao;const
TL = 15; { Total de elementos da lista }type
lista = array[1..TL] of longint;var
L : lista;
comp : longint;
troca : longint;
i : longint;begin
randomize;
{ Joga valores para a lista }
for i := 1 to TL do
L[i] := trunc(random(TL)) + 1;
escreve_lista(L,0,0);
end.
A variável L é a que vai guardar a lista. Com as variáveis comp e troca iremos contar o número de comparações e trocas. E na rotina principal lançamos valores gerados aleatóreamente entre 1 e 15 para a lista.
Vamos criar também um procedimento que troca o valor de dos registros. O precedimento é o seguinte:
E vamos criar também um procedimento que esreve a lista, e mais quantas comparação e trocas foram feiras. Vamos chamar esse procedimento de escreve_lista.
procedure trocar_v (var a,b : longint);
var
c : longint;
begin
c := a;
a := b;
b := c;
end;
procedure escreve_lista (L : lista; comp : longint; troca : longint);
var
i : longint;
begin
write(' ');
for i := 1 to (TL - 1) do
write(L[i]:2,'| ');
writeln(L[TL]:2);
if not((troca = 0) and (comp=0)) then
writeln('Trocas: ',troca,' Comparações: ',comp);
end;
O algritmo é o seguinte:
Como podemos ver, também contamos quantas comparações e trocas foram feitas. Um resultado possível poderia ser este:
var
i,j : longint;
begin
comp := 0; troca := 0;
for i := 2 to TL do
begin
for j := TL downto i do
begin
inc(comp);
if L[j-1] > L[j] then
begin
inc(troca);
trocar_v(L[j],L[j-1]);
end;
end;
end;
escreve_lista(L,comp,troca);
end;
15| 4| 6| 9| 5| 11| 3| 5| 10| 11| 3| 9| 9| 11| 12 <-- Lista inicialAqui temos um algoritmo que certamente funciona. Porem a que preço? O algoritmo faz muitas comparações desnecessárias, e além disso, troca somente com o seu vizinho. Não seria mais eficiente que o 15 fosse jogado diretamente para o final, por exemplo?
3| 3| 4| 5| 5| 6| 9| 9| 9| 10| 11| 11| 11| 12| 15 <-- Lista ordenada
Trocas: 39 Comparações: 105
Estes são todos os passos realizados pelo algoritmo:
15| 4| 6| 9| 5| 11| 3| 5| 10| 11| 3| 9| 9| 11| 12Em negrito aparecem as trocas (use uma régua para ver melhor). Note o que elas acontecem sempre com o seu vizinho, nunca mais longe. Observe também o longo caminho do 15 para ir do início ao fim, sendo que ele troca 14 vezes de posição.
15| 4| 6| 9| 5| 11| 3| 5| 10| 3| 11| 9| 9| 11| 12
15| 4| 6| 9| 5| 11| 3| 5| 3| 10| 11| 9| 9| 11| 12
15| 4| 6| 9| 5| 11| 3| 3| 5| 10| 11| 9| 9| 11| 12
15| 4| 6| 9| 5| 3| 11| 3| 5| 10| 11| 9| 9| 11| 12
15| 4| 6| 9| 3| 5| 11| 3| 5| 10| 11| 9| 9| 11| 12
15| 4| 6| 3| 9| 5| 11| 3| 5| 10| 11| 9| 9| 11| 12
15| 4| 3| 6| 9| 5| 11| 3| 5| 10| 11| 9| 9| 11| 12
15| 3| 4| 6| 9| 5| 11| 3| 5| 10| 11| 9| 9| 11| 12
3| 15| 4| 6| 9| 5| 11| 3| 5| 10| 11| 9| 9| 11| 12
3| 15| 4| 6| 9| 5| 11| 3| 5| 10| 9| 11| 9| 11| 12
3| 15| 4| 6| 9| 5| 11| 3| 5| 9| 10| 11| 9| 11| 12
3| 15| 4| 6| 9| 5| 3| 11| 5| 9| 10| 11| 9| 11| 12
3| 15| 4| 6| 9| 3| 5| 11| 5| 9| 10| 11| 9| 11| 12
3| 15| 4| 6| 3| 9| 5| 11| 5| 9| 10| 11| 9| 11| 12
3| 15| 4| 3| 6| 9| 5| 11| 5| 9| 10| 11| 9| 11| 12
3| 15| 3| 4| 6| 9| 5| 11| 5| 9| 10| 11| 9| 11| 12
3| 3| 15| 4| 6| 9| 5| 11| 5| 9| 10| 11| 9| 11| 12
3| 3| 15| 4| 6| 9| 5| 11| 5| 9| 10| 9| 11| 11| 12
3| 3| 15| 4| 6| 9| 5| 11| 5| 9| 9| 10| 11| 11| 12
3| 3| 15| 4| 6| 9| 5| 5| 11| 9| 9| 10| 11| 11| 12
3| 3| 15| 4| 6| 5| 9| 5| 11| 9| 9| 10| 11| 11| 12
3| 3| 15| 4| 5| 6| 9| 5| 11| 9| 9| 10| 11| 11| 12
3| 3| 4| 15| 5| 6| 9| 5| 11| 9| 9| 10| 11| 11| 12
3| 3| 4| 15| 5| 6| 9| 5| 9| 11| 9| 10| 11| 11| 12
3| 3| 4| 15| 5| 6| 5| 9| 9| 11| 9| 10| 11| 11| 12
3| 3| 4| 15| 5| 5| 6| 9| 9| 11| 9| 10| 11| 11| 12
3| 3| 4| 5| 15| 5| 6| 9| 9| 11| 9| 10| 11| 11| 12
3| 3| 4| 5| 15| 5| 6| 9| 9| 9| 11| 10| 11| 11| 12
3| 3| 4| 5| 5| 15| 6| 9| 9| 9| 11| 10| 11| 11| 12
3| 3| 4| 5| 5| 15| 6| 9| 9| 9| 10| 11| 11| 11| 12
3| 3| 4| 5| 5| 6| 15| 9| 9| 9| 10| 11| 11| 11| 12
3| 3| 4| 5| 5| 6| 9| 15| 9| 9| 10| 11| 11| 11| 12
3| 3| 4| 5| 5| 6| 9| 9| 15| 9| 10| 11| 11| 11| 12
3| 3| 4| 5| 5| 6| 9| 9| 9| 15| 10| 11| 11| 11| 12
3| 3| 4| 5| 5| 6| 9| 9| 9| 10| 15| 11| 11| 11| 12
3| 3| 4| 5| 5| 6| 9| 9| 9| 10| 11| 15| 11| 11| 12
3| 3| 4| 5| 5| 6| 9| 9| 9| 10| 11| 11| 15| 11| 12
3| 3| 4| 5| 5| 6| 9| 9| 9| 10| 11| 11| 11| 15| 12
3| 3| 4| 5| 5| 6| 9| 9| 9| 10| 11| 11| 11| 12| 15
Trocas: 39 Comparações: 105
Neste algoritmo, ao invés dos dados serem comparados com os seus vizinhos, é criado um gap. O gap, no início, é igual à parte inteira da divisão do número de elementos da lista por 2. Por exemplo, se a nossa lista tem 15 elementos, o gap inicial é igual a 7. São então comparados os elementos 1o. e 8o., 2o. e 9o., e assim por diante.
O que acontece, então? A maior parte dos elementos já vão para suas posições aproximadas. O 15, por exemplo, já é mandado para o fim da lista na primeira passagem, ao contrário do que acontece na ordenção de troca.
Ao terminar de passar por todos os elementos da lista, o gap é diminuído em 1 e é feita uma nova passagem. Isso é repetido até que o gap seja igual a 0.
O algoritmo é este aqui:
Um resultado possível para este algoritmo seria o seguinte:
procedure ordena_shell (l : lista);
var
gap,i,j,k : longint;
begin
comp := 0; troca := 0;
gap := TL div 2;
while (gap > 0) do
begin
for i := (gap + 1) to TL do
begin
j := i - gap;
while (j > 0) do
begin
k := j + gap;
inc(comp);
if (l[j] <= l[k]) then
j := 0
else
begin
inc(troca);
trocar_v(l[j],l[k]);
end;
j := j - gap;
end;
end;
gap := gap div 2;
end;
escreve_lista(l,comp,troca);
end;
1| 12| 12| 9| 11| 13| 4| 14| 6| 11| 14| 14| 13| 8| 2Vamos observar agora todos os passos realizados pelo algoritmo:
1| 2| 4| 6| 8| 9| 11| 11| 12| 12| 13| 13| 14| 14| 14
Trocas: 21 Comparações: 52
15| 9| 3| 6| 1| 4| 15| 14| 4| 13| 5| 12| 11| 12| 4Observe o número 5. No início, ele está próximo do fim da lista. Porém, logo no princípio da operação, ele é jogado para o início do algoritmo, ou seja, próximo da sua posição final. Após isso, ele move-se mais duas vezes para chegar ao seu destino final.
14| 9| 3| 6| 1| 4| 15| 15| 4| 13| 5| 12| 11| 12| 4
14| 4| 3| 6| 1| 4| 15| 15| 9| 13| 5| 12| 11| 12| 4
14| 4| 3| 5| 1| 4| 15| 15| 9| 13| 6| 12| 11| 12| 4
14| 4| 3| 5| 1| 4| 12| 15| 9| 13| 6| 12| 11| 15| 4
14| 4| 3| 5| 1| 4| 12| 4| 9| 13| 6| 12| 11| 15| 15
4| 4| 3| 5| 1| 4| 12| 14| 9| 13| 6| 12| 11| 15| 15
4| 1| 3| 5| 4| 4| 12| 14| 9| 13| 6| 12| 11| 15| 15
4| 1| 3| 5| 4| 4| 12| 6| 9| 13| 14| 12| 11| 15| 15
4| 1| 3| 5| 4| 4| 12| 6| 9| 11| 14| 12| 13| 15| 15
4| 1| 3| 5| 4| 4| 11| 6| 9| 12| 14| 12| 13| 15| 15
1| 4| 3| 5| 4| 4| 11| 6| 9| 12| 14| 12| 13| 15| 15
1| 3| 4| 5| 4| 4| 11| 6| 9| 12| 14| 12| 13| 15| 15
1| 3| 4| 4| 5| 4| 11| 6| 9| 12| 14| 12| 13| 15| 15
1| 3| 4| 4| 4| 5| 11| 6| 9| 12| 14| 12| 13| 15| 15
1| 3| 4| 4| 4| 5| 6| 11| 9| 12| 14| 12| 13| 15| 15
1| 3| 4| 4| 4| 5| 6| 9| 11| 12| 14| 12| 13| 15| 15
1| 3| 4| 4| 4| 5| 6| 9| 11| 12| 12| 14| 13| 15| 15
1| 3| 4| 4| 4| 5| 6| 9| 11| 12| 12| 13| 14| 15| 15
Trocas: 18 Comparações: 45
Imagine o primeiro dado da lista como sendo i e o último como sendo o j. O i é então retirado para que sirva como chave. É feita então a comparação entre i (que é a chave) e j. Caso j seja menor que a chave, j e a chave trocam de posição, e i é incrementado. Caso o contrário ocorra, não há troca, e j é decrementado.
Esse processo é repetido até que i e j apontem para o mesmo dado (que é o dado central). A lista então é dividida em duas listas, e o mesmo processo é realizado, tanto na lista da direita como da esquerda. Novamente as listas são divididas, e o processo é repetido. Isso acontece até que o número de listas (segmentos) seja igual ao número de registros da lista original.
A explicação é bastante complexa, vejamos o algoritmo:
Note que existe um procedimento dentro do outro. O procedimento principal chama ao parcial, que por sua vez chama a si mesmo. Um resultado possível de se obter com essa lista é:
procedure ordena_segmentacao (l : lista);procedure parcial(esq,dir : integer; var l : lista);
var
i,j,k : integer;
begin
k := (l[esq] + l[dir]) div 2;
i := esq;
j := dir;repeat
while l[i] < k do
inc(i);
while k < l[j] do
dec(j);
inc(comp);
if i <= j then
begin
inc(troca);
trocar_v(l[i],l[j]);
inc(i);
dec(j);
end;
until i > j;if esq < j then
parcial(esq,j,l);
if i < dir then
parcial(i,dir,l);
end;begin { procedimento principal }
comp := 0; troca := 0;
parcial(1,TL,l);;
escreve_lista(l,comp,troca);
end;
13| 7| 11| 10| 15| 7| 10| 4| 2| 2| 2| 13| 14| 8| 13Note que o número de trocas é similar ao obtido com o algoritmo de ordenação por shell, no entanto, o número de comparações é bem menor. E aqui temos todos os passos do algoritmo:
2| 2| 2| 4| 7| 7| 8| 10| 10| 11| 13| 13| 13| 14| 15
Trocas: 17 Comparações: 19
1| 8| 9| 8| 13| 14| 14| 7| 7| 4| 15| 10| 3| 15| 6Observe, pelo número 6, que o objetivo é o mesmo da ordenação por shell: jogar o número para sua posição aproximada, e depois apenas ajustá-lo. O que muda, no caso, é o processo de como isso é feito.
1| 3| 9| 8| 13| 14| 14| 7| 7| 4| 15| 10| 8| 15| 6
1| 3| 6| 8| 13| 14| 14| 7| 7| 4| 15| 10| 8| 15| 9
1| 3| 6| 4| 13| 14| 14| 7| 7| 8| 15| 10| 8| 15| 9
1| 3| 6| 4| 7| 14| 14| 7| 13| 8| 15| 10| 8| 15| 9
1| 3| 6| 4| 7| 7| 14| 14| 13| 8| 15| 10| 8| 15| 9
1| 3| 4| 6| 7| 7| 14| 14| 13| 8| 15| 10| 8| 15| 9
1| 3| 4| 6| 7| 7| 9| 14| 13| 8| 15| 10| 8| 15| 14
1| 3| 4| 6| 7| 7| 9| ?060;b>8| 13| 8| 15| 10| 14| 15| 14
1| 3| 4| 6| 7| 7| 9| 8| 10| 8| 15| 13| 14| 15| 14
1| 3| 4| 6| 7| 7| 8| 8| 10| 9| 15| 13| 14| 15| 14
1| 3| 4| 6| 7| 7| 8| 8| 9| 10| 15| 13| 14| 15| 14
1| 3| 4| 6| 7| 7| 8| 8| 9| 10| 14| 13| 14| 15| 15
1| 3| 4| 6| 7| 7| 8| 8| 9| 10| 13| 14| 14| 15| 15
1| 3| 4| 6| 7| 7| 8| 8| 9| 10| 13| 14| 14| 15| 15
Trocas: 18 Comparações: 22
João 582-4045Se quisermos buscar um nome qualquer dentro desta lista, temos que percorrer toda a lista, ou pelo menos o necessário até encontrarmos o nome procurado.
Paulo 532-4352
Pedro 594-2412
André 343-5324
Fernando 324-4235
Maria 241-4353
Sônia 425-2412
Rafael 243-2534
Tiago 435-3421
Mas se tivermos a lista ordenada por ordem alfabética, fica muito mais fácil: é só irmos para a letra que queremos, e logo encontraremos o telefone desejado.
Vamos criar um programa que vai nos servir de base para nossas pesquisas:
Criamos as variáveis pos e pesq, que vão gardar a posição do dado pesquisado e o número de pesquisas feitas, respectivamente. Os dados jogados para a lista são os múltiplos de 3: 3, 6, 9, 12, etc...
program busca;const
TL = 20; { Total de elementos da lista }type
lista = array[1..TL] of longint;var
L : lista;
pesq : longint;
pos : longint;
i : longint;procedure pesquisado (pos: longint; pesq : longint?60;/b>);
begin
writeln('Posição: ',pos);
writeln('Dados pesquisados: ',pesq);
end;begin { Rotina principal }
for i := 1 to TL do
L[i] := i * 3;
end.
O procedimento pesquisado nos rerorna a posição do dados pesquisado, e quantos dados o programa teve que passar até que encontrasse o dado buscado.
Iremos, neste caso, aumentar o número de dados para da lista
para 20, para que o resultado fique mais visível.
Esse tipo de pesquisa é útil caso a lista de busca esteja desordenada, mas caso a lista esteja em ordem, seu rendimento é bastante baixo.
O algoritmo seria este:
O número de dados pesquisados, neste caso, é igual à posição dos dados. Por exemplo, para que se encontre um dados que está na 13a. posição, é necessário que se façam 13 buscas.
procedure busca_simples (L : lista; val : longint);
var
x,i,pos,pesq : integer;
begin
pos := -1;
for i := 1 to TL do
begin
inc(pesq);
if L[i] = val then
begin
pos := i;
break;
end;
end;
pesquisado(pos,pesq);
end;
Caso estejamos buscando o dado de número 54 do nosso programa, estes são todos os passos realizados pelo algoritmo:
A busca é feita dado a dado, até que se encontre o dado buscado.
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60 3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
O algoritmo é o seguinte:
Como se pode imaginar, o número de passos realizados por este algoritmo é bem menor que o anterior, porém é importante notar que o a lista deve estar ordenada para que este algoritmo funcione.
procedure pesquisa_binaria(var L : lista; val : longint);
var x, j, y, pos, pesq : integer;begin
y := 0;
x := TL;
while x-y > 1 do
begin
j := (x+y) div 2;
inc(pesq);
if val <= L[j] then
x := j
else
y := j;
end;
if L[x] = val then
pos := x
else
pos := -1;
pesquisado(pos,pesq);
end;
Aqui os passos realizados pelo algoritmo:
A busca é feita, no caso, buscando-se o dado central. Note que na primeira linha o dado central é o 30. Logo depois, a lista foit dividida em duas, então o dado central se tornou o 45. E assim por diante, até que se encontrou o dado correto.
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
3| 6| 9| 12| 15| 18| 21| 24| 27| 30| 33| 36| 39| 42| 45| 48| 51| 54| 57| 60
Podemos concluir que o algoritmo de pesquisa binária é,
normalmente, mais veloz, e por isso recomendado para listas grandes.
É claro que isso pode se inverter, caso - por exemplo - se busque pelo primeiro dado.
Aqui está o gráfico que compara as duas formas de pesquisa de dados:
Os métodos de ordenação mais utilizados são três: