DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORÍTMOS DE ORDENAÇÃO DE DADOS

...

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.

3.2 Algoritmo de ordenação por flutuação - Bubble sort

Um dos algoritmos de ordenação mais simples e utilizados na atualidade dentre tantos outros métodos. O bubble sort ganha essa referência pela fácil memorização de seu funcionamento e implementação (poucas linhas de código). Este tipo de algoritmo consiste em intercalar os elementos, devido a isso se encaixa na categoria de ordenação por intercalação. Com uma estrutura de dados desordenada inicia-se o algoritmo pelo primeiro elemento, depois se faz a comparação dele com todos os demais que estão na estrutura desordenada. Com quatro linhas de código é possível implementá-lo. É um algoritmo que deve ser utilizado apenas para pequenas quantidades de dados, para que não “engasgue” durante sua execução.

---------------------------------------------------------------

3.3 Algoritmo de ordenação por mistura - Merge sort

Merge sort, ou ordenação por mistura, é um algoritmo de ordenação do tipo que divide para conquistar. Sua ideia consiste em dividir (um grande problema em vários sub-problemas, e resolver tais sub-problemas através da recursividade) e conquistar (após todos os sub-problemas terem sido resolvidos ocorre a tão esperada conquista, que consiste na união das resoluções dos sub-problemas).

Os principais passos úteis desse algoritmo consistem em:

Dividir: Dividir os dados em subsequências pequenas;

Conquistar: Classificar as duas metades recursivamente aplicando o Merge sort;

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

Basicamente o raciocínio para que ele funciona da seguinte maneira: ordenar as várias subestruturas internas, caso essas estruturas não estejam ordenadas, basta ordená-las pelo mesmo método (de maneira infinita). Este algoritmo consiste em uma base matemática extremamente complexa e com um método bem interessante para ser estudado. Como exemplo podemos usar a ordenação dos seguinte números: 7, 3, 4, 8, 1, 2, 3, 5. O algoritmo irá dividir os números em pares ordenados: {3, 7}, {4, 8}, {1, 2}, {3, 5}, logo após fará o merge desses dados, ou seja, juntando-os em dois pares ordenados: {3, 4, 7, 8}, {1, 2, 3, 5}, depois irá juntá-los novamente: 1, 2, 3, 3, 4, 5, 7, 8. Ao final da execução do algoritmo a sequência inicial estará ordenada em a partir de divisões que foram feitas durante ao longo do processo de funcionamento do mesmo.

---------------------------------------------------------------

3.4 Algoritmo de ordenação por generalização - Heapsort

Este é um tipo de algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por seleção. Foi desenvolvido em 1964 por Robert W. Floyd e J.W.J. Williams, e faz suas operações localmente, utilizando apenas um número constante de elementos armazenados fora da estrutura de dados, basicamente como é feito no algoritmo por inserção. O mais interessante no seu funcionamento é a forma na qual ele arranja os dados depois de ordená-los, utilizando uma estrutura chamada monte (heap), que pode ser representada com uma árvore (uma árvore binária com propriedades especiais) ou como um vetor. Para a ordenação crescente, deve ser construído uma “heap” mínimo (o menor elemento fica na raiz). Isso é extremamente importante para vários conceitos e problemas presentes nos computadores, pois depois de ordenados os dados, podemos saber em que nível da árvore se encontra determinado item, operações sobre arvores binárias também são conceitos muito importantes para outras estruturas computacionais.

3.5 Algoritmo de ordenação por contagem - Counting sort

É o algoritmo mais rápido em variados casos, pois ordena os dados em tempo linear (segue uma linha tênue). Sim, tempo linear é possível. Esse tipo de ordenação pressupõe que os dados serão sempre uma entrada de 1 a N, pra qualquer inteiro sendo N, ou seja, se serão 6 dígitos, a entrada precisa ser qualquer combinação possível de 6 números que variam entre de 1 a 6.

A base matemática do algoritmo está em determinar que para cada elemento X da entrada o número de elementos menores que X, e depois inserir diretamente X na posição de saída na estrutura.

3.6 Algoritmo de ordenação por comparação - Quicksort

O algoritmo quicksort é um método de ordenação muito rápido e eficiente, inventado por Hoare em 1960 , quando visitou a Universidade de Moscovo, ainda