DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORÍTMOS DE ORDENAÇÃO DE DADOS
Por: vikthorgu • 27/4/2016 • Trabalho acadêmico • 6.137 Palavras (25 Páginas) • 1.527 Visualizações
[pic 1]
Código: 325X
Instituto de Ciências Exatas e Tecnologia
Curso de Ciência da Computação
Campus Pinheiros
“DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORÍTMOS DE ORDENAÇÃO DE DADOS”
São Paulo 2015
[pic 2]
Instituto de Ciências Exatas e Tecnologia
Curso de Ciência da Computação
Campus Pinheiros
Métodos de ordenação de dados
“DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORÍTMOS DE ORDENAÇÃO DE DADOS”
São Paulo 2015
SUMÁRIO
1. INTRODUÇÃO...............................................................................................5
2. OBJETIVO DO TRABALHO...........................................................................6
3. REFERENCIAL TEÓRICO.............................................................................7
3.1 Algoritmo de ordenação por inserção - Insertion sort...............................7
3.2 Algoritmo de ordenação por flutuação - Bubble sort.................................7
3.3 Algoritmo de ordenação por mistura - Merge sort.....................................8
3.4 Algoritmo de ordenação por generalização - Heapsort.............................9
3.5 Algoritmo de ordenação por contagem - Counting sort.............................9
3.6 Algoritmo de ordenação por comparação - Quicksort...............................9
3.7 Algoritmo de ordenação por seleção - Selection sort..............................10
4. DESENVOLVIMENTO...................................................................................11
4.1 Testando o método bolha - Bubble sort...................................................12
4.2 Testando o método comparação - Quicksort...........................................13
4.3 Geoprocessamento..................................................................................16
4.4 Sistema de monitoramento Amazônia legal.............................................16
4.5 O Geoprocessamento de imagens da Floresta Amazônica.....................17
5. COMPARATIVO ENTRE OS MÉTODOS DE ORDENAÇÃO........................19
6. RESULTADOS E DISCUSSÃO.....................................................................21
7. CONSIDERAÇÕES FINAIS...........................................................................25
8. CÓDIGO FONTE...........................................................................................26
9. REFERÊNCIAS BIBLIOGRÁFICAS..............................................................34
1. INTRODUÇÃO
Basicamente todas as linguagens de programação presentes na atualidade utilizam algum tipo de função para ordenação de dados. Nas próximas páginas trataremos sobre os principais algoritmos existentes, seu funcionamento e como devem ser implementados.
A ordenação de dados é o ato de se colocar os elementos de uma sequência de informações, ou dados, em uma relação de ordem predefinida.
Um algoritmo que ordena um conjunto, geralmente representado num vetor, é chamado de algoritmo de ordenação. Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em certa ordem, ou seja, efetua sua ordenação completa ou parcial.
2. OBJETIVO DO TRABALHO
Reconhecidamente o país de maior diversidade biológica do mundo, o Brasil tem sofrido uma constante perda de suas riquezas naturais. O desmatamento da Amazônia é hoje a mais visível delas, decorrendo da ocupação desordenada e não-sustentável que se constata na maior parte das suas fronteiras de ocupação.
O objetivo deste trabalho é demonstrar os principais conceitos sobre métodos de ordenação, seus benefícios, origem; como eles evoluíram com os passar dos tempos; vantagens e desvantagens. Assim como expor nossa opinião sobre o assunto, seus principais marcos e sua importância para o meio computacional atual.
Com o intuito de auxiliar no combate às questões de desmatamento na região, o Instituto Nacional de Pesquisas Espaciais (Inpe) criou um programa de monitoramento da região da Amazônia Legal, composto por três sub-sistemas. Hoje o monitoramento feito pelo Brasil é modelo para o mundo, sendo o sistema de Detecção de Desmatamento em Tempo Real (Deter) considerado como exemplo para outros países.
Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade de se acessar seus dados de modo mais eficiente. No decorrer deste trabalho veremos qual é o melhor método a ser utilizado em determinado tipo de situação.
3. REFERENCIAL TEÓRICO
3.1 Algoritmo de ordenação por inserção - Insertion sort
Este algoritmo pode ser exemplificado utilizando-se de ações do nosso dia a dia na resolução de um problema. Um exemplo bem prático disso é quando você está jogando baralho, e suas cartas já estão na mesa e você precisa colocá-las em sua mão de forma ordenada. Mas como fazer isso? Tal ordenação deve acontecer de maneira prática e fácil para que você possa jogar rapidamente, mas que também seja sua melhor jogada. É exatamente o que o algoritmo de ordenação por inserção faz. Sua ideologia principal é adicionar um item qualquer na estrutura dos dados, depois, para cada item que ainda não esteja na estrutura, antes de adicioná-lo, comparar com cada item que já esteja nela até encontrar a posição a ser encaixada (ou seja, já em ordem). Esse tipo de algoritmo de ordenação só é uma boa opção quando temos uma entrada de dados pequena, pois para entradas maiores poderia consumir muito tempo no processamento.
...