DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS.
Por: nickmanoel • 21/11/2017 • Trabalho acadêmico • 2.621 Palavras (11 Páginas) • 302 Visualizações
UNIVERSIDADE PAULISTA
CIÊNCIA DA COMPUTAÇÃO
ANDRE SOUZA DOS SANTOS RA C8719F-5
LEONARDO DA SILVA YAMANE DE OLIVEIRA RA C9471D-7
NICOLAS MANOEL MENDES RA C931AI-0
THOMAS JACKSON DE MELO RA C801GG-7
VITOR MAION MOREIRA RA C768CA-1
DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS.
SÃO PAULO 2017
ANDRE SOUZA DOS SANTOS RA C8719F-5
LEONARDO DA SILVA YAMANE DE OLIVEIRA RA C9471D-7
NICOLAS MANOEL MENDES RA C931AI-0
THOMAS JACKSON DE MELO RA C801GG-7
VITOR MAION MOREIRA RA C768CA-1
DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS.
Atividade prática supervisionada para obtenção de nota no curso em Ciência da computação apresentado à Universidade Paulista – UNIP.
Orientador: Edilson Rodrigues
SÃO PAULO 2017
Índice
1.Objetivo....................................................................................................................2
2.Introdução................................................................................................................3
3.Referencial Teórico.................................................................................................4
4.Resultados e Discussão.........................................................................................6
4.1.Dados Aleatórios..................................................................................................6
4.2.Dados pré-ordenados em ordem decrescente..................................................7
4.3. Dados já ordenados (ordem crescente)............................................................8
5.Considerações Finais.............................................................................................9
6.Desenvolvimento...................................................................................................10
7.Código Fonte.........................................................................................................16
8.Referências Bibliográficas...................................................................................26
1. Objetivo
Este trabalho tem como objetivo conhecer e apresentar diferentes métodos de ordenação em estrutura de dados, como por exemplo, QuickSort.
Iremos analisar alguns fatores nos método de ordenação, como seus algoritmos e suas velocidades.
2. Introdução
O algoritmo é uma sequência finita que deve ser executada de maneira mecânica ou eletrônica, o mesmo pode ser executado através do computador ou dos seres humanos.
Os algoritmos tem como objetivo nortear os passos a ser seguido em determinada atividade ou auxiliar na resolução de algum problema, podemos perceber que diversos algoritmos podem ser utilizados para uma mesma ação.
Na computação os algoritmos também tem a sua importância assim como na maioria das atividades que realizamos diariamente nas nossas vidas, na computação os algoritmos devem ser bem definidos pois é uma máquina que executará suas funções, todas as tarefas que são executados em um computador possuem algum tipo de algoritmo dessa forma o algoritmos nos ilustra que o mesmo está presente para ser seguido como se fosse uma receita.
3. Referencial Teórico
Na computação temos 3 tipos de algoritmos que são utilizados frequentemente com objetivo de ordenar dados, cada um com uma função distinta, são eles o QuickSort, InsertionSort e algoritmo BubbleSort.
No algoritmo QuickSort podemos verificar que ele é um método de ordenação rápido e eficiente que foi criado em 1960 por um estudante, o método surgiu quando o aluno tentava traduzir um dicionário de inglês para russo de forma que as palavras fosse ordenadas de uma maneira mais rápida e fácil.
O QuickSort ainda tem como estratégia a divisão e a conquista, ou seja a estratégia consiste em rearranjar as chaves menores para que elas precedam as chaves maiores, ainda esse método ordena as duas sublistas de chaves menores e maiores para que lista seja ordenada adequadamente conforme necessário.
Em algumas raras instâncias, o Quicksort pode ser tão lento quanto os algoritmos elementares; mas em geral é muito mais rápido. Mais precisamente, o algoritmo consome tempo proporcional a n log n em média e proporcional a n2 no pior caso.
Usaremos duas abreviaturas ao discutir o algoritmo. A expressão v[i..k] ≤ x será usada como abreviatura de v[j] ≤ x para todo j no conjunto de índices i..k. Analogamente, a expressão v[i..k] ≤ v[p..r] será interpretada como v[j] ≤ v[q] para todo j no conjunto i..k e todo q no conjunto p..r.
No método algoritmo BubbleSort podemos verificar que também é um método de ordenação porém mais simples que o QuickSort, esse algoritmo tem como objetivo comparar os itens a serem ordenados de maneiro sucessiva ou seja o mesmo faz comparações de acordo com as posições dos dados a serem ordenados, porém esse algoritmo não é indicado para casos de ordenações que requem velocidade e que possuem grande quantidade de dados a serem ordenados pois ele percorre os dados por diversas vezes.
Técnica básica Comparam-se dois elementos e trocam-se suas posições se o segundo elemento é menor do que o primeiro São feitas várias passagens pela tabela Em cada passagem, comparam-se dois elementos adjacentes Se estes elementos estiverem fora de ordem, eles são trocados.
Vantagens Simplicidade do algoritmo, Estável. Desvantagens Lentidão Indicações Tabelas muito pequenas. Quando se sabe que a tabela está quase ordenada, Demonstrações didáticas. Origem da denominação, Os elementos menores (mais “leves”) vão aos poucos “subindo” para o início da tabela, como se fossem bolhas.
...