Ordenação Interna

Métodos de Ordenação Interna

Manaus – 2013

Sumário Pág.

Introdução ----------------------------------------------------------------------------- 1

Objetivos ------------------------------------------------------------------------------- 2

Metodologia --------------------------------------------------------------------------- 3

Algoritmos de Ordenação --------------------------------------------------------- 4

SelectionSort ------------------------------------------------------------------- 4

InsertionSort -------------------------------------------------------------------- 5

BubbleSort ---------------------------------------------------------------------- 6

Merge Sort ----------------------------------------------------------------------- 7

QuickSort ----------------------------------------------------------------------- 7

Resultados ---------------------------------------------------------------------------- 9

Conclusão ----------------------------------------------------------------------------- 13

INTRODUÇÃO

Em diversas situações no cotidiano, o homem vê-se diante da dificuldade de consultar dados ordenados. Como exemplo pode-se fazer referência a uma biblioteca. Imagine como seria consultar livros se os nomes dos mesmos não estivessem em uma classificação de ordem alfabética. Portanto uma das ações mais utilizadas na computação é a ordenação. Entre elas temos: as numéricas e as lexicográficas.

Estudar a complexidade de um algoritmo é determinar o custo computacional para sua execução. O estudo é feito por duas vias: teoria da complexidade computacional ou Análise de algoritmos. Nesse trabalho iremos usar a segunda.

Existem diversos algoritmos de ordenação interna e eles são classificados em métodos simples e métodos eficientes, dentre os algoritmos existentes o presente trabalho irá expor a implementação e os testes de cinco destes métodos. Os três primeiros são simples e os dois últimos são eficientes:

1. SelectionSort

2. InsertionSort

3. BubbleSort

4. MergeSort

5. QuickSort

Os testes foram realizados com vetores de números inteiros de diferentes tamanhos (100, 1.000, 10.0000, 1.000.000), com valores aleatórios, assim também como um relatório gráfico comparativo de cada método através do tamanho do vetor versus tempo (mms).

OBJETIVOS

Objetivo geral: Mostrar a eficiência dos algoritmos de diferentes tamanhos e tipos.

Objetivo especifico: Verificar e analisar a eficiência dos algoritmos de ordenação interna.

METODOLOGIA

O trabalho foi baseado em artigos científicos, e buscamos base em livros de vários autores referentes ao assunto, visando coletar assuntos relevantes ao tema algoritmo de ordenação interna, seus desempenhos e suas especificações.

A metodologia adotada consiste inicialmente no estudo da complexidade e no comportamento de cada algoritmo, em seguida foi feita a implementação destes na linguagem C, foram feitas experimentações e medição de tempo na resolução de várias instâncias, que são de melhor e pior caso. Essas medições são apresentadas por gráficos de tempo x tamanho.

Local de Realização

Biblioteca da Uninorte, ambiente com mesas para estudos, climatizado, com livros para consulta e internet disponível para pesquisa em sites.

Algoritmos de Ordenação

Ordenação corresponde a métodos de rearranjar um conjunto de objetos em ordem crescente ou decrescente, tem como objetivo facilitar a recuperação dos itens desse conjunto.

Diversas estratégias são utilizadas na solução de problemas computacionais. Os algoritmos de ordenação se baseiam em várias técnicas: seleção, trocas, dividir para conquistar dentre outras. A estratégia utilizada também determina a complexidade computacional de tempo e espaço do algoritmo.

Em todos os métodos verificados nesse trabalho a análise de complexidade é baseada no número de comparações e no número de trocas que o algoritmo realiza.

• SelectionSort

É um método de ordenação que funciona percorrendo o vetor diversas vezes e a cada passagem vai trazendo o vetor de menor valor para a primeira posição. A cada passagem é analisado a quantidade de itens do vetor menos um. É o algoritmo ideal para arquivos com registros muito grandes.

Ele possui uma grande desvantagem, mesmo depois de algumas entradas terem sido ordenadas, a inserção de outra entrada pode exigir muitas modificações.

Vantagens:

- Fácil implementação;

- Número de movimentações pequenas.

Desvantagens:

- Ordem de complexidade quadrática;

- Algoritmo não estável.

Análise de complexidade

Para a análise do algoritmo SelectionSort será considerado o seguinte aspecto: a quantidade de comparações realizadas.

O total de comparações realizadas por esse método é representada pela fórmula:

(n-1) + (n-2)+(n-3)+ ...+1 = (n2 – n)/2 = O(n2).

O