Algoritmos de Ordenação

F. S. Guizi

Algoritmos de Ordenação

Relatório apresentado à Universidade Federal do ABC como parte dos requisitos para aprovação na disciplina BC 505 - Processamento da Informação do Curso de Bacharelado em Ciência e Tecnologia.

Prof. Rogério Neves

Santo André - SP
2013
Sumário

1. Introdução

Algoritmos de ordenação são algoritmos que colocam elementos de uma lista em certa ordem, que pode ser numérica ou lexicográfica, ascendente ou descendente. O objetivo principal da ordenação é facilitar a recuperação posterior dos itens ordenados [1], ou seja, tornar o acesso aos dados mais eficiente. Dentre os principais algoritmos de ordenação pode-se citar Bolha (Bubble Sort), Ordenação por Seleção (Selection Sort), Ordenação por Inserção (Insertion Sort), Quick Sort , Concha (ShellSort), Merge e Heap.
Os algoritmos de ordenação podem ser comparados de acordo com a sua complexidade, tempo de execução, números de trocas, tipo de execução estabilidade, etc.
A complexidade de um algoritmo diz respeito aos recursos computacionais – espaço de memoria e tempo de máquina – requeridos para solucionar um problema. Tendo em vista que existem diversos algoritmos para solucionar um mesmo problema, a análise da complexidade computacional é importante para se definir os algoritmos mais eficientes para a solução de um dado problema [2].
Dessa forma, a análise da complexidade de um algoritmo é determinada segundo um modelo matemático que supõe que este vai trabalhar com a entrada de dados de tamanho N. A execução de um algoritmo pode ser dividida em etapas elementares denominadas passos: correspondente a um numero fixo de operações básicas, ou tempo constante, ou operação de maior frequência (operação dominante) . O numero de passos de um algoritmo é considerado o numero de execuções da operação dominante e função das entradas [3].
A expressão matemática de avaliação do tempo que é definida como a função que fornece o numero de