parte 3

1
PESQUISA EM MEMÓRIA PRIMÁRIA
Olá! Iremos neste Capítulo tratar do assunto pesquisa. A
palavra pesquisa aqui, tem o significado estrito de busca.
Iremos buscar objetos de informação. Você certamente já
pesquisou por muitas coisas na sua vida, brinquedos, roupas,
chaves, livros e pessoas estão entre as “coisas” que mais
procuramos! Se você já fez isso, já deve ter se aborrecido ao
não encontrar (ou demorar muito para encontrar) o objeto ou
pessoa que procura. Mas, ao demorar a encontrar um objeto,
você já se perguntou se está procurando da maneira correta?
Normalmente, é difícil encontrar algo em um conjunto de
elementos se não usarmos a estratégia de busca apropriada
para o modelo de organização do conjunto? Neste Capítulo
iremos discutir e aprender sobre estas estratégias de busca e
discutir aspectos da pesquisa de diferentes organizações do
conjunto onde procuramos. Mão a obra então!
A pesquisa em memória primária envolve a busca por objetos de informação armazenados em
estruturas de dados instanciadas na memória primária do computador. Não iremos tratar aqui da
pesquisa em memória secundária, que envolve outras técnicas.
Nosso estudo vai compreender a pesquisa simples, onde sabemos exatamente qual o objeto que
queremos. Normalmente sabemos qual é este objeto por meio de uma informação que o diferencia de
todos os demais objetos. Chamaremos esta informação de chave de pesquisa.
Chave de Pesquisa
A pesquisa em memória primária será feita com base em uma
CHAVE DE PESQUISA. A chave de pesquisa pode ser um
elemento de dado do objeto. Por exemplo, o RG de uma pessoa, o
CNPJ de uma empresa ou o número de matrícula de um estudante.
Pode ser também o nome de um país, ou o ISBN de um livro. O
importante da chave de pesquisa é que ela seja única, de forma a
permitir que cada elemento do conjunto seja unicamente
identificável pela sua chave de pesquisa.
A idéia básica da pesquisa portanto é dado um conjunto de dados e uma chave, localizar um elemento
neste conjunto cujo valor da chave de pesquisa seja o mesmo da chave usada. A chave de pesquisa é
escolhida e definida pelo programador com base no problema específico que ele está tratando. Por
exemple, em um conjunto de dados que cataloga os computadores de uma empresa, a chave de
pesquisa pode ser o número de série do computador ou de seu patrimônio.
O conjunto pode ser organizado e armazenado usando diferentes estruturas e tipos abstratos de dados:
Vetores, listas encadeadas, árvores. Já estudamos no capítulo anterior o algoritmo de pesquisa em
listas e em árvores binárias de pesquisa. Neste capítulo iremos analisar em maiores detalhes estes e
outros algoritmos.
Em uma pesquisa, o conceito de eficiência e muito importante. A eficiência pode ser medida pelo
número de inspeções realizadas até encontrar o objeto procurado. Evidentemente, quanto menos
inspeções forem feitas, mais eficiente será a pesquisa.
Inspeção
Uma inspeção consiste na operação de comparação da chave
procurada com a chave de busca de um objeto, visando verificar
se o objeto em questão é que procuramos.
Iremos estudar algoritmos de pesquisa para as três seguintes situações:
1. Os dados estão dispostos de forma desordenada e desconhecida em uma lista linear (um vetor
ou uma lista encadeada). Este cenário pode ser comparado a uma busca onde não há pistas
sobre em que lugar o objeto está. Dessa forma, a única alternativa que temos é realizar uma
busca exaustiva visitando todos os lugares até o objeto ser encontrado. A única forma de
determinar se o objeto não está presente é inspecionar todos os lugares.
2. Os dados estão dispostos de forma ordenada em uma lista linear (um vetor ou uma lista
encadeada). Nesse cenário, a busca é facilitada porque os objetos foram guardados usando
alguma forma de ordenação baseada na chave de busca. Se os objetos forem armazenados,
por exemplo, colocando os objetos em uma seqüência iniciando pelo menor e terminando
pelo maior, a busca poderá ser feita sem a necessidade de inspecionar todos os objetos.
3. Os dados estão dispostos em de forma não ordenada, porém as posições onde os dados estão
localizados podem ser calculadas usando a chave de pesquisa. Esta situação é a que acontece
nas chamadas tabelas Hash onde os elementos são inseridos em posições calculadas a partir
de sua chave de pesquisa.
Iremos estudar a aplicação de três métodos de ordenação aplicáveis a estes cenários. Os métodos
consistem em Pesquisa Seqüencial, Pesquisa Binária e Hashing. As seções a seguir detalham
estes métodos.
Suponha um baralho contendo 40 cartas todas diferentes,
distribuídas de forma totalmente aleatória. Pense em uma carta
específica e responda:
a) Qual a propobilidade da primeira carta do baralho ser a
que você pensou?
b) Qual a propobilidade da segunda carta, ser a que você
pensou? E da terceira?
c) Qual a probabilidade de encontrar a carta após 4
tentativas?
d) Em média quantas cartas terão que ser inspecionadas para
você encontrar a carta que pensou?
1.1 PESQUISA SEQUENCIAL
A pesquisa seqüencial é realizada inspecionando-se o conjunto de objeto seqüencialmente, do início
para o fim ou vice-versa. Duas situações podem ocorrer:
Pesquisa com sucesso: O elemento é encontrado em uma das posições do conjunto
Pesquisa sem sucesso: O conjunto e completamente percorrido e o elemento não é encontrado.
Em um algum de pesquisa, normalmente fazemos dois testes: verificamos se o elemento procurado
corresponde ao objeto inspecionado e verificamos se o limite do conjunto de objetos foi atingido. Por
exemplo, o código abaixo faz isso:
// procurando o x no vetor V
while ((V[i]!= x) && (i<limiteVetor)){
i++;
}
Para melhorar esta implementação, iremos apresentar um algoritmo de pesquisa seqüencial que utiliza
uma sentinela. O uso de sentinelas torna a pesquisa seqüencial mais eficiente.
Sentinela
Sentinela é um valor conhecido que é inserido em uma posição
específica de um arranjo ou de uma lista. O objetivo é usarmos o
valor do sentinela para pararmos um processamento ou uma
busca. Por exemplo, quando buscamos um valor x em um vetor
que vai de 0 a n, e inserimos o valor x como sentinela na posição
n+1. Assim, a busca pode ser feita até encontrarmos o valor do
sentinela, sem a necessidade de testarmos se chegamos até o
limite do arranjo. O código abaixo ilustra este cenário:
// buscando x
v[n+1] = x; // atribui o sentinela
i=0;
while (v[i]!=x) {
i++;
}
1.1.1 Implementação da Pesquisa Seqüencial
Continuaremos a apresentar nossas implementações respeitando o conceito de TAD. Neste capitulo,
iremos usar o TAD Tabela, que nada mais é conjunto do tipo Elemento (já visto em listas
encadeadas). O tipo tabela é apresentado na Figura 4.1.
#include"elemento.h"
#define TRUE 1
#define FALSE 0
#define MAXTAB 1000
typedef struct {
int n;
Elemento itens[MAXTAB+1];
} Tabela;
typedef Tabela *pTabela;
int inicializaTabela(pTabela);
int tabelaCheia(pTabela);
int insereElemento(pTabela, Elemento);
int pesquisaSeqElemento(pTabela, int);
Figura 4.1: Interface do TAD Tabela
As implementações das operações inicializaTabela, tabelaCheia e insereElemento são apresentadas na
Figura 4.2. A Figura 4.3 apresenta a implementação da operação de pesquisaSeqElemento. Esta
operações possui como parâmetro a tabela onde pesquisar e o valor da chave utilizada para a pesquisa.
A função retorna -1 em caso de pesquisa sem sucesso e o índice da posição do elemento procurado,
em caso de pesquisa sem sucesso. Note que foi usado o sentinela (inserido na posição n+1 da tabela).
#include "tabela.h"
/* inicializa a tabela atribuindo 0 ao contador de elementos */
int inicializaTabela(pTabela t) {
t->n = 0;
return TRUE;
}
/*função que verifica se a tabela está cheia
* retorna 1 se cheia e 0 se vazia*/
int tabelaCheia(pTabela t){
return (t->n == MAXTAB);
}
/* Função que insere um elemento na tabela
* */
int insereElemento(pTabela t, Elemento e){
if (tabelaCheia(t)){
return FALSE;
}
t->itens[t->n]=e;
t->n++;
return TRUE;
}
Figura 4.2: Implementação das operações do TAD Tabela
/**
* Pesquisa o elemento usandoa um sentinela.
* O sentila é colocada na
* primeira possição vaga da tabela
*/
int pesquisaSequencial(pTabela t, int chave){
int i;
t->itens[t->n+1].codigo = chave;
i=0;
while(t->itens[i].codigo!=chave) {
i++;
}
if(i>t->n) {
return -1;
}
return i;
}
Figura 4.3: Implementação da operação pesquisaSequencial
1.1.2 Tempo de execução de algoritmos
Os métodos de pesquisa são um bom tópico em nosso curso para introduzirmos algumas noções
sobre desempenho de algoritmos. Para iniciar esta discussão, vamos nos reportar a uma pergunta? É
possível determinar quanto tempo a operação de pesquisa seqüencial leva para encontrar um
elemento?
Existem importantes elementos estão envolvidos nesta pergunta. A saber:
1. A Máquina que será usada para executar o programa.
2. O tamanho total dos dados
Evidentemente, o tempo de uma pesquisa vai mudar dependendo do computador que for utilizado.
Quanto mais rápido o computador, mais rápida será a pesquisa. A mudança de desempenho de uma
computador para outro pode ser expresso por uma constante C. Assim diremos que o tempo gasto por
um programa para executar pode ser expresso por uma função
T Æ f(n).C
Onde C é a constante associada ao computador.
n, por sua vez é o tamanho da entrada de Dados. Ou seja, o tempo de execução da função de
pesquisa é uma função do tamanho da entrada de dados.
Função de complexidade de tempo
Quando analisamos o tempo de execução é comum deixarmos a
constante C de lado e nos concentramos na função f(n). Esta
função é importante pois ela nos dá uma medida de tempo de
execução independente do computador que será utilizado para
executar a operação. A função f(n) é denominada de função de
complexidade de tempo.
Um outro aspecto importante na análise de desempenho de algoritmos são os diferentes casos ou
cenários de execução possíveis. São geralmente considerados os seguintes casos:
•
Melhor Caso: compreende a melhor situação para o algoritmo. A situação em que a resposta
será obtida de forma mais rápida.
•
Caso Médio: Compreende a média de todos os casos considerando as distribuições de
probabilidade típicas para os dados em questão.
•
Pior Caso: Compreende a pior situação para o algoritmo em questão.
Podemos determinar a função de complexidade de tempo para estes três casos para o algoritmo de
pesquisa seqüencial:
Melhor caso: f(n) = 1, ocorre quando o elemento procurado é o primeiro a ser inspecionado.
Pior caso: f(n) = n, ocorre quando o elemento procurado é o último elemento do conjunto a ser
inspecionado.
Caso médio: f(n) = (n+1)/2
O caso médio é obtido da seguinte forma: seja x o elemento procurado e C = {c1,c2,c3..cn}, o conjunto
de elementos a ser pesquisado. Considera-se para este cálculo que a possibilidade de encontrar o
elemento procurado é igualmente provável para qualquer posição do conjunto de elementos
pesquisado. Ou seja,
P(x=c1))= P(x=c2)= .. P(x=cn)=1/n
Temos ainda que para encontrar o elemento procurado na i-ésimo posição do conjunto são necessárias
i inspeções. Por exemplo, para encontrar o elemento na primeira posição é necessário uma
comparação. Para encontrar o elemento na segunda posição são necessárias duas comparações. E
assim por diante.
Sendo assim, temos que
f(n) = 1 * P(x=c1) +2 * P(x=c2)+3* P(x=c3) + .. + n* P(x=cn)
f(n) = 1 * 1/n + 2*1/n+3*1/n +.. n*1/n
f(n) = (1+2+3+..n) *1/n
f(n) = n*(n+1)/2 *1/n
f(n) = (n+1)/2
Tarefa 4.2
1. Desenvolva um programa utilizando o TAD Tabela que
meça o tempo de execução da pesquisa seqüencial. Altere
o código da tabela para aceitar um conjunto de até 100
000 itens. Pesquise por alternativas para medir o tempo de
execução de um programa. Planeje sua estratégia para
medir o tempo.
2. No estudo da pesquisa seqüencial, a busca não leva em
conta a organização dos dados no conjunto. Caso os
dados se encontrem ordenados, por exemplo, em ordem
crescente, a pesquisa seqüencial pode tirar partido desta
ordenação interrompendo a busca ao encontrar um
elemento maior que o que foi procurado. Implemente um
nova operação no TAD Tabela que realize esta pesquisa
considerando que os dados estão ordenados em ordem
crescente. Para testar esta operação os dados devem ser
inseridos ordenadamente na tabela.
1.2 PESQUISA BINÁRIA
Caso o conjunto de dados de pesquisa esteja ordenado, podemos utilizar a pesquisa binária para
encontrar elementos no conjunto. A Pesquisa binária consistem em uma técnica do tipo Dividir para
Conquistar (Divide to Conquer), na qual o conjunto de dados pesquisado é sistematicamente
reduzido à metade a cada inspeção realizada.
Figura 4.4: Divisão dos dados na Pesquisa Binária
A Figura 4.4 representa o método de divisão dos dados que ocorre na pesquisa binária. O quadro
inteiro representa o conjunto completo dos dados. As inspeções são feitas no elemento central dos
dados. Se o elemento inspecionado é menor que procurado, o algoritmo descarta todos os elementos
que são maiores que o elemento inspecionado. Ou seja, a metade dos dados é descartada (parte
amarela). O algoritmo segue o mesmo procedimento agora inspecionando o elemento central dos
elementos que sobraram, até encontrar o elemento ou não restarem mais elementos a serem
inspecionados. Utilizando este método, a pesquisa binária consegue localizar o elemento desejado
com desempenho muito melhor que a pesquisa seqüencial. As divisões sucessivas levam a localização
de elemento em tempo logarítmico, conforme veremos a seguir.
Vejamos agora a pesquisa binária usando como exemplo um vetor ordenado de elementos a seguir:
0
1
2
3
4
A D E F G
5 6
J
7
8
M N O
Suponha que o elemento procurado seja o ‘D’.
Suponha também que os limites inferior e superior do vetor seja denotados pelas variáveis inicio e
fim.
No começo da pesquisa inicio = 0 e fim = 8
A pesquisa é iniciada inspecionando o elemento central do Vetor. Este elemento determinado pela
média entre inicio e fim:
meio = (inicio+fim)/2 = 4
Para primeira inspeção meio = 4; Como ‘D’ é menor que ‘G’, toda a metade superior do vetor é
descartada. No algoritmo este descarte é feito recalculando o valor de fim:
fim = meio-1 = 3
O valor de meio é recalculado agora para determinar o meio da metade inferior:
meio = (inicio+fim)/2 = 1
Agora, com meio = 1, o item procurado é encontrado.
O algoritmo completo da pesquisa binária é mostrado na implementação da operação pesquisaBinária
para o TAD Tabela (Figura 4.5).
int pesquisaBinaria( pTabela t, int chave)
{
int inicio,fim,meio;
inicio=0;
fim=t->n-1;
while (inicio<=fim) {
meio=(inicio+fim)/2;
if (chave ==t->itens[meio].codigo){
return meio;
}
else
if (chave < t->itens[meio].codigo){
fim=meio-1;
}
else
inicio=meio+1;
}
return -1;
/* não encontrado */
}
Figura 4.5: Implementação da operação pesquisaBinária
Conforme já mencionado, a pesquisa binária apresenta comportamento logarítmico. A Função de
complexidade de tempo é dada por:
f(n) = log2(n)
Para ilustrar o que significa esta eficiência logarítmica, suponha que você esteja procurando registros
em uma tabela com 1.000.000 de registros. Se você utiliza a pesquisa seqüencial, vai levar em média
(n+1)/2 = ~ 500.000 inspeções para cada pesquisa. Utilizando a pesquisa binária, cada pesquisa vai
ter um custo de log2 1.000.000 = ~20.
Ou seja, usando pesquisa seqüencial realiza-se em media 500.000 inspeções para encontrar um
elemento; ao passo que com a pesquisa binária serão necessárias, em média, apenas 20 (vinte)
inspeções!
Atividade 4.3
1. Desenvolva um programa utilizando o TAD Tabela que
meça o tempo de execução da pesquisa seqüencial. Altere
o código da tabela para aceitar um conjunto de até 100
000 itens. Pesquise por alternativas para medir o tempo de
execução de um programa. Planeje sua estratégia para
medir o tempo.
2. Implemente uma versão recursiva da pesquisa binária.
1.3 TABELAS HASH
Até o momento, discutimos métodos de pesquisa baseados na comparação explícita da chave de
busca. Neste métodos, se pesquisamos algum objeto com chave de pesquisa igual a X, procuramos
até encontrar o objeto com o valor de identificador igual a X. Nesta seção iremos estudar uma
abordagem completamente diferente. Trata-se das tabelas Hash, método também conhecido como
espalhamento.
Embora diferente, o método de espalhamento é bastante simples e intuitivo. A fixação dos conceitos
de endereço e função hash vão facilitar o entendimento do método.
Tabela Hash: O método de espalhamento permite o
armazenamento e recuperação de dados em estruturas onde cada
posição possui um índice. Por exemplo um vetor. Chamaremos
estas estruturas simplesmente de tabela hash.
Endereço: Corresponde ao valor de um índice na tabela. Os
endereços irão variar de 0 até N-1, onde N é o tamanho máximo
da tabela hash.
Função hash: é uma função aritmética que tem como entrada uma
chave e que calcula um valor inteiro de um endereço válido na
tabela Hash.
A função a seguir é um exemplo de função hash.
int h (char * chave){
int tam, i,soma=0;
tam = strlen(chave);
for(i=0;i<tam;i++) {
soma+=abs(chave[i]);
}
return soma%N;
}
Esta função recebe uma string como parâmetro e retorna valores
entre 0 e N-1.
A função abs é da biblioteca da linguagem C e retorna o valor
inteiro correspondente ao código ASCII de um caractere. Para
determinar o valor ser retornado, a função faz um cálculo
aritmético baseado no código ASCII de cada caractere que forma
a string. O valor calculado é o resto entre a soma obtida e N,
que nos dá um valor entre 0 e N-1.
Quando um registro vai ser inserido na tabela, a posição de inserção é determinada pela função Hash,
tomando como entrada a chave de pesquisa utilizada. Normalmente, as chaves de pesquisa usadas em
tabelas Hash são valores alfanuméricos (strings), por exemplo, nomes de pessoas.
Um função Hash pode ser qualquer função aritmética que gere valores de endereços a partir da chave
de pesquisa. No entanto, existem funções Hash melhores que as outras. As seguintes características
devem ser buscadas na definição de uma função Hash:
•
Ser de computação simples e de baixo custo;
•
Gerar valores de endereço de forma uniforme, de maneira a tentar distribuir os dados
uniformemente na tabela. Ou seja, a probabilidade de geração dos endereços entre 0 e N-1,
pela função Hash deve é a mesma.
Para o método re espalhamento a chave de pesquisa deve ser única. Conforme Figura 4.6, a função
hash h calcula um endereço com base no valor da chave k. Se esta chave não for única para os
registros a serem armazenados, o mesmo valor de endereço será fatalmente calculado para dois
registros diferentes.
O princípio básico do método de espalhamento é a geração de endereços dentro da tabela por meio da
função Hash. Esta geração ocorre nas seguintes situações:
(1) Inserção de um registro: Para inserir um registro, a chave (que deve se única) é usada para
calcular o endereço de armazenamento do registro.
(2) Recuperação de um registro: Para recuperar um registro armazenado, com base em um valor
chave de pesquisa. Neste caso a chave informada é usada para determinar o possível
endereço de armazenamento do registro procurado.
Figura 4.6: A função hash determina o índice com base na chave de pesquisa.
Um problema que fatalmente ocorre em funções Hash é o cálculo de um mesmo endereço para dois
valores de chave diferentes. Este problema é chamado de colisão.
Colisão
A colisão em tabelas hash ocorre quando o mesmo endereço na
tabela é calculado para diferentes valores de chave. Por exemplo,
a função Hash
int h (char * chave){
int tam, i,soma=0;
tam = strlen(chave);
for(i=0;i<tam;i++) {
soma+=abs(chave[i]);
}
return soma%N;
}
Retorna o mesmo valor para strings contendo os mesmos
caracteres. Por exemplo, as chaves “maria” e “maira”, iriam
produzir um mesmo valor embora sejam valores diferentes.
A colisão não pode ser evitada, mas deve ser tratada. A seguir veremos como tratar colisões em
implementações de tabelas Hash
1.3.1 Operações de Inserção e Pesquisa em Tabelas Hash
Veremos como é feita a inserção e a pesquisa em uma tabela Hash. Veremos primeiro uma versão
sem tratamento de colisão. Implementaremos estas funções como operações do TAD tabelaHash.
#include"elemento.h"
#define TRUE 1
#define FALSE 0
#define MAXTAB 1000
typedef struct {
int n;
Elemento itens[MAXTAB+1];
} Tabela;
typedef Tabela *pTabela;
int inicializaTabela(pTabela);
int insereElemento(pTabela, Elemento);
int pesquisaElemento(pTabela, char *);
Figura 4.7: TAD TabelaHash sem tratamento de colisão
A Figura 4.7 apresenta o TAD TabelaHash sem tratamento de colisão. A tabela utilizada consiste de
um vetor de registros do tipo Elemento. Apenas lembrando, o tipo Elemento possui os seguintes
campos:
char nome[20];
int codigo;
char telefone[10];
O campo nome será usado como chave de pesquisa. Assim, fica convencionado que os registros
armazenados na tabela não poderão ter o mesmo nome.
Usaremos o campo codigo para determinar se um endereço da tabela está ocupado ou não. Para
tanto, na inicialização da tabela, atribuiremos o valor -1 ao código. O valor -1 no campo código
indicará que o endereço está desocupado.
O código da operação inicializaTabela é mostrado na Figura 4.8. Conforme pode ser observado, a
tabela possui também um contador n que mantém o número de elementos da tabela. Implementamos
também uma função lógica chamada de enderecoOcupado, que retorna TRUE se um endereço
(end) estiver ocupado e FALSE, caso contrário. Esta função é apresentada na Figura 4.8.
int inicializaTabela(pTabela t) {
int register i;
t->n = 0;
for(i=0;i<MAXTAB;i++) {
t->itens[i].codigo=-1;
}
return TRUE;
}
int enderecoOcupado(pTabela t, int end){
if (t->itens[end].codigo==-1) {
return TRUE;
}
return FALSE;
}
Figura 4.8: Inicialização da Tabela Hash e função enderecoOcupado.
A função Hash utilizada é baseada na função h, já apresentada. No entanto, para calcular o valor da
soma, cada caractere foi multiplicado pela sua posição (i+1), evitando a colisão de nomes com
mesmo conjunto de caracteres. A Figura 4.9 apresenta esta implementação.
/* função hash */
int h (char * chave){
int tam, i,soma=0;
tam = strlen(chave);
for(i=0;i<tam;i++) {
soma+=abs(chave[i])*(i+1);
}
return soma%MAXTAB;
}
Figura 4.9: implementação da função hash
A inserção de elementos na tabela segue o seguinte algoritmo:
insere na tabela:
calcula endereço com base na chave do elemento a ser inserido
se endereço estiver ocupado então
imprima("ocorreu uma colisão.")
retorna FALSE
fim se
senão
insere elemento no endereço calculado
fim senão
A implementação da operação de inserção é mostrada na Figura 4.10.
int insereElemento(pTabela t, Elemento e){
int end;
end = h(e.nome);
if (enderecoOcupado(t,end)) {
printf("Ocorreu uma colisão.\n");
return FALSE;
}
t->itens[end]=e;
t->n++;
return TRUE;
}
Figura 4.10: Implementação da operação insereElemento.
Note que, se o endereço calculado já estiver ocupado, ocorre uma colisão que não é tratada. Um aviso
de colisão é enviado ao usuário e a inserção do novo elemento simplesmente não ocorre.
Conforme já mencionado, colisões em tabelas Hash são inevitáveis, mesmo para uma tabela 10
vezes maior que o número de registros a ser armazenado, a probabilidade de colisões é ainda muito
grande. Este comportamento é ilustrado pelo paradoxo do aniversário.
Paradoxo do aniversário: Se tomarmos um grupo de mais de 25
pessoas de forma totalmente aleatório, a probabilidade de que haja
entre estas pessoas pelo menos duas que fazem aniversário na
mesma data do ano é maior que 50%. Esta medida é curiosamente
verdadeira, considerando-se que a data de aniversário de uma
pessoa é uma variável aleatória, estas datas deveriam ser
uniformemente distribuídas entre os dias do ano.
O paradoxo do aniversário está associado com tabelas Hash. Considere uma tabela Hash com 365
endereços disponíveis. Cada endereço corresponde a um dia do ano. Ao inserirmos 25 registros nesta
tabela, usando uma função h totalmente aleatória, a chance de haver uma colisão é de 50%.
Na pesquisa por um elemento, um valor de chave deve ser informado. Com base neste valor o
endereço é calculado. Se o endereço estiver ocupado, o valor do campo nome do elemento é
comparado com a chave de pesquisa para verificar se o elemento que lá está é realmente o elemento
procurado. Neste caso o valor de end é retornado. Caso contrário o elemento procurado não existe na
tabela. A operação de pesquisa é apresentada na Figura 4.11.
int pesquisa(pTabela t, char *chave){
int end;
end = h(chave);
if (enderecoOcupado(t,end)) {
if(strcmp(t->itens[end].nome,chave)==0) {
return end;
}
}
return -1;
}
Figura 4.11: Implementação da operação pesquisa.
1.3.2 Tratamento de Colisões
Na implementação que realizamos até agora, quando uma colisão ocorre, o dado simplesmente não é
inserido. Evidentemente este não é o comportamento esperado de nenhum sistema de armazenamento
de informações. Assim, ao invés de simplesmente abortar a inserção iremos tratar o evento da colisão
permitindo a inserção de vários elementos com chaves diferentes que mapeiam para o mesmo
endereço.
Conforme observado na TAD TabelaHash apresentado, na inserção, quando o endereço vazio é
obtido, o elemento é inserido no mesmo. A tabela itens é um vetor de Elemento e cada endereço
se refere a apenas um elemento.
Veremos duas formas de tratar a colisão:
(1) Com listas encadeadas
(2) Com endereçamento aberto
No tratamento de colisões com listas encadeadas, a estrutura da tabela e alterada. Ao invés de uma
tabela de registros é definida uma tabela de listas encadeadas, onde cada lista encadeada será o
conjunto de registros inseridos cujas chaves de pesquisa foram mapeadas para o mesmo endereço. A
Figura 4.12 ilustra esta abordagem.
Figura 4.12: Tratamento de Colisão com Listas Encadeadas
A Tabela é formada de um vetor de ponteiros para N listas encadeadas. Agora, na inserção, o
endereço end é calculado e o elemento é inserido na lista encadeada apontada pelo ponteiro da
posição end.
A Figura 4.13 apresenta a implementação da interface do TAD tabelaHash com com tratamento de
colisão por meio de lista encadeada. Este TAD utiliza como cliente o tadLista implementado no
Capítulo 3. A única modificação neste Tad foi na operação pesquisa que agora utiliza o campo nome
do registro Elemento como chave e recebe a string chave como parâmetro para realizar a pesquisa. O
TadLista é reapresentado na Figura 4.14.
#include "tadLista.h"
#define TRUE 1
#define FALSE 0
#define MAXTAB 1000
typedef struct {
int n;
Lista itens[MAXTAB+1];
} Tabela;
typedef Tabela *pTabela;
int inicializaTabela(pTabela);
int insereElemento(pTabela, Elemento);
Elemento pesquisaElemento(pTabela, char *);
Tabela: 4.13: Interface do TAD Tabela Hash
/* tadLista.h */
#include"elemento.h"
typedef struct nodo{
Elemento e;
struct nodo* prox;
} *Lista;
void inicializaLista(Lista *);
void insereNaLista(Lista *, Elemento );
Elemento pesquisaNaLista(Lista , char *chave);
Elemento removeDaLista(Lista *, int );
Figura 4.14: Interface do TAD Lista Encadeada
A Figura 4.15 apresenta a implementação das operações do TAD TabelaHash.
int inicializaTabela(pTabela t) {
int register i;
t->n = 0;
/* Inicializa todas as listas contidas na tabela */
for(i=0;i<MAXTAB;i++) {
inicializaLista(&t->itens[i]);
}
return TRUE;
}
int insereElemento(pTabela t, Elemento e){
int end;
end = h(e.nome);
insereNaLista(&(t->itens[end]),e);
t->n++;
return TRUE;
}
Elemento pesquisaElemento(pTabela t, char *chave){
int end;
end = h(chave);
return pesquisaNaLista(t->itens[end],chave);
}
Figura 4.15: operações inicializaTabela, insereElemento e pesquisaElemento
1.3.3 Tratamento de Colisão usando endereçamento Aberto
Outra abordagem para tratar as colisões é o uso de endereçamento aberto (open addressing) . Nesta
abordagem, a estrutura de dados da tabela é a mesma originalmente estabelecida (um vetor de
registros). A técnica de endereçamento aberto consiste nos seguintes procedimentos:
Inserção:
(1) Calcular o endereço usando a função Hash para o valor de chave do registro
(2) Se o endereço estiver ocupado, procurar nas posições vizinhas ao endereço calculado uma
posição vazia.
Pesquisa:
(1) Calcular o endereço usando a função Hash e a chave de pesquisa fornecida
(2) Procurar, a partir do endereço até:
a. Encontrar o elemento procurado (pesquisa com sucesso)
b. Encontrar uma posição vazia ou o fim da tabela (pesquisa sem sucesso)
Atividade
Modificar a implementação inicial de Hash (sem tratamento de
colisão) para suportar colisões com a técnica de endereçamento
aberto.
2
ORDENAÇÃO EM MEMÓRIA PRIMÁRIA
Olá. Neste capítulo chegaremos ao fim de nosso estudo na
disciplina de TPA. Reservei para a última etapa o tema
Ordenação. A ordenação em computação reúne um conjunto
de algoritmos que permite ordenar um conjunto de dados
segundo uma determinada chave de ordenação. Neste capítulo
iremos estudar alguns desses principais algoritmos. Se você
vasculhar a Internet vai encontrar a maioria destes algoritmos
implementados. Assim você poderá se perguntar para que
estudamos estes mecanismos se as suas implementações já
estão prontas? E mais, porque estudar vários métodos de
ordenação se existe um particularmente que é mais rápido que
os outros? A resposta é simples: Porque estes algoritmos e suas
variações reúnem técnicas de programação que são de muita
valia na resolução de outros problemas, alem de tocarem em
aspectos complexos que, ao serem absorvidos pelo estudante
são capazes de aprofundar sua capacidade de raciocínio e
habilidades em desenvolver programas. Vamos a ele então.
2.1 CONCEITOS BÁSICOS DE ORDENAÇÃO
A ordenação consiste em rearranjar um conjunto de objetos em ordem crescente ou decrescente,
levando-se em conta uma chave ordenação. A ordenação possui motivações óbvias. Em geral,
colocamos dados de forma ordenada para:
•
Facilitar a obtenção de uma informação ao se observar um conjunto de dados. Por exemplo, a
visualização da classificação de candidatos em um concurso fica mais fácil se a lista de
candidatos estiver ordenada pelo número de pontos que fizeram.
•
Facilitar a recuperação de uma informação . Por exemplo: obter os pontos que um candidato
em um concurso fez, sabendo o seu nome, fica mais fácil se a lista de candidatos estiver
ordenada por nome.
A ordenação pode ser feita considerando diferentes tipos de dados para a chave, inteiros, reais,
strings. O que importa é estabelecer as comparações nos algoritmos de acordo com o tipo de dado
da chave de ordenação. Na ordenação de um arranjo de registros, com a tabela de elementos usada
no capítulo anterior, apenas a chave de ordenação é usada. Os demais campos do registro são
irrelevantes.
2.1.1 Operações Típicas de processos de Ordenação
Nos diferentes métodos de ordenação, algumas operações ocorrem com mais freqüência e o
desempenho dos métodos está geralmente associado com a realização dessas operações. As duas
operações que mais afetam o desempenho dos algoritmos de ordenação são as operações de troca e de
comparação:
•
Troca: Consiste na troca de valores entre duas posições do arranjo que está sendo ordenado.
Esta operação tem custo elevado e é a que mais afeta o desempenho dos algoritmos. A
operação de troca geralmente é suportada por uma função. A Figura 5.1 apresenta uma
implementação da função troca
•
Comparação: consiste nas comparações entre dois valores contidos em posições do arranjo
com o objetivo de saber qual dentre as duas é menor. Embora de menor custo, esta operação
também afeta bastante o desempenho dos algoritmos devido ao fato de serem feitas muitas
comparações nos processos de ordenação.
void troca(int *x, int *y){
int aux;
aux = *x;
*x=*y;
*y=aux;
}
Figura 5.1: Implementação da função troca
2.2 MÉTODOS DE ORDENAÇÃO
Iremos estudar 5 métodos de ordenação diferentes neste capítulo. A saber:
(1)
(2)
(3)
(4)
(5)
Seleção
Inserção
Bolha
Shell
Quicksort
Dependendo da aplicação e situação, o uso de um método pode ser mais conveniente que o outro. Em
geral, o quicksort apresenta-se com melhor desempenho na maioria das situações. O Método da bolha
é o menos eficiente. Porem a sua simplicidade o torna conveniente para ordenar pequenos vetores
(com tamanho menor que 20). A seguir discutimos cada um destes algoritmos individualmente.
2.2.1 Ordenação por Seleção
Este método tem como estratégia selecionar o menor elemento remanescente do conjunto não
ordenado e mover este elemento para sua posição correta. Por exemplo, suponha um arranjo com 4
elementos.
O processo de ordenação por seleção determina quem é o menor elemento e o insere na primeira
posição do vetor. Para tanto, o elemento que estava na posição inicial precisa ser colocado na posição
onde estava o menor. Em seguida o segundo menor é encontrado e inserido na segunda posição do
arranjo. O Algoritmo segue assim sucessivamente até encontrar o último elemento e inseri-lo na
última posição.
A Figura 5.2 apresenta a implementação do algoritmo de seleção.
Implementação:
void selecao (int a[], int n){
int register i,j;
int min;
for(i=0;i<n-1;i++) {
min =i;
for ( j=i+1;j<n;j++) {
if (a[j] <a[min]) {
min =j;
}
}
troca(&a[min],&a[i]);
imprimevetor(a,n);
}
}
Figura 5.2: Implementação da Ordenação por Seleção
Tomando como exemplo o arranjo
int B[] = {10,3,7,20,1,2,11,0,5,4};
a execução da função seleção irá imprimir a seguinte sequencia de valores intermediários para o
arranjo B até a sua ordenação completa:
10
0
0
0
0
0
0
0
0
0
3
3
1
1
1
1
1
1
1
1
7
7
7
2
2
2
2
2
2
2
20 1
20 1
20 3
20 3
3 20
3 4
3 4
3 4
3 4
3 4
2
2
2
7
7
7
5
5
5
5
11
11
11
11
11
11
11
7
7
7
0 5 4
10 5 4 (fim
10 5 4 (fim
10 5 4 (fim
10 5 4 (fim
10 5 20 (fim
10 7 20 (fim
10 11 20 (fim
10 11 20 (fim
10 11 20 (fim
da
da
da
da
da
da
da
da
da
interação
interação
interação
interação
interação
interação
interação
interação
interação
i=0)
i=1)
i=2)
i=3)
i=4)
i=5)
i=6)
i=7)
i=8)
O algoritmo de seleção utiliza o índice i como limite inferior da parte do arranjo que ainda não está
ordenado (de i até n-1). A medida que o arranjo vai sendo ordenado este limite vai avançando (laço
mais externo). O laço mais interno tem como objetivo encontrar o menor elemento dentre os
elementos que ainda não foram ordenados. min é iniciado sempre com o valor de i. Em seguida o
laço mais interno (do j) se encarrega de verificar se no restante do vetor (posições de i+1 até n-1)
existe um valor menor que a[min]. Toda vez que isso ocorre, o valor de min é atualizado. Ao final
de um laço mais interno, a variável min vai conter o índice do menor valor no arranjo dentre os
elementos que não foram ainda ordenados.
Conforme pode ser visto na saída do programa, na primeira interação de i, i=0, o menor elemento
contido no vetor é localizado e inserido na posição 0. Esta inserção é feita pela operação de troca que
ocorre ao final de cada iteração do laço mais externo.
Note que as trocas ocorrem independentemente de haver sido encontrado um valor menor que a[i].
Neste caso haverá uma troca entre duas posições idênticas pois o valor de min vai ser igual a i. Isso
ocorreu nas iterações 6,7 e 8. Caso seja importante melhorar o desempenho do algoritmo esta troca
entre posições iguais pode ser evitada comparando-se o valor de min com i. Se estes forem iguais a
troca não precisa ser feita.
2.2.2 Método da Inserção
Este método é similar ao que o jogador de cartas utiliza: Cada elemento a ser ordenado é
reposicionado entre os ordenados movendo-se os elementos maiores que ele uma posição para a
direita e posteriormente inserindo-o na posição vaga.
A Figura 5.3 apresenta a implementação do algoritmo de Inserção.
void insercao(int a[], int n) {
int i,j,x;
for(i=1;i<n;i++) {
x=a[i];
j=i-1;
while((j>=0) && (a[j]>x)) {
a[j+1]=a[j];
j = j-1;
imprimevetor(a,n);
}
a[j+1]=x;
imprimevetor(a,n);
}
}
Figura 5.3: Implementação do método de ordenação por Inserção
A função imprimevetor é chamada a cada iteração do laço while (mais interno) e ao fim de cada
laço mais externo também . A execução desta função sobre o arranjo
int B[] = {10,3,7,20,1,2,11,0,5,4};
produz a seguinte saída:
10 3 7 20 1 2 11 0 5 4
10 10 7 20 1 2 11 0 5 4
3 10 7 20 1 2 11 0 5 4 (fim
3 10 10 20 1 2 11 0 5 4
3 7 10 20 1 2 11 0 5 4 (fim
3 7 10 20 1 2 11 0 5 4 (fim
3 7 10 20 20 2 11 0 5 4
3 7 10 10 20 2 11 0 5 4
3 7 7 10 20 2 11 0 5 4
3 3 7 10 20 2 11 0 5 4
1 3 7 10 20 2 11 0 5 4 (fim
1 3 7 10 20 20 11 0 5 4
1 3 7 10 10 20 11 0 5 4
1 3 7 7 10 20 11 0 5 4
1 3 3 7 10 20 11 0 5 4
1 2 3 7 10 20 11 0 5 4 (fim
1 2 3 7 10 20 20 0 5 4
1 2 3 7 10 11 20 0 5 4 (fim
1 2 3 7 10 11 20 20 5 4
1 2 3 7 10 11 11 20 5 4
1 2 3 7 10 10 11 20 5 4
1 2 3 7 7 10 11 20 5 4
1 2 3 3 7 10 11 20 5 4
1 2 2 3 7 10 11 20 5 4
1 1 2 3 7 10 11 20 5 4
0 1 2 3 7 10 11 20 5 4 (fim
0 1 2 3 7 10 11 20 20 4
0 1 2 3 7 10 11 11 20 4
0 1 2 3 7 10 10 11 20 4
0 1 2 3 7 7 10 11 20 4
0 1 2 3 5 7 10 11 20 4 (fim
0 1 2 3 5 7 10 11 20 20
0 1 2 3 5 7 10 11 11 20
0 1 2 3 5 7 10 10 11 20
0 1 2 3 5 7 7 10 11 20
0 1 2 3 5 5 7 10 11 20
0 1 2 3 4 5 7 10 11 20 (fim
da iteração i=1)
da iteração i=2)
da iteração i=3)
da iteração i=4)
da iteração i=5)
da iteração i=6)
da iteração i=7)
da iteração i=8)
da iteração i=9)
Na execução da função o laço mais externo é usado para delimitar os elementos do arranjo ainda não
inspecionados. A variável x é usada para guardar o valor do elemento a ser inserido (a[i]). Na
primeira iteração este elemento é o 3. Na segunda é o 7. Na terceira é o 10 e assim por diante. Nem
sempre o elemento em x será substituído. Por exemplo, na iteração i=3, o elemento x é igual a 10 e
não terá a sua posição alterada. O laço while tem a finalidade de percorrer o arranjo nas posições
entre (i-1 e 0) procurando valores menores que x. À medida que estes valores são encontrados eles
vão sendo deslocados para a direita. O laço while termina quando é encontrado um elemento menor
que x ou o limite do vetor é atingido.
2.2.3 Método da Bolha
O Método da Bolha consiste em percorrer o vetor trocando os elementos adjacentes caso necessário.
Por este motivo, este método realiza muitas trocas.
A implementação deste método é apresentada na Figura 5.4.
void bolha ( int a[],int n){
int register i,j;
for(i=n-1;i>0;i--) {
for(j=1;j<=i;j++) {
if(a[j-1]>a[j]){
troca(&a[j-1],&a[j]);
imprimevetor(a,n);
}
}
}
}
Figura 5.4: Método da Bolha
A execução do método da bolha sobre o vetor
int B[] = {10,3,7,20,1,2,11,0,5,4}; produz a seguinte saída:
10 3 7 20 1 2 11 0 5 4
3 10 7 20 1 2 11 0 5 4
3 7 10 20 1 2 11 0 5 4
3 7 10 1 20 2 11 0 5 4
3 7 10 1 2 20 11 0 5 4
3 7 10 1 2 11 20 0 5 4
3 7 10 1 2 11 0 20 5 4
3 7 10 1 2 11 0 5 20 4
3 7 10 1 2 11 0 5 4 20
3 7 1 10 2 11 0 5 4 20
3 7 1 2 10 11 0 5 4 20
3 7 1 2 10 0 11 5 4 20
3 7 1 2 10 0 5 11 4 20
3 7 1 2 10 0 5 4 11 20
3 1 7 2 10 0 5 4 11 20
3 1 2 7 10 0 5 4 11 20
3 1 2 7 0 10 5 4 11 20
3 1 2 7 0 5 10 4 11 20
3 1 2 7 0 5 4 10 11 20
1 3 2 7 0 5 4 10 11 20
1 2 3 7 0 5 4 10 11 20
1 2 3 0 7 5 4 10 11 20
1 2 3 0 5 7 4 10 11 20
1 2 3 0 5 4 7 10 11 20
1 2 0 3 5 4 7 10 11 20
(troca
(troca
(troca
(troca
(troca
(troca
10
10
20
20
20
20
e
e
e
e
e
e
3)
7)
1)
2)
11)
0)
1
1
0
2
0
1
0
2
2
3
3
3
4
4
4
5
5
5
7 10 11 20
7 10 11 20
7 10 11 20
2.2.4 Desempenho dos métodos de Seleção, Inserção e Bolha
Para a análise de desempenho de métodos de ordenação deve levar em contar o número de
comparações e o número de trocas realizadas.
O Método da Seleção realiza aproximadamente n2/2 comparações e n trocas, pois para cada i de 1
até n-1 ocorre uma troca e n-1 comparações. Assim temos que no final ocorrem n-1 trocas e (n-1 +
(n-2) + ... 2 +1 = n(n-1)/2 comparações.
O método da Inserção realiza aproximadamente n2/4 comparações e n2/8 trocas no caso médio. No
entanto, esse método é linear para arranjos parcialmente ordenados, o que o torna um método
conveniente para estes casos.
O método da Bolha realiza n2/2 comparações e n2/2 trocas no caso médio e no pior caso.
Realize testes de mesa para os métodos de seleção, inserção e
bolha para os seguintes vetores:
A = {10,0,3,2,5}, B={5,4,3,2,1}, C={1,1,2,2,0,0}.
2.2.5 Método de Shell
O método que estudaremos agora foi inventado por Criado por Donald Shell em 1959. Conforme
comentado na Seção 5.2.4, o método da Inserção é bastante eficiente ao ordenar arranjos que já estão
parcialmente ordenados. Shell observou esta característica e criou um método onde o método de
inserção é aplicado sucessivamente.
Em seu método, o algoritmo de inserção é aplicado para ordenar subconjuntos do arranjo completo.
Estes subconjuntos são pegos considerando uma distância entre os elementos. Para cada execução do
método de Inserção é considerada um distância d. d é iniciado com um valor que vai sendo
decrementado até chegar a 1. Para cada valor de d, os elementos do arranjo localizados a uma
distância d entre si são ordenados.
Por exemplo, em um arranjo,
a = {a0,a1,a2,a3,a4,a5,a6,a7,a8,a9}
e considerando uma série de distâncias d = {5,3,1}. Nas iterações com distância d = 5, o método da
inserção será aplicado aos elementos do arranjo localizados a uma distância 5 entre si. Os elementos
são pegos do arranjo a partir da posição a0, na primeira iteração, a1 na segunda, a2 na terceira e assim
sucessivamente.
Assim para a distância 5 teremos a ordenação dos elementos:
{a0,a5} (primeira iteração)
{a1,a6} (segunda iteração)
{a2,a7} (terceira iteração)
{a3,a8} (quarta iteração)
{a4,a9} (quinta iteração)
Para a distância 3 teremos a ordenação dos elementos:
{a0,a3,a6,a9} (primeira iteração)
{a1,a4,a7} (segunda iteração)
{a2,a5,a8} (terceira iteração)
{a3,a6,a9} (quarta iteração)
{a4,a7} (quinta iteração)
{a5,a8} (sexta iteração)
{a6,a9} (sétima iteração)
Para a distância 1 teremos a ordenação do arranjo completo
{a0,a1,a2,a3,a4,a5,a6,a7,a8,a9} (primeira iteração)
A cada iteração a distância d é reduzida de acordo com alguma seqüência. Na utiliza iteração esta
distância é reduzida a 1. Este passo corresponde ao método de inserção original.
Vejamos um exemplo concreto, considerando o arranjo a = {35,28,16,07,12,08,04} e
utilizando a seqüência de distâncias {3,1}:
Para d = 3 o método ordena os elementos que estão a uma distância 3 entre si. Na tabela abaixo estes
elementos estão em negrito:
35
28
16
07
12
08
04
35 está ordenado, 7 é comparado
07
28
16
35
12
08
04
{07,35} está
comparado
04
28
16
07
12
08
35
{04,07,35} está ordenado
04
28
16
07
12
08
35
28 está ordenado, 12 é comparado
04
12
16
07
28
08
35
{12,28} está ordenado
04
12
16
07
28
08
35
16 está ordenado, 35 é comparado
04
12
08
07
28
16
35
{08,16} está ordenado
ordenado,
4
é
Após a ordenação parcial feita com d=3, a distância é reduzida a 1 e o vetor é completamente
ordenado.
Para implementação do método de Shell, implementa-se um função (Shell) que corresponde ao
método de inserção parametrizado pela distância. Esta implementação é apresentada na Figura 5.5.
shell(int A[], int n, int d) {
int i,j,x;
for(i=d;i<n;i++) {
x=A[i];
j=i-d;
while((j>=0) && (A[j]>x)) {
A[j+d]=A[j];
j = j-d;
imprimevetor(A,n);
}
A[j+d]=x;
imprimevetor(A,n);
}
}
Figura 5.5: Implementação da função Shell
Note que a função shell corresponde exatamente à função insercao, se substituirmos o d pelo
valor 1.
Para concluirmos a implementação do método de Shell basta agora implementarmos uma função que
gere a seqüência de distâncias e a chave a função Shell para cada distância da série. A Figura 5.6
apresenta uma implementação da função shellSort, que executa o método com a série {5,2,1}.
void shellsort1(int a[], int n) {
int p;
int d[3] = {5,2,1};
for (p=0;p<3;p++) {
shell(a,n,d[p]);
}
}
Figura 5.6: Implementação do método de Shell com distâncias 5,2 e 1
A execução de shellsort1 sobre o vetor
int B[] = {10,3,7,20,1,2,11,0,5,4}; produz a seguinte saída:
10 3 7 20
Distancia d=
10 3 7 20
2 3 7 20
2 3 7 20
2 3 7 20
2 3 0 20
2 3 0 20
2 3 0 5
2 3 0 5
Distancia d=
2 3 2 5
0 3 2 5
0 3 2 5
0 3 2 5
0 3 1 5
0 3 1 5
0 3 1 5
0 3 1 5
0 3 1 5
0 3 1 5
0 3 1 5
0 3 1 5
0 3 1 5
0 3 1 4
Distancia d=
0 3 1 4
0 3 3 4
0 1 3 4
0 1 3 4
0 1 3 4
0 1 3 3
0 1 2 3
0 1 2 3
0 1 2 3
0 1 2 3
0 1 2 3
0 1 2 3
1
5
1
1
1
1
1
1
1
1
2
1
1
1
2
2
2
2
2
2
2
2
2
2
2
1
2
2
2
2
4
4
4
4
4
4
4
4
2 11
10
10
10
10
10
10
10
10
11
11
11
11
11
11
11
11
10
10
10
10
10
10
10
10
7
7
7
7
5
5
11
11
11
11
11
11
11
11
11
11
11
11
11
11
5
5
5
5
5
5
5
5
5
5
5
5
0
5
4
0 5
0 5
0 5
7 5
7 5
7 20
7 20
7 20
4
4
4
4
4
4
4
4
7
7
7
7
7
7
7
10
10
10
10
7
7
7
20
20
20
20
20
20
20
20
20
20
20
20
20
20
4
4
4
4
4
4
4
4
4
4
10
10
10
10
11 7 20 10
11 7 20 10
11 7 20 10
11 7 20 10
11 7 20 10
11 7 20 10
11 7 20 10
11 7 20 10
11 7 20 10
11 11 20 10
7 11 20 10
7 11 20 10
0
0
0
1
1
1
2
2
2
3
3
3
4
4
4
5
5
5
7 11 20 20
7 11 11 20
7 10 11 20
Conforme pode ser observado, a seqüência de distâncias pode variar. A única restriçã é que termine
com 1. Não existe uma seqüência ideal. Donald Knuth (vale a pena ver
http://pt.wikipedia.org/wiki/Donald_Knuth), mostrou empiricamente que a seqüência
( 1,4,
13,40,121,364,1093..) apresenta eficiência 20 % maior que outras seqüências.
A Figura 5.7 apresenta a função shellsort2 que executa a função Shell usando esta seqüência.
// executa o shell sort a seqüência de Knuth ( 1,4, 13,40,121,364,1093..)
void shellsort2(int a[],int n) {
int i,p=0;
int d[MAX/9];
/* se o tamanho do vetor é menor que 9 */
if((n/9)<1){
p =1;
d[0]=1;
}
else {
/* gera a seqüência de distancias e guarda no vetor d */
for (i=1;i<=n/9;i=3*i+1) {
d[p] =i;
p++;
}
}
for (i=p-1;i>=0;i--) {
shell(a,n,d[i]);
}
}
Figura 5.7: Implementação do método de Shell usando a seqüência de Knuth
2.2.6 O Método Quicksort
Até o momento, foram estudados métodos de ordenação cuja função de complexidade é próxima de
n2. Ou seja, complexidade quadrática. Nos melhores casos, o método da inserção e Shell pode chegar
próximo de um comportamento linear. O método quicksort baseia-se em uma estratégia de dividir
para conquistar (vide pesquisa binária), tornando-o assim um método que apresenta complexidade
logarítimica (sublinear), no caso médio. Este comportamento do quicksort o torna um método de
ordenação extremamente rápido.
O algoritmo Quicksort foi inventado por C.A.R. Hoare em 1960, durante visita a Universidade de
Moscou (Russia), ainda como estudante.
A idéia fundamental do quicksort consiste em:
First, the sequence to be sorted a is partitioned into two parts, such that all elements of the first part b
are less than or equal to all elements of the second part c (divide). Then the two parts are sorted
separately by recursive application of the same procedure (conquer). Recombination of the two parts
yields the sorted sequence (combine). Figure 1 illustrates this approach.
Primeiro dividir: a seqüência a ser ordenada a é particionada em duas partes b e c, de tal modo que
todos os elementos da primeira parte b são menores ou iguais a todos os elementos da segunda parte
c. Em seguida conquistar: as duas partes são ordenadas separadamente por meio da aplicação
recursiva do mesmo procedimento. Por último recombinar. A recombinação das duas partes
ordenadas em separado produz uma seqüência também ordenada, dado que os elementos da primeira
parte b são menores ou iguais a todos os elementos da segunda parte c.
O processo de particionamento da seqüência é feita por meio da escolha de um elemento pivô. Por
exemplo, Seja o arranjo {f,e,d,h,a,c,g,b} e o valor d como o elemento escolhido para fazer a
primeira partição. O elemento escolhido é chamado de pivô.
Após a primeira iteração com o valor d como pivô teremos a seguinte configuração para o vetor:
{b,c,a,d,h,e,g,f}
Neste passo o processo é repetido para cada sub vetor [b,c,a] e [h,e,g,f]
A Figura 5.8 apresenta uma implementação da operação de particionamento. Nesta implementação o
pivô é sempre o elemento do meio do vetor.
void particiona(int a[], int esq,int dir, int *pi, int *pj) {
int x;
int i,j;
i = esq;
j = dir;
x = a[(i+j)/2]; // obtem o pivo desta particao
printf("O pivo é %d da pos. %d\n",x,(i+j)/2);
do {
while((x > a[i]) && (i<dir)) {
i++;
}
while ((x < a[j]) && (j>esq)){
j--;
}
if(i<=j) {
troca(&a[i],&a[j]);
i++;
j--;
}
} while(i< j);
*pi = i;
*pj = j;
}
Figura 5.8: função particiona
A Figura 5.9 apresenta a função ordenaQS que aplica o método sobre um arranjo com limites esq e
dir.
void ordenaQS(int a[], int esq, int dir) {
int i,j;
particiona(a, esq,dir, &i,&j);
imprimevetor(a,16);
if(esq<j)
ordenaQS(a,esq,j);
if (dir>i)
ordenaQS(a,i,dir);
}
Figura 5.9: Implementação da função ordenaQS
A implementação da função quicksort, apresentada na Figura 5.10 consiste apenas no encapsulamento
da função ordenaQS em uma função cujos parâmetros são apenas o arranjo e seu tamanho.
void quicksort(int a[],int n) {
ordenaQS(a,0,n-1);
}
Figura 5.10: implementação da função quicksort
1 Realizar os experimentos com os 5 métodos de ordenação
estudados. No caso do shellsort utilizar a seqüência de Knuth.
a) Realizar testes com todos os métodos para vetores de tamanho
20000, 40000, 60000, 80000, 100000, 150000, 200000, 250000,
300000, 350000, 400000 e 500000.
b) Utilizar um software que trace gráficos (Excel, por exemplo) e
traçar um gráfico de desempenho dos métodos utilizados. O
gráfico deve ter os seguintes eixos: eixo x: tamanho do vetor. Eixo
y: tempo de execução. Colocar as curvas de todos os métodos no
mesmo gráfico para facilitar a comparação.
c) Fazer uma análise dos resultados obtidos (descritiva).
2. Sabemos que a eficiência do Shellsort depende da seqüência de
distâncias utilizada. Assim, neste exercício, primeiramente você
deve inventar uma seqüência de distâncias sua para ser utilizada
no Shellsort. Posteriormente, escreva uma função myShellsort
que execute o Shellsort com uma seqüência produzida por você.
Invente uma seqüência sua! Você pode utilizar a mesma estrutura
que foi utilizada para as funções shelsort1 e shellsort2. Compare
os resultados de tempo obtidos com a sua seqüência com os
obtidos com a seqüência de Knuth.