ALGORÍTMOS DE ORDENAÇÃO DE DADOS
Por: nkasdkdsa • 30/5/2016 • Trabalho acadêmico • 3.657 Palavras (15 Páginas) • 304 Visualizações
[pic 1]
Sumário
- Objetivo do trabalho 3
- Introdução 4
- Referencial Teórico 5
- Desenvolvimento 14
- Resultados e discussão 15
- Considerações finais 16
Referências bibliográficas 17
Código fonte 18
1 Objetivo do trabalho
O objetivo desse trabalho consiste em estudar os algoritmos de ordenação interna e toda teoria computacional envolvida.
Após pesquisa bibliográfica sobre o assunto em questão o grupo escolheu três algoritmos para implementar e testar o desempenho. Dentre os vários algoritmos de ordenação existente, especificamente neste trabalho foi escolhido os algoritmos Bubble Sort, um dos mais conhecidos devido à sua simplicidade de implementação, Quick Sort, é considerado o melhor algoritmo de ordenação interna atualmente, e Insertion Sort, um dos mais simples algoritmos de ordenação interna.
Os algoritmos escolhidos serão implementados na linguagem Java a fim de permitir maior prática nesta linguagem juntamente com a ampliação do raciocínio em lógica de programação.
2 Introdução
Ordenação é o processo de realocar os elementos pertencente a uma estrutura de dados em ordem ascendente ou descendentes. Alguns fatores que influenciam na eficácia de um algoritmo de ordenação é o número de registros a serem ordenados, o limite de memória disponível, o grau de ordenação existente e a forma de como o algoritmo irá ordenar os dados.
Existem inúmeros algoritmos com complexidades variadas e com diferentes níveis de eficiência, mas todos possuem um único objetivo que é facilitar a recuperação posterior dos dados armazenados.
A proposta deste trabalho consiste justamente em estudar com maior profundidade os algoritmos, Bubble Sort, Quick Sort e Insertion Sort, bem como suas características principais. Esse estudo será abordado no capítulo 3 o qual consiste do referencial teórico. Após o referencial teórico, será abordado no capítulo 4 o desenvolvimento dos algoritmos escolhido pelo grupo, depois no capítulo 5 os resultados e discussões, isto é, como foram aplicados os testes e sobre o desempenho obtido, etc. No capítulo 6 o grupo apresentará as considerações finais e o seu entendimento sobre tudo que foi feito. E finalmente as referências para esta pesquisa e o código dos algoritmos desenvolvidos como anexo.
3 Referencial Teórico
Ordenação
Corresponde ao processo de rearranjar um conjunto de dados em ordem ascendente ou descendente.
Seu objetivo é facilitar a recuperação dos dados posteriormente. Imagine como seria difícil utilizar um catálogo telefônico se os nomes das pessoas não estivessem listados em ordem alfabética, ou se dicionários estivessem com as palavras todas desorganizadas. A conveniência de usar dados ordenados é inquestionável e precisa ser aplicada também à ciência da computação.
Os métodos de ordenação ilustram claramente como um determinado problema pode ser resolvido por meio de diferentes algoritmos, cada um apresentando vantagens e desvantagens, que devem ser considerados sob o ângulo da aplicação a que se destinam.
Existem diversos fatores que influenciam diretamente na eficácia de um algoritmo de ordenação, tais como:
- Número de registros a serem ordenados;
- A memória interna disponível (se cabe ou não todos os registros);
- O grau de ordenação já existente;
- Os tipos de meios de armazenamento em que os dados estão armazenados;
- A complexidade e os requisitos de armazenamento do algoritmo de ordenação;
- Se os registros deverão ou não ser removidos ou inseridos periodicamente.
Métodos de ordenação são classificados em dois grandes grupos:
- Ordenação interna: Onde os métodos não necessitam de uma memória secundária para o processo, a ordenação é feita na memória principal do computador.
- Ordenação externa: Quando o arquivo a ser ordenado não cabe na memória principal e, por isso, tem de ser armazenado em um dispositivo externo (fita, disco, etc.).
A principal diferença entre os dois grupos é que no método de ordenação interna qualquer registro pode ser acessado diretamente, enquanto no método externo é necessário fazer o acesso em blocos.
Existem vários algoritmos de ordenação de ambos os grupos, mas neste trabalho foram pesquisados três algoritmos da ordenação interna.
Bubble Sort
Por ser de fácil entendimento e implementação, o Bubble Sort (bolha) está entre os mais conhecidos métodos de ordenação de dados. O princípio do Bubble Sort é a troca de valores entre posições consecutivas, fazendo com que os valores mais altos (ou mais baixos) “borbulhem” para o final dos dados, daí o nome Bubble Sort.
Exemplo de ordenação em ordem crescente:
5 - 3 - 1 - 4 - 2
Primeiro compara-se as duas primeiras posições, nesse caso os números 5 e 3, se o primeiro número for maior que o segundo número deve-se fazer uma troca de posição entre eles. Assim ficando:
...