Análise Matemática e Empírica para Algoritmos de Ordenação

Análise Matemática e Empírica para Algoritmos de Ordenação
Gustavo Catarino da Costa
UNIOESTE - Universidade Estadual do Oeste do Paraná
Rua Universitária, 2069. Jardim Universitário.
Caixa Postal 711 - CEP 85819-110 Cascavel, PR

Resumo. Este trabalho tem por objetivo apresentar e comparar os resultados obtidos de uma análise matemática e uma análise empírica dos algoritmos de ordenação Selection Sort e Insertion Sort.

1. Introdução
A resolução de problemas nem sempre pode ser feita de qualquer maneira, principalmente na computação. Tarefas simples como a busca em um vetor ou a ordenação de dados pode ser um problema se não tratado da maneira correta quando se usa um parâmetro específico ou um largo conjunto de dados de entrada.
O foco deste trabalho são os métodos para ordenação de dados. São diversos os algoritmos existentes, cada um com suas vantagens e desvantagens, mas todos foram criados com um único objetivo, otimizar a ordenação em uma determinada situação, ou seja, existem algoritmos de ordenação que tratam diversos casos. Os algoritmos analisados neste trabalho serão o Selection Sort (Ordenação por Seleção) e o Insertion Sort (Ordenação por
Inserção). Para ambos os algoritmos serão realizadas as análises empírica e matemática, obtendo informações a respeito do pior e melhor caso e a classe de eficiência de cada um.
Nos próximos capítulos serão discutidos a estrutura e a explicação de funcionamento de cada método, posteriormente, a respeito da implementação realizada e os testes executados e por fim uma comparação entre os resultados obtidos da análise matemática e a análise empírica.

2. Algoritmo Insertion Sort
O método de ordenação Insertion Sort, ou Ordenação por Inseração, é um algoritmo para ordenação de dados muito simples e fácil de implementar. Ele ordena um vetor processando um item por vez sendo eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre o vetor da esquerda para