Aps unip 2º semestre
Atividade Prática Supervisionada
Curso: Ciência da Computação
DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS
BRASÍLIA-DF
2012
ÍndiceÍndice
Introdução3
Referencial Teórico5
Ordenação por inserção (Insertion Sort)5
Ordenação por Fusão (Merge Sort) 7
Ordenação Rápida (QuickSort) 10
Desenvolvimento13
Intervalos de tempo15
Gŕaficos Comparativos de velocidade por quantidade de elementos18
Considerações Finais21
Referências Bibliográficas22
Código Fonte23
Introdução
Em vários momentos do dia a dia, o homem depara-se com a necessidade de consultar dados ordenados. Como exemplo, pode-se citar uma lista telefônica. Imagine como seria consultar o telefone de uma pessoa se os nomes não estivessem classificados em ordem alfabética. Por isso uma das atividades mais utilizada na computação é a ordenação.
Ordenação corresponde ao método de rearranjar um conjunto de objetos em uma ordem crescente ou decrescente, e tem como objetivo facilitar a recuperação dos itens do conjunto oque à torna uma atividade relevante e fundamental em processamento de dados.
O projeto implementado em nosso trabalho é um software simples, onde pode-se manipular a quantidade de dados a ser ordenados e assim comparar o desempenho em relação ao tempo de ordenação em cada método.
Para falar das principais métodos de Algoritmo de Ordenação podemos separar em duas partes, em Métodos Simples e Métodos Sofisticados. Os Métodos Simples como Insertion Sort, Selection Sort, Bubble Sort, Comb Sort. E os Métodos Sofisticados: Quick Sort, Merge Sort, HeapSort, Shell Sort, Radix Sort, Gnome Sort, Count Sort, Bucket Sort, Cocktail Sort, TimSort.
Implementamos os seguintes algoritmos de ordenação: Insertion Sort; Merge Sort; Quick Sort;
Podemos dividir os algoritmos em 2 “classes”, conforme sua complexidade. Algoritmos de tempo de execução O(n2) – Insertion; Algoritmos de tempo de execução O(lg n) –