aps atividade supervissionada

Prévia do material em texto

1
5
UNIVERSIDADE PAULISTA – UNIP
CURSO: CIÊNCIA DA COMPUTAÇÃO
“DESESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFOMACE DE ALGOTMO DE ORDENÇÃO DE DADOS”
MANAUS
2017
UNIVERSIDADE PAULISTA – UNIP
CURSO: CIÊNCIA DA COMPUTAÇÃO
Hudson Jonathan RA: D2313B5
Jackeline Suzanne Ra: DO5GED8
“DESESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFOMACE DE ALGOTMO DE ORDENÇÃO DE DADOS”
Trabalho exigido pela disciplina Estrutura de dados, como requisito para avalição da Atividade Pratica Supervisionada do curso de Ciência da computação, para nota parcial de nota sob Orientação : Prof. Alisson
MANAUS
2017
Índice
1–Objetivo do Trabalho.......................................................................................4
2–Introdução.......................................................................................................5
3–Referencial Teórico.........................................................................................
4–Desenvolvimento..........................................................................................
4.1–Blubble Sort..................................................................................................
4.2–Merge Sort....................................................................................................
4.3–Quick Sort…….............................................................................................
4.4–Insert Sort......................................................................................................
4.5- Heap Sort.......................................................................................................
5–Considerações Finais....................................................................................
6–Referência Bibliográfica.....................................................................................
Objetivo do trabalho
O objetivo desse trabalho é analisar a performance de algoritmos de ordenação de dados, tais como:
* BubleSort
* SelectSort
* InsertSort
* QuickSort
Introdução
A ordenação é um dos aspectos fundamentais das ciências computacionais. Torna-se, então, importante reduzir ao máximo a complexidade temporal dos algoritmos que lidam com este problema. As melhores ordenações em série normalmente demoram O(n log n), tempo que tende a agravar com o aumento do número de elementos. Deste modo, foram desenvolvidas versões para funcionamento em paralelo destes algoritmos, cujo objetivo é diminuir consideravelmente o tempo de execução dos mesmos.
Neste trabalho irei abordar alguns algoritmos de ordenação. Relativamente aos que realizam operações de comparação e troca, existem o bubble sort, quick sort, merge sort, insert sort e select sort.
Referência teórica
Desenvolvimento
Bubble sort 
 ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, e a cada passagem fazer flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
No melhor caso, o algoritmo executa {\displaystyle n}operações relevantes, onde {\displaystyle n}representa o número de elementos do vector. No pior caso, são feitas {\displaystyle n^{2}}operações. A complexidade desse algoritmo é de ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.
É o algoritmo mais simples, mas o menos eficientes. Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Caso o elemento da posição 2 for maior que o da posição 3, eles trocam de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes.
Selection Sort
Este algoritmo é baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o segundo menor valor para a segunda posição e assim sucessivamente, até os últimos dois elementos.
Neste algoritmo de ordenação é escolhido um número a partir do primeiro, este número escolhido é comparado com os números a partir da sua direita, quando encontrado um número menor, o número escolhido ocupa a posição do menor número encontrado. Este número encontrado será o próximo número escolhido, caso não for encontrado nenhum número menor que este escolhido, ele é colocado na posição do primeiro número escolhido, e o próximo número à sua direita vai ser o escolhido para fazer as comparações. É repetido esse processo até que a lista esteja ordenada.
Insertion sort 
É um algoritmo simples e eficiente quando aplicado em pequenas listas. Neste algoritmo a lista é percorrida da esquerda para a direita, à medida que avança vai deixando os elementos mais à esquerda ordenados.
O algoritmo funciona da mesma forma que as pessoas usam para ordenar cartas em um jogo de baralho como o pôquer.