ATPS Classificação E Pesquisa, Etapas 2 E 4

Introdução

Etapa 2

Antes de mais nada, apresentarei o código-fonte dos algoritmos de pesquisa e ordenação utilizados, e um breve comentário sobre eles.

Busca Linear (ou Busca Sequencial)

1 Análise de Complexidade

No melhor caso, o elemento a ser buscado é encontrado logo na primeira tentativa da busca. No pior caso, o elemento a ser buscado encontra-se na última posição e são feitas N comparações, sendo N o número total de elementos. No caso médio, o elemento é encontrado após N/2 comparações. O algoritmo de busca linear é um algoritmo O(n).

1 Código em C

/**

* Retorna -1 caso não encontre ou a posição

* caso encontre.

*/

int procura(char vetor[], int tamanho, char elementoProcurado) {

int i;

for (i = 0; i < tamanho; i++) {

if (vetor[i] == elementoProcurado) {

return i;

}

}

return -1;

}

Busca Binária (ou Pesquisa Binária)

2 Análise de Complexidade

A complexidade desse algoritmo é da ordem de Θ(log2 n), em que n é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é O(n).

1 Código em C

//em C para se passa um vetor como parâmetro para uma função, tem que se passar o ponteiro do vetor

int PesquisaBinaria ( int *array, int chave , int N)

{

int inf = 0; //Limite inferior (o primeiro elemento do vetor em C é zero )

int sup = N-1; //Limite superior (termina em um número a menos 0 à 9 são 10 numeros )

int meio;

while (inf v[i + 1])

{swapbubble(v, i);

trocou = 1;

}

}while(trocou);

}

Insertion Sort

Insertion sort, ou ordenação por inserção, é um simples algoritmo, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer

Análise de Complexidade

Menor número de trocas e comparações entre os algoritmos de ordenação O(n) quando o vetor está ordenado. Pior caso O(n²).

Código em C

void insertionSort(int v[], int n)

{

int i, j, chave;

for(j=1; j= 0 && v[i] > chave)

{

v[i+1] = v[i];

i--;

}

v[i+1] = chave;

}

}

Shell Sort

Criado por Donald Shell em 1959, publicado pela Universidade de Cincinnati, Shell sort é o mais eficiente algoritmo de ordenação dentre os de complexidade quadrática. É um refinamento do método de inserção direta. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção.

Análise de Complexidade

No pior caso, depende da sequênciado gap. Melhor conhecida: O(nlog2n).

2 Código em C

void shellSort(int * vet, int size) {

int i , j , value;

int gap = 1;

do {

gap = 3*gap+1;

} while(gap < size);

do {

gap /= 3;

for(i = gap; i < size; i++) {

value =vet[i];

j = i - gap;

while (j >= 0 && value < vet[j]) {

vet [j + gap] =vet[j];

j -= gap;

}

vet [j + gap] = value;

}

} while ( gap > 1);

}

Selection Sort

O selection sort (do inglês, ordenação por seleção) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

Análise de Complexidade

O algoritmo possui complexidade O(n2) enquanto que, por exemplo, os algoritmos HeapSort e MergeSort possuem complexidades O(nlogn).

Código em C

void selection_sort(int num[], int tam) {

int i, j, min;

for (i = 0; i < (tam-1); i++) {

min = i;

for (j = (i+1); j < tam; j++) {

if(num[j] < num[min]) {

min = j;

}

}

if (i != min) {

int swap = num[i];

num[i] = num[min];

num[min] = swap;

}

}

}

Heapsort

O algoritmo heapsort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por seleção.

Análise de Complexidade

Tem um desempenho em tempo de execução muito bom em conjuntos ordenadosaleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Alguns algoritmos de ordenação rápidos têm desempenhos espetacularmente ruins no pior cenário, quer em tempo de execução, quer no uso da memória. O Heapsort trabalha no lugar e o tempo de execução em pior cenário para ordenar n elementos é de O (n lg n). Lê-se logaritmo (ou log) de "n" na base 2. Para valores de n, razoavelmente grande, o termo lg n é quase constante, de modo que o tempo de ordenação é quase linear com o número de itens a ordenar.

Características

Comparações no pior caso: 2n log2n + O(n) é o mesmo que 2n lgn + O(n)

Trocas no pior caso: n log2n + O(n) é o mesmo que n lgn + O(n)

Melhor e pior caso: O(n log2n) é o mesmo que O(n lgn)

Código em C

void heapsort(tipo* a, int n)

{

int i = n/2, pai, filho;

tipo t;

for (;;)

{

if (i > 0)

{

i--;

t = a[i];

}

else

{

n--;

if (n == 0)

return;

t = a[n];

a[n] = a[0];

}

pai = i;

filho = i*2 + 1;

while (filho < n)

{

if ((filho + 1 < n) && (a[filho + 1] > a[filho]))

filho++;

if (a[filho] > t)

{

a[pai] = a[filho];

pai = filho;

filho = pai*2 + 1;

}

else

break;

}

a[pai] = t;

}

}

Quick Sort

O algoritmo Quicksort é um método de ordenação muito rápido e eficiente, inventado em 1960. Foi criado o 'Quicksort ao tentartraduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rapidamente. Foi publicado em 1962 após uma série de refinamentos.

O Quicksort é um algoritmo de ordenação por comparação não-estável.

Análise de Complexidade

Complexidade de tempo: θ(n lg2 n) no melhor caso e no caso médio; θ(n2) no pior caso;

Complexidade de espaço: θ(lg2 n) no melhor caso e no caso médio e θ(lg2 n) no pior caso.

PS: R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade θ(lg2 n) no pior caso.

Código em C

void quickSort( int a[], int l, int r)

{

int j;

if( l < r )

{

// divide and conquer

j = partition( a, l, r);

quickSort( a, l, j-1);

quickSort( a, j+1, r);

}

}

int partition( int a[], int l, int r) {

int pivot, i, j, t;

pivot = a[l];

i = l; j = r+1;

while( 1)

{

do ++i; while( a[i] = j ) break;

t = a[i]; a[i] = a[j]; a[j] = t;

}

t = a[l]; a[l] = a[j]; a[j] = t;

return j;

}

Merge Sort

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

Sua ideia básica é muito fácil: criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.

Os três passosúteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:

1. Dividir: Dividir os dados em subsequências pequenas;

2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;

3. Combinar: Juntar as duas metades em um único conjunto já classificado.

Análise de Complexidade

Complexidade de tempo: Θ(n log2 n)

Complexidade de espaço: Θ(n)

Observações:

É possível implementar o merge sort utilizando somente um vetor auxiliar ao longo de toda a execução, tornando assim a complexidade de espaço adicional igual a Θ(n log n).

É possível também implementar o algoritmo com espaço adicional Θ(1)

Algoritmo Criado por Von Neumann em 1945.

Vantagens: algoritmo de ordenação de simples implementação e fácil entendimento utilizando chamadas recursivas.

Desvantagens: Alto consumo de memória, devido a série de chamadas recursivas.

Código em C

void merge(int vec[], int vecSize) {

int mid;

int i, j, k;

int* tmp;

tmp = (int*) malloc(vecSize * sizeof(int));

if (tmp == NULL) {

exit(1);

}

mid = vecSize / 2;

i = 0;

j = mid;

k = 0;

while (i < mid && j < vecSize) {

if (vec[i] < vec[j]) {

tmp[k] = vec[i];

++i;

}

else {

tmp[k] = vec[j];

++j;

}

++k;

}

if (i == mid) {

while (j < vecSize) {

tmp[k] = vec[j];

++j;

++k;

}

}

else {

while (i < mid) {

tmp[k] = vec[i];

++i;

++k;

}

}

for (i = 0; i < vecSize; ++i) {

vec[i] = tmp[i];

}

free(tmp);

}

voidmergeSort(int vec[], int vecSize) {

int mid;

if (vecSize > 1) {

mid = vecSize / 2;

mergeSort(vec, mid);

mergeSort(vec + mid, vecSize - mid);

merge(vec, vecSize);

}

}

Desenvolvimento

Estes testes foram feitos num computador / Netbook, com:

Processador Intel Celeron, 1.2GHz (single Core)

4GB de RAM, operando em Dual-Channel

Frontside BUS de 800MHz;

Utilizei o CodeBlocks como IDE, pois ele devolve o tempo de execução do programa.

Fiz 9 testes, para o tamanho de vetor de 100, 1000, 10000 e 50000. Tirei a média dos valores e o desvio padrão. Para todos os testes, mandei imprimir na tela o vetor, antes da ordenação e depois.

Utilizei o valor de 50000 e não 100000 conforme o sugerido pela ATPS por motivos de tempo.

Como base para os testes com inteiros e doubles, utilizei as seguintes funções:

Para doubles:

//gera numeros doubles aleatorios:

//N é o numero de elementos (ou TAM) do vetor

//low = 0; high = 100000; seed = 1234554321

#include

#include

#define TAM 50000

/**********************************************************

Algoritmo 1 – Gerador de números reais aleatórios

Gerador de distribuicao uniforme retorna um numero

double (real com longa precisão) na faixa low – high,

ou seja, [low,high].

**********************************************************/

double unif(long int *seed, double low, double high)

{

double unif_ret;

long int m,a,b,c, k;

double value_0_1;

m = 2147483647;

a = 16807;

b = 127773;

c = 2836;

k = *seed/b;

*seed = a * (*seed % b) - k*c;

if

ETAPA 4

Passo 1 - Apresentar explicações sobre as análises realizadas neste estudo: por que houve reclamações de clientes com relação a desempenho e se existe um algoritmo de ordenação que pode ser usado como padrão para qualquer.

Os algoritmos tem características únicas nos quais apresentam desempenho superior conforme a entrada no sistema (quantidade de dados) e recursos disponíveis:

 Selection

Características Desvantagens

Interessante para arquivos pequenos O fato de o arquivo já estar ordenado não ajuda

em nada, pois o custo continua quadrático.

O algoritmo não é estável.

 Bubble

Características Desvantagens

Para o usuário, não há vantagem. Percorre a estrutura muitas vezes, por isto se torna ineficiente.

 Insertion

Características Desvantagens

Eficiente quando a estrutura está "quase ordenada".

Boa escolha caso deseja inserir elementos aos poucos. Estável. O pior caso quando os itens estão originalmente na ordem reversa.

 Merge

Características Desvantagens

Recomendado para aplicações com restrição de tempo. A complexidade do merge sort é a mesma para o pior, médio e melhor caso. Independente da situação dos dados no vetor, o algoritmo irá sempre dividir e intercalar os dados. Utiliza memória auxiliar, já que utiliza outros vetores para as subordenações. Alto consumo de memória

 Shell

Características Desvantagens

A razão da eficiência do algoritmo ainda não é conhecida. Ninguém ainda foi capaz de analisar o algoritmo. A sua análise contém alguns problemas matemáticos muito difíceis. O que se sabe é que cada incremento não deve ser múltiplo do anterior.

Shellsort é uma ótima opção para arquivos de

tamanho moderado. O tempo de execução do algoritmo é sensível à

ordem inicial do arquivo.

O método não é estável,

 Quick

Características Desvantagens

O pior caso ocorre quando, sistematicamente, o pivô é escolhido como sendo um dos extremos de um arquivo já ordenado.

Isto faz com que o procedimento Ordena seja

chamado recursivamente n vezes, eliminando apenas um item em cada chamada.

Extremamente eficiente para ordenar arquivos de dados.

Necessita de apenas uma pequena pilha como

memória auxiliar. Em seu pior caso, realiza o mesmo número de comparações que o Bubble sort.

Não é estável.

Possui várias versões, o que pode trazer diversos problemas e diferenças de desempenho, como as versões utilizadas nos testes.

 Binary Tree Search

Características Desvantagens

Ordenação rápida. Foi um dos melhores métodos de ordenação testados.

Melhor rendimento com menor quantidade de elementos.

As árvores binárias são uma das estruturas

de dados mais importantes devido a grande

aplicabilidade das mesmas. Torna o processo de busca mais lento, devido a possibilidade de alta profundidade da árvore.

Seu desempenho depende da quantidade e ordem dos elementos de entrada.

 

 AVL Tree

Características Desvantagens

Objetiva buscas mais rápidas. Ordenação lenta devido aos inúmeros processos de calculo dos fatores de balanceamento e balanceamentos.

Sua ordenação foi uma das mais demoradas.

 B-Tree

Características Desvantagens

Arvore-B é uma estrutura balanceada projetada para trabalhar com dispositivos de armazenamento secundário como dispositivos magnéticos. Utilizada para manipular muitos dados, sendo utilizada por SGBDs e manipulação de arquivos.

Economia de memória. Mais adequada a arquivos voláteis do que árvores binárias. Performance de busca por chave é idêntica a da árvore binária, se só ponteiros para nodos são empilhados.

Nodo não-folha com m chaves é visitado m vezes.

Desta forma, a padronização de um algoritmo de busca consistirá em perda de desempenho nas operações básicas (inserção, busca e remoção). Para se evitar desagrados dos clientes, deve-se escalar para uma determinada tarefa, um algoritmo com características favoráveis resultando em melhores desempenhos.

Passo 2 - Apresentar os principais aspectos que devem ser levados em consideração no momento da escolha do método a ser usado para ordenar uma base de dados e mantê-la ordenada. Para isso deverão considerar principalmente: a dimensão da base de dados; o número de execuções de ordenação realizadas pelo sistema e o número de buscas realizadas pelo sistema.

Resultados dos testes de dados aleatórios:

As tabelas acima demonstram o desempenho médio dos algoritmos, uma referência mais próxima de um caso real.

Como podemos constatar nos mais variados testes (como na Etapa 2), a entrada no sistema é um dos aspectos mais importantes na escolha, muitos dos métodos tem desempenho relacionado a ordem e quantidade de dados inseridos. Outro fatores muito importantes que devem ser levados em consideração é o tipo de estrutura utilizada, quantidade de recursos disponíveis (memória principal).

 

Passo 3 - Apresentar:

A posição da equipe sobre as melhores práticas em situações que envolvam pequenas bases de dados, grandes bases de dados e bases de dados de tamanho médio;

Para pequenas bases de dados

Concluímos que para pequenas bases de dados, o algoritmo escolhido poderia ser:

● Busca Binária

● Busca Linear

● Busca Linear com sentinela

● Ordenação usando Seleção

● Ordenação usando Bublesort

● Ordenação usando Inserção

Chegamos a esta conclusão por que estes algoritmos tem um grande gasto de performance se a massa de dados for muito grande, mas se não, eles podem ser utilizados. Um motivo para adoção destes seria a facilidade de implementação comparado aos algoritmos mais robustos. Dentre os métodos de ordenação, podemos ter uma alternativa interessante: Inserção. Como foi citado, é uma boa opção caso a inserção de elementos seja aos poucos.

Para bases de dados médias

Concluímos que para bases de dados medias, o algoritmo escolhido poderia ser:

● Ordenação Quicksort

● Ordenação Binária

● Ordenação ShellSort

● Ordenação Heapsort

● Ordenação Mergesort

● Árvore Binária de Pesquisa

Ao pensar em algoritmos para buscas nessas bases de dados de médio porte que usam estes metodos de ordenação, podemos sugerir um melhor método de busca para este cenário, que é o algoritmo de Busca Binária, onde necessita dos dados ordenados para que a busca seja bem sucedida. Se os dados não estiverem ordenados pode se utilizar os mesmos algoritmos de busca sugeridos para bases de pequeno porte.

A Árvore Binária de Pesquisa também se apresentou eficiente para o processo de ordenação.

Para grandes bases de dados

Concluímos que para bases de dados de grande porte, o algoritmo escolhido poderia ser:

● Arvores de Pesquisa

● Arvores Binárias de Pesquisa

● Arvores AVL

● B-Trees

Estes algoritmos são tanto quanto de ordenação quanto de busca, porem existe algumas peculiaridades.

Como estamos lidando com uma base de dados de grande porte, irá demandar muito processamento para todas as operações. Por exemplo, se na base de dados é preciso inserir muitos dados e retirar muitos dados somente, o algoritmo mais indicado é Arvores de Binárias de Pesquisa ou Arvores de Pesquisa, onde o algoritmo não irá modificar os dados para melhorar a pesquisa (rotações ou balanceamentos), mesmo assim, não deixando de faze-la.

Mas se além de Inserir/Remover os dados é necessário realizar pesquisas rápidas, o algoritmo indicado é Arvore AVL. Onde as operações são realizadas mas a estrutura é toda organizada para deixar os dados mais próximos possiveis de serem encontrados (fazendo rotações na arvore de elementos).

Mas se a massa de dados for muito robusta, utilizando de Inserções/Remoções e pesquisas, o algoritmo recomendado é o B-Tree. Mas para sua implantação é necessário que o algoritmo rode em algum computador com boa capacidade de processamento.

● Considerações finais da equipe sobre o estudo realizado.

Existem muitos bons algoritmos com diversas opções e características interessantes de uso. Para a implementação de um mecanismo de ordenação e/ou busca, deve-se observar as características do sistema (frequencia e volume de inserção, órdem dos dados a ser inseridos, tamanho da base de dados, etc.) e qual os métodos que mais se encaixam.

 

REFERÊNCIAS

SONG, Siang Wun. Universidade de São Paulo - IME/ USP. Árvore Binária de Busca. 2008. Acesso em: 27 de novembro de 2012. Disponível em: http://www.ime.usp.br/~song/mac5710/slides/06bst.pdf.

UFMG. Universidade Federal de Minas Gerais. Ordenação / Algoritmos e Estrutura de Dados II. 181 p. Acesso em: 27 de novembro de 2012. Disponível em: http://www2.dcc.ufmg.br/livros/algoritmos/slides.php.

UFSC. UFSC. Capítulo 10: Gerenciamento de Arquivos / Parte II: Árvores e Listas. Acesso em: 27 de novembro de 2012. Disponível em: http://www.inf.ufsc.br/~ine5384-hp/Estruturas.GerArq-2.html#10.3.3.%20%C3%81rvore%20B.

USP. Universidade de São Paulo - IME/ USP. Mergesort: ordenação por intercalação. Acesso em: 27 de novembro de 2012. Disponível em: http://www.ime.usp.br/~pf/algoritmos/aulas/mrgsrt.html.

TOFFOLO, Túlio. Toffolo. Árvores AVL / Algoritmos e estrutura de dados. Acesso em: 27 de novembro de 2012. Disponível em: http://www.toffolo.com.br.