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

Universidade Paulista – Unip

Campus – Manaus

Instituto de Ciências Exatas e Tecnologicas - ICET

Ciência da Computação

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

Manaus

2017

Grupo:

Jamison Lopes Rossete Moraes - RA: D12975-9

Paulo Oliveira Siqueira Júnior - RA: D001GB-3

Matheus Alves Barros - RA: D11800-5

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

Trabalho solicitado pelo Professor Rildo Nogueira para a obtenção de nota na Atividade Pratica Supervisionada, do Curso de Ciência da Computação, da Universidade Paulista.

Manaus

2017

Introdução

Imagine que você gostaria de adicionar um contato de um colega ou parente seu em seu smartphone, entretanto, você repara que a sua lista de contatos não está organizando em ordem alfabética? Seria muito complicado. A ordenação ou classificação de registros consiste em organizá-los na ordem desejada pelo usuário, seja ela de ordem crescente, decrescente e etc. Buscando assim facilitar a recuperação, visualização e edição dos dados.

Para realizar essas tarefas de ordenação, O campo da ciência da computação utiliza-se de vários algoritmos que foram desenvolvidos com objetivo de facilitar tais organizações de dados. Essa ordenação em ciência da computação possui diversos tipos algoritmos que utilizam diferentes técnicas de ordenação para ordenar um conjunto de dados, eles são conhecidos como Algoritmos de Ordenação ou Métodos de Ordenação.

Esses dados podem tanto ser ordenados para caber na memória principal possibilitando qualquer registro ser imediatamente acessado, processo na qual é conhecido por Ordenação Interna. Quando os dados forem ordenados e não couberem na memória principal, os registros são acessados sequencialmente ou em grandes blocos método no qual é chamado de Ordenação Externa.

Na ordenação interna podemos encontrar dois tipos de métodos, o método simples e o eficiente, os programas pequenos e fáceis de entender são chamados de Métodos Simples, são exemplos: Insertion Sort, Selection Sort, Bubble Sort, Comb Sort. Os Métodos Eficientes são, portanto mais complexos nos detalhes, requerem um número menor de comparações. São projetados para trabalhar com uma quantidade maior de dados, são exemplos: Quick sort, Merge sort, Shell sort, Heap sort, Radix sort, Gnome sort, Count sort, Bucket sort, Cocktail sort, Timsort.

Na Ordenação Externa consiste em ordenar arquivos de tamanho maior que a memória interna disponível, o método mais importante de ordenação externa é o de ordenação por intercalação onde ele combina dois ou mais blocos ordenados em um único bloco ordenado para diminuir a quantidades de passadas (leituras sobre por dados).

Um dos ramos da Ordenação de Dados pode-se encontrar o Geoprocessamento, que faz parte da área de Geomática. Que consiste no tratamento das informações geográficas, por meio de tecnologias ligadas à informação espacial tanto na coleta quanto no tratamento e na análise desses dados. Essas tecnologias são chamadas de Geotecnologias, alguns exemplos são: Posicionamento por satélite, Cartografia, Topografia, Fotogrametria, Sensoriamento remoto. 

O Sistemas de Informação Geográfica (SIG) é geralmente a associado somente à geotecnologia, porém um SIG é composto também de metodologias, dados (coletados e/ou tratados), hardwares (scanners, gps etc.) e recursos humanos (como os responsáveis por operar os programas ou gerenciar os equipamentos etc.). 

Banco de Dados Geográficos (BDG), antes de entende-lo precisamos saber o que é um Banco de Dados. Segundo Korth, um banco de dados “é uma coleção de dados inter-relacionados, representando informações sobre um domínio específico”, ou seja, um banco de dados é sempre que houver um agrupamento de informações forem relacionadas entre si. E também saber que o BDG utiliza um banco de dados relacional, onde dados são armazenados na forma de tabelas relacionáveis entre si através campos chaves.

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<=n-1; i++){

        min = i;

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

            if (vet[j] < vet[min])

            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.