Analise empirica algortimos
Centro de Ciências Exatas e Tecnológicas
Colegiado de Ciência da Computação
Curso de Bacharelado em Ciência da Computação
Trabalho de Projeto e Análise de Algoritmos
Análise Empírica de algoritmos
Eder Schaphauser Ziomek
Cascavel
2014
1. Introdução
Este trabalho visa fazer a análise empírica de algoritmos de ordenação, serão analisados cinco algoritmos de ordenação, são eles: Bubble Sort, Selection Sort, Insertion Sort,Quicksort e Mergesort.
Para que fosse possível realizar a análise empírica teve-se o desenvolvimento dos algoritmos em linguagem de programação Java.
2. Metodologia
Os parâmetros utilizados para realizar a análise dos algoritmos foram à contagem de operações básicas. Quando um algoritmo é executado, ele gera ao fim da ordenação o numero de operações básicas que foram necessárias para realizar a ordenação do arquivo de teste. Foram gerados no total cinco arquivos de operações básicas, nestes as arquivos estão contidos, o numero do arquivo de teste e o tanto de operações básicas que foram necessárias para executar o arquivo de teste.
3. Análise Empírica dos Algoritmos
Está seção visa mostrar os algoritmos que foram desenvolvidos neste trabalho, será feita uma descrição do algoritmo, será mostrado o pseudocódigo do algoritmo, serão ilustradas as características de entradas, mostrando caso exista o pior e melhor caso, serão ilustradas as análises matemáticas, serão mostrados os gráficos e tabelas de cada algoritmo e a classe assintótica do algoritmo.
1
2
3
3.1 Bubble Sort
3.1.1 Descrição
O bubble sort é um algoritmo de ordenação dos mais simples. A ideia deste algoritmo se baseia em percorrer o vetor diversas vezes, a cada passagem fazendo com que o maior elemento do vetor vá para o final do vetor.
3.1.2 Pseudocódigo INTEIRO [] bubbleSort(inteiro v[])
INICIO
VAR aux, i, j : inteiro;