Aps Ordenaçao

[pic 1][pic 2]

Ciência da Computação

DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE ALGORITMOS DE ORDENAÇÃO DE DADOS

Karen A de Oliveira Leme                                                                RA C22164-3

João Vitor M. Bonachini da Silva                                                    RA C27271-0

Celso Apolinário Prazeres Junior                                                     RA C04815-1 

Araçatuba, SP 2015

Lista de Figuras

Figura 21 - Processo de triagem de inserção        

Figura 22 Quinta passagem em detalhe        

Figura 23 Max Heap        

Figura 24 Representação da Heap        

Figura 25: Dividindo a lista de Merge Sort        

Figura 26 Listas como eles são mesclados juntos        

 

Sumário

CAPÍTULO 1 - INTRODUÇÃO        

1.1 Objetivos        

1.2 Introdução        

CAPÍTULO 2 - REFERENCIAL TEÓRICO        

2.1 Bubble Sort        

2.2 Selection Sort        

2.3 Insertion Sort        

2.4 Heap Sort        

2.5 Shell Sort        

2.6 Merge Sort        

2.7 Quick Sort        

CAPÍTULO 3 - DESENVOLVIMENTO        

3.1 Desenvolvimento        

CAPÍTULO 4 - RESULTADOS E DISCUSSÃO        

4.1 Vetor Ordenado        

4.1.1 Movimento        

4.1.2 Comparação        

4.1.3 Tempo de execução        

4.2 Vetor Aleatório        

4.2.1 Movimento        

4.2.2 Comparação        

4.2.3 Tempo de execução        

4.3 Vantagens e Desvantagens        

CAPÍTULO 5 - CONSIDERAÇÕES FINAIS        

5.1 Considerações Finais        

CAPÍTULO 6 - CÓDIGO FONTE        

6.1 Código Fonte        

CAPÍTULO 7 - BIBLIOGRAFIA        

---

Capítulo 1

1. Introdução

1. Objetivos

Pesquisar bibliografia a respeito dos principais algoritmos de ordenação de dados e o desenvolvimento de sistema computacional completo, utilizando a linguagem de programação C#, que obtenha os dados, efetue a ordenação e compare os desempenhos entre sete técnicas selecionadas, além da elaboração de uma monografia sobre os aspectos teóricos que envolvem o projeto, bom como sobre todos os assuntos relativos ao desenvolvimento do sistema computacional.

1. Introdução

A maioria dos algoritmos de ordenação funciona através da comparação dos dados que estão sendo classificados. Em alguns casos, pode ser desejável para classificar um grande pedaço de dados (por exemplo, uma estrutura que contém um nome e endereço) com base em apenas uma porção dos dados. O pedaço de dados efetivamente utilizadas para determinar a ordem de classificação é chamado a chave.algoritmos de ordenação são geralmente julgado pela sua eficiência. Neste caso, refere-se a eficiência a eficiência algorítmica como o tamanho da entrada cresce grande e está geralmente em função do número de elementos de classificar. A maior parte dos algoritmos em uso ter uma eficiência de algorítmico ou O (n ^ 2) ou O (N * log (n)). Alguns algoritmos especiais de caso (um exemplo é mencionado em pérolas ) pode classificar certos conjuntos de dados mais rápido do que O (n * log (n)). Esses algoritmos não são baseadas em comparar os itens que estão sendo classificados e dependem de truques. Demonstrou-se que nenhum algoritmo de chave de comparação pode ter um melhor desempenho do que O (N log N * (N)). Muitos algoritmos que têm a mesma eficiência não têm a mesma velocidade de entrada no mesmo. Em primeiro lugar, os algoritmos devem ser julgados com base no seu caso médio, melhor caso, e pior eficiência. Alguns algoritmos, como a classificação rápida, executa excepcionalmente bem para algumas entradas, mas terrivelmente para os outros. Outros algoritmos, como o merge sort, não são afetados pela ordem de entrada de dados. Mesmo uma versão modificada do Bubble Sort pode terminar em O (n) para as entradas mais favoráveis. Um segundo fator é o "termo constante".

Como grande notação abstrai muitos dos detalhes de um processo, é bastante útil para olhar para o retrato grande. Mas uma coisa que fica descartada é a constante na frente da expressão: por exemplo, O (c * n) é apenas O (n). No mundo real, a constante, c, irá variar entre diferentes algoritmos. A Quick Sort bem implementada deve ter um multiplicador constante muito menor do que Heap de classificação. Um segundo critério para julgar algoritmos é a sua necessidade de espaço - eles exigem espaço de rascunho ou a matriz pode ser classificada no lugar (sem memória adicional para além de algumas variáveis)? Alguns algoritmos nunca exigem espaço extra, enquanto que alguns são mais facilmente compreendidos quando implementado com espaço extra (heap de classificação, por exemplo, pode ser feito no local, mas conceitualmente é muito mais fácil pensar em um monte separado). As necessidades de espaço pode até depender da estrutura de dados utilizada (Merge Sort em matrizes contra Merge Sort em listas ligadas, por exemplo). Um terceiro critério é a estabilidade - não o tipo preservar a ordem das chaves com valores iguais? A maioria dos tipos simples fazer exatamente isso, mas alguns tipos, como Heap de classificação, não.