O DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS

...

A diferença do BDG é suportar feições geométricas em suas tabelas. Este tipo de base com geometria oferece a possibilidade de análise e consultas espaciais. É possível calcular nestes casos, por exemplo, áreas, distâncias etc. Os softwares que utilizam o BDG são chamados de Sistemas Gerenciadores de Banco de Dados (SGBD), alguns exemplos são: PostgreSQL, MySQL, Access e Oracle.

Referencial Teórico

Insertion Sort

Insertion Sort ou ordenação por inserção é o método que percorre um vetor de elementos da esquerda para a direita e à medida que avança vai ordenando os elementos à esquerda. Possui complexidade C(n) = O(n) no melhor caso e C(n) = O(n²) no caso médio e pior caso. É considerado um método de ordenação estável.

O funcionamento do algoritmo é bem simples: consiste em cada passo a partir do segundo elemento selecionar o próximo item da sequência e colocá-lo no local apropriado de acordo com o critério de ordenação.

Implementação:[pic 1]

Selection Sort-

A ordenação por seleção ou selection sort consiste em selecionar o menor item e colocar na primeira posição, selecionar o segundo menor item e colocar na segunda posição, segue estes passos até que reste um único elemento. Para todos os casos (melhor, médio e pior caso) possui complexidade C(n) = O(n²) e não é um algoritmo estável.

void selecao (int vet, int tam){

int i, j, min, x;

for (i=1; i-1; i++){

min = i;

for (j=i+1; j

if (vet[j]

min = j;

}

x = vet[min];

vet[min] = vet[i];

vet[i] = x;

}

Quick Sort

O Algoritmo Quicksort, criado por C. A. R. Hoare em 1960, é o método de ordenação interna mais rápido que se conhece para uma ampla variedade de situações.Provavelmente é o mais utilizado. Possui complexidade C(n) = O(n²) no pior caso e C(n) = O(n log n) no melhor e médio caso e não é um algoritmo estável.

É um algoritmo de comparação que emprega a estratégia de "divisão e conquista". A ideia básica é dividir o problema de ordenar um conjunto com n itens em dois problemas menores. Os problemas menores são ordenados independentemente e os resultados são combinados para produzir a solução final.

Basicamente a operação do algoritmo pode ser resumida na seguinte estratégia: divide sua lista de entrada em duas sub-listas a partir de um pivô, para em seguida realizar o mesmo procedimento nas duas listas menores até uma lista unitária.

void quick(int vet[], int esq, int dir){

int pivo = esq, i,ch,j;

for(i=esq+1;i

j = i;

if(vet[j]

ch = vet[j];

while(j > pivo){

vet[j] = vet[j-1];

j--;

}

vet[j] = ch;

pivo++;

}

}

if(pivo-1 >= esq){

quick(vet,esq,pivo-1);

}

if(pivo+1

quick(vet,pivo+1,dir);

}

}

A principal desvantagem deste método é que ele possui uma implementação difícil e delicada, um pequeno engano pode gerar efeitos inesperados para determinadas entradas de dados.

Mergesort

Criado em 1945 pelo matemático americano John Von Neumann o Mergesort é um exemplo de algoritmo de ordenação que faz uso da estratégia "dividir para conquistar" para resolver problemas. É um método estável e possui complexidade C(n) = O(n log n) para todos os casos.

Esse algoritmo divide o problema em pedaços menores, resolve cada pedaço e depois junta (merge) os resultados. O vetor será dividido em duas partes iguais, que serão cada uma divididas em duas partes, e assim até ficar um ou dois elementos cuja ordenação é trivial.

Para juntar as partes ordenadas os dois elementos de cada parte são separados e o menor deles é selecionado e retirado de sua parte. Em seguida os menores entre os restantes são comparados e assim se prossegue até juntar as partes.

void mergeSort(int *vetor, int posicaoInicio, int posicaoFim) {

int i, j, k, metadeTamanho, *vetorTemp;

if(posicaoInicio == posicaoFim) return;

metadeTamanho = (posicaoInicio + posicaoFim ) / 2;

mergeSort(vetor, posicaoInicio, metadeTamanho);

mergeSort(vetor, metadeTamanho + 1, posicaoFim);

i = posicaoInicio;

j = metadeTamanho + 1;

k = 0;

vetorTemp = (int *) malloc(sizeof(int) * (posicaoFim - posicaoInicio + 1));

while(i 1 || j 1) {

if (i == metadeTamanho + 1 ) {

vetorTemp[k] = vetor[j];

j++;

k++;

}

else {

if (j == posicaoFim + 1) {

vetorTemp[k] = vetor[i];

i++;