“DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS”
Por: Bruna_Garcia • 29/5/2015 • Trabalho acadêmico • 2.797 Palavras (12 Páginas) • 426 Visualizações
UNIVERSIDADE PAULISTA – UNIP
CIÊNCIA DA COMPUTAÇÃO-NOITE
“DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS”
Jundiaí
2015
INTRODUÇÃO
Este trabalho, tem como objetivo aprimorar nosso conhecimento em algoritmos de ordenação de dados.
O tema utilizado como base na elaboração do trabalho é: “O geoprocessamento de imagens da floresta amazônica permite a fiscalização de ações de crimes ambientais. Os satélites geram cerca de 100 mil imagens de toda a região a cada 24 horas, essas imagens são armazenadas e catalogadas”.
Esse tema é bastante interessante, já que nos mostra a importância da organização seja de dados ou de quaisquer outros objetos ou informações do dia-a-dia. A organização, nos permite enxergar melhor, ter facilidade de acesso e agilidade no manuseio dos objetos ou informações de um sistema.
Com os algoritmos de ordenação não é diferente.
Algoritmos são esquemas para solucionar problemas, é sempre obtido uma lógica nessa solução. Esses problemas são analisados pelos algoritmos e escritos em programas obtendo a solução.
O conceito de ordenação é: o processo de rearranjar um conjunto de objetos em uma ordem crescente ou decrescente.
A ordenação de dados em computação consiste em algoritmos que ordena os dados em uma sequência completa ou parcial, dependendo do que está sendo pedido pelo usuário.
Existem vários tipos de algoritmos de ordenação, tais como:
- Insertion Sort;
- Selection Sort;
- Bubble Sort;
- Merge Sort;
- Quick sort..
Neste trabalho, utilizamos apenas os algoritmos Insrtion Sort, Selection Sort, Bubble Sort e Merge Sort. Ao decorrer deste trabalho vamos mencioná-los várias vezes, além de explica-los detalhadamente, dando vários exemplos de suas funções.
REFERÊNCIAL TEÓRICO
Para a criação do programa, utilizamos a Linguagem C e o software Dev C++.
Antigamente, Martin Richards inventou a linguagem BCPL e logo depois Ken Thompson inventou a linguagem B. A Linguagem de programação C é derivada da linguagem B e foi inventada por Dennis Ritchie na década de 70. Foi implementada pela primeira vez pelo DEC PDP-11 rodando o sistema operacional UNIX.
A Linguagem C, é utilizada para a criação de diversos programas, como processadores de texto, planilhas eletrônicas, programas de comunicação, programas para a automação industrial, gerenciadores de bancos de dados, programas de projeto assistido por computador, programas para a solução de problemas da Engenharia, física, química, além de ser utilizada para a criação de sistemas operacionais, por mais modernos que sejam.
Essa linguagem, é o intermediário entre o humano e a máquina, permite que você escreva uma linguagem próxima da máquina mas compreensível para o humano.
Sua principal vantagem, é seu nível ecológico alto, gera os códigos executáveis e bastante econômico.
No programa, utilizamos os algoritmos de ordenação Insertion Sort, Selection Sort, Bubble Sort e Merge Sort, como já citado acima.
O algoritmo Insertion Sort é bem simples e eficiente quando aplicado em pequenas listas, ou pequenas quantidades de dados. A ordenação dos elementos nesse algoritmo ocorre da esquerda para a direita, os elementos ordenados vão ficando para a esquerda até o fim da ordenação.
É um tipo de algoritmo muitas vezes comparado com a forma que as pessoas utilizam para ordenar cartas de baralho.
Em Selection Sort, o menor elemento sempre é passado para a primeira posição, se a ordenação for ocorrer em ordem crescente. Se a ordenação for em ordem decrescente, o maior elemento vai sempre ser passado para a primeira posição. E assim ocorre sucessivamente até os dois últimos elementos.
O algoritmo Bubble Sort, é o mais simples e também o menos eficiente, consiste em comparar o elemento da primeira posição com o da segunda posição, caso o elemento da primeira seja menor que o da segunda, eles continuam em suas posições, caso ao contrário, eles trocam. E assim sucessivamente até o último número.
O algoritmo Merge Sort, é o mais complexo de todos, ele faz a intercalação de várias formas dos elementos para ordenalos.
Todos esses algoritmos de ordenação serão explicados detalhadamente ao decorrer deste trabalho, bem como a realização do programa e os resultados obtidos.
DESENVOLVIMENTO
Geração e obtenção de dados para ordenação
Declaramos um vetor com 100000 posições onde serão armazenados os arquivos e as variáveis num, i, random, op, flag=0 que serão utilizadas durante o programa, também utilizamos um ponteiro não instanciado, apenas declarado por FILE, que irá ler os arquivos que o usuário inserir.
O usuário terá duas opções: 1- abrir um arquivo em txt e 2- gerar números randômicos, caso o usuário digite uma opção diferente de 1 e 2, que não exista, o flag terá a função de mostrar um erro.
Caso o usuário escolha a opção 1, o arquivo terá que ser realmente txt e deve estar na pasta do programa, ao contrário, o programa não roda.
Ao abrir o arquivo txt, o programa irar definir quantos arquivos tem no total e armazena-los na variável num e salva qualquer outro valor que existe no arquivo guardando no vetor de 100000 posições. Depois o arquivo texto é fechado.
Se o usuário escolher a opção 2, ele digitará quantos números aleatórios ele quer para o programa gerar e armazenar no vetor. Caso ele digite um número maior que 100000, o programa apontará um erro, pois o número digitado excedeu o tamanho do vetor.
Criamos um recurso para o programa gerar números aleatórios de 0 até 10 milhões e armazena-los na variável random e random por vetor.
Focando no tema deste trabalho, o usuário irá, com certeza escolher a opção 1, já que estamos trabalhando com fotos de satélites catalogadas. A opção 1 é abrir arquivo em txt, mas não estamos trabalhando com imagens ? É ai que o ponteiro declarado por FILE entre em ação, ele lera as imagens e ira converte-las em arquivo txt.
...