O Desenvolvimento de sistema para análise de performance de algoritmos de ordenação de dados
Por: Jeison Bueno • 15/3/2017 • Trabalho acadêmico • 10.334 Palavras (42 Páginas) • 276 Visualizações
[pic 1]
Estrutura de dados
Ordenação de dados
Sumario
1. Objetivo
2.Introdução
3. Desenvolvimento de sistema para análise de performance de algoritmos de ordenação de dados
3.1 Conceitos gerais de estrutura de dados
3.2 Definição de estrutura de dados
4. Técnicas e métodos de classificação e busca e ordenação de dados
4.1 Bubble Sort
4.2 Select Sort
4.3 Insert Sort
4.4 Shell Sort
4.5 Quick Sort
5.Dissertação
6.Projeto (estrutura) do programa
7.Relatório com as linhas de código
8. Anexos
9.Bibliografia
1.OBJETIVO
Análises
A análise deve ser feita sobre o número de comparações, atribuições e tempo
de execução dos algoritmos. Organizamos de forma inteligente os dados
coletados em tabelas, e também construimos gráficos a partir dos dados.
Então, disserte sobre os dados nas tabelas e gráficos.
As implementações dos algoritmos
Neste trabalho, está sendo utilizado a compilação, interpretação e uso deste
código constitui parte deste trabalho prático. A implementação dos outros
algoritmos a serem utilizados na primeira
parte. Usaremos o padrão de programação do
código fornecido e implementaremos os novos algoritmos seguindo esse
padrão.
Salienta-se que o uso desse programa pode ser realizado em linha de
Comando (prompt). Compilaremos o código para gerar o arquivo executável e
configurar o arquivo a seguir.
Exemplos de ordenação Interna
Métodos de ordenação interna são métodos no qual consegue-se ordenar o
Arquivo usando-se somente a memória pricipal do computador(memória RAM),
ou seja, o arquivo cabe todo na memória.
Um aspecto importante aspecto na escolha de um algoritmo de ordenação é o
tempo gasto para ordenar o arquivo. Também podemos considerar o número
de comparações entre as chaves e o número de movimentações ou trocas dos
itens do arquivo.
Outro fator importante de extrema importância é a quantidade de memória
gasta para ordenar o arquivo. O uso econômico da memória disponível é muito
apreciado na ordenação interna. Métodos que utilizam o próprio vetor para
realizar a ordenação, ou seja, não utilizam memória adicional são conhecidos
como métodos
Alguns exemplos de métodos de ordenação serão os seguintes:
BubbleSort, SelectSort, InsertSort, QuickSort e etc.
2.INTRODUÇÃO
O objetivo deste trabalho é fazer o desenvolvimento de sistema para análise de
performance de algoritmos de ordenação de dados.
Linguagem
Linguagem utilizada: Linguagem Java.
Na análise da ordem de complexidade dos algoritmos será analisado o pior
caso sempre.
Foram passados ponteiros de estruturas para as funções para economizar
memória.
Análises
A análise dos algoritmos será dividida em duas partes. Na primeira, a análise
Será sobre os algoritmos de ordenação simples (de ordem de complexidade
O(n2) – i.e.,
BubbleSort, SelectSort, InsertSort e algumas variações). Você deverá
Implementar os três algoritmos citados e implementar variações desses
algoritmos de forma que através de análises de experimentos você possa
analisar:
Se vale a pena inserir a verificação de ordenação (houve troca) no algoritmo
BubbleSort;
Se vale a pena usar o algoritmo InsertSort com elemento sentinela;
Se vale a pena usar um algoritmo InsertSort tendo o arranjo implementado
através de apontadores/cursores;
Se vale a pena inserir uma verificação (Min == i) para evitar a troca, no
método SelectSort.
A segunda parte será sobre os algoritmos de ordenação por comparação ditos
eficientes, como MergeSort, HeapSort e QuickSort, que tem complexidade de
tempo de O( n log n ). São fornecidas implementações convencionais e
versões otimizadas.
Aproveite os algoritmos implementados por você e verifique:
A entrada deve ser lida de um arquivo a ser fornecido como parâmetro em linha
de comando ( int main(int argc, char**argv) ) composta de vários conjuntos de
testes, onde cada linha do arquivo contém uma expressão aritmética a ser
avaliada, no seguinte formato:
Até que tamanho de entrada, vale a pena usar algoritmos O(n2) com relação
a algoritmos O(n log n).
...