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

Prévia do material em texto

UNIVERSIDADE PAULISTA - UNIP
CAMPUS TATUAPÉ
CURSO DE CIÊNCIA DA COMPUTAÇÃO
DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS
SÃO PAULO - SP
2020
ESTRUTURA DE DADOS
Trabalho semestral apresentado como parte dos requisitos para aprovação de semestre do curso Bacharel em Ciência Da Computação.
 Área de concentração: Est. de Dados
 Orientador: Msc. Ricardo Drudi
 
 
 SÃO PAULO - SP
 2020
Sumário:
Introdução	4
Objetivo	5
Algoritmos de Ordenação	6
Selection Sort	6
Insertion sort	8
Merge Sort	9
Esquema de Funcionamento:	9
Estudo de caso	10
Ordenado 10.000:	10
Inverso 10.000:	11
Semi Ordenado 10.000:	11
Random 10.000:	12
Anexos do Software:	13
•MergeSort:	13
•Selection Sort:	14
•Insertion Sort:	14
•Funções	15
Conclusão	16
Referências	17
Introdução
Um algoritmo que faz a ordenação de um conjunto, geralmente representado num vetor, por sua vez é intitulado de algoritmo de ordenação. Em Ciência Da Computação, algoritmo de ordenação, é um algoritmo que aloca os dados de uma certa sequência em uma determinada ordem. O que em outras palavras, significa que ocorre a ordenação completa ou parcial. As ordens mais utilizadas são as ordens numéricas e a lexicográfica. Existem inúmeras razões para que se ordene uma sequência. Uma delas é a possibilidade de acessar seus dados com mais eficiência.
Dentre os mais importantes algoritmos de ordenação, podemos citar Bubble sort (ou ordenação por flutuação), Heap sort (ou ordenação por heap), Insertion sort (ou ordenação por inserção), Merge sort (ou ordenação por mistura) e o Quicksort. Existem outros diversos algoritmos de ordenação, que nós, alunos, podemos, com dedicação, pesquisar posteriormente. Entretanto, para estudo iremos nos concentrar nos seguintes algoritmos: Selection Sort, Quicksort e Insertion sort.
Objetivo
As Atividades Práticas Supervisionadas do 4º Semestres de 2019 do Curso de Ciência da Computação, tem por seu objetivo a pesquisa bibliográfica no que diz respeito em um dos principais algoritmos de ordenação de dados e o desenvolvimento de sistema computacional completo, utilizando a linguagem de programação Python, que obtenha os dados, efetue a ordenação e faça comparação dos desempenhos dentre as três técnicas selecionadas, além da elaboração de uma monografia sobre os aspectos teóricos que envolvem o projeto, bem como sobre todos os assuntos relativos ao desenvolvimento do sistema computacional. 
Algoritmos de Ordenação
Os Algoritmos de ordenação, são considerados em ciência da computação, como um algoritmo que traz em ordem correta de seguimento, uma sequência de dados aleatórios á ele fornecido. Seu principal objetivo é trazer mais facilidade para recuperação de dados listados.
Foram selecionados então três diferentes tipos de algoritmos de ordenação para apresentação de seus funcionamentos, sendo eles: Selection Sort, Quick Sort e Insertion Sort (Bruno, 2013).
Selection Sort
Sua base de funcionamento é trazer para a posição inicial do vetor o elemento de menor valor (podendo também ser o de maior valor, o que irá depender da requisição da ordenação), após isso ele deve trazer para próxima posição do vetor o segundo elemento de menor valor e assim consecutivamente, até que todos os elementos estejam ordenados (Bruno, 2013).
Em selection sort é selecionado um elemento da primeira posição na qual deve ser realizada a comparação com os demais, a partir de então ele começa a realizar comparações a sua direita a fim de encontrar um próximo elemento de menor valor. Se encontrado, o elemento de menor valor então é selecionado a partir daí para continuar as comparações, caso não sejam encontrados elementos de menor valor, este então inverte de posição com o primeiro número escolhido, após realizar a primeira comparação e identificar o menor elemento, ele segue utilizando agora para comparação o elemento da próxima posição a direita. Este processo é repetido até que todo o vetor esteja ordenado (Bruno, 2013).
Esquema de funcionamento Selection Sort:
· Neste passo, o primeiro número escolhido foi o 3. Ele foi comparado com todos os numerais à sua direita, e o numeral de menor expressão localizado foi o 1, logo, os dois efetuam a troca de lugares, invertendo suas posições (texto alterado).
· Na etapa seguinte, sendo o passo 2, ocorre o mesmo processo do passo 1. O número escolhido foi o 5, e o numeral de menor expressão localizado foi o 2, logo, os dois efetuam a troca de lugares, invertendo suas posições (texto alterado).
· No seguinte passo, o passo 3, o numeral localizado foi submetido à comparação com os outros numerais à sua esquerda. Não foi localizado nenhum numeral menor que 3, sendo assim, o mesmo permanece em sua respectiva posição (texto alterado).
· No passo de número 4, o numeral escolhido de novo foi 5, e em comparação com o seguinte e o ultimo numeral à direita, o numeral 4 inverte de lugar, pois é o único número menor que ele à sua direita e por esse motivo, o numeral 4, efetua a troca de lugar (texto alterado).
· Vetor já encontra-se ordenado (texto alterado) (Bruno, 2013).
Insertion sort
Neste caso o algoritmo funciona da esquerda para direita, ordenando os elementos a sua esquerda na medida em que avança. O insertion sort tem uma maior simplicidade e eficiência quando se tratam de listas de menor tamanho.
Um exemplo simples de como ele funciona é comparando-o com a forma em nós ordenamos as cartas em um jogo como pôquer (Bruno, 2013).
Esquema de funcionamento 
· No passo inicial é comparado se a primeira posição é maior que a próxima (no caso o 3 é comparado com o 5) sendo a condição falsa os números permanecem sem troca.
· Em seguida, os próximos números comparados são 5 e 4. Sendo o 4 o menor que o 5, eles invertem de posição.
· A próxima verificação foi realizada com o número 2. Sendo ele menor que todos os seus antecessores (3, 4 e 5), ele é colocado na primeira posição e os demais são arrastados para direita
· A última posição apresentava o número 1 sendo o menor de todos, logo foi colocado na primeira posição, e a lista já se encontra ordenada (Bruno, 2013).
Merge Sort
Sendo um modo privado de ordenação, o MergeSort tem como base executar a divisão dos dados pela metade e realizar a ordenação de cada um deles, e posteriormente a ordenação intercalada de ambas as partes, utilizando-se da função da recursividade (Bruno, 2013).
 
Esquema de Funcionamento:
• Passo 1: Nesta etapa, foi realizado a divisão do vetor em duas partes.
• Passo 2: Na etapa seguinte foi realizada a subdivisão.
• Passo 3: A partir desse passo é iniciada a ordenação utilizando a recursividade.
•Passo 4: Após ordenado, o vetor é intercalado e finalizado (Bruno, 2013).
Estudo de caso
Para realizar os testes de cada um dos métodos de ordenação apresentados pela pesquisa, foi utilizada a seguinte configuração:
· Processador: Core 2 quad 9400
· Memória Ram: 4gb ddr2
· OS: Windows 10 pro x64
Ordenado 10.000:
	Algoritmo
	Tempo(ms)
	Selection Sort
	
6.524.117
	Insertion sort
	
0.003427
	MergeSort
	0.077479
Inverso 10.000:
	Algoritmo
	Tempo(ms)
	Selection Sort
	20.158.548
	Insertion sort
	6.987.522
	MergeSort
	0.076573
Semi Ordenado 10.000:
	Algoritmo
	Tempo(ms)
	Selection Sort
	15.297.567
	Insertion sort
	9.229.647
	MergeSort
	0.110132
Random 10.000:
	Algoritmo
	Tempo(ms)
	Selection Sort
	10.504.986
	Insertion sort
	6.709.494
	MergeSort
	0.088816
Observação: Não foram ordenados arquivos acima dos 10.000, por impossibilidade do hardware.
Anexos do Software:
•MergeSort:
•Selection Sort:
•Insertion Sort:
•Funções
Conclusão
Com a finalização da pesquisa e o alcance de todos os objetivos solicitados pelo orientador, o grupo teve a oportunidade de realizar observações sobre os métodos de ordenação citadosna pesquisa e, concluiu-se que, o método que se mostrou mais eficiente na ordenação dos dados fornecidos para os testes foi o MergeSort com o tempo médio de 0.1177, entre os dados de ordenação inverso, ordenado, semi e random apresentados nas tabelas. 
Referências
Bruno. (2013). Dev Media. Fonte: DevMedia: https://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-comparacao/28261
Pereira, A. P. (2009). O que é algoritmo. Fonte: TecMundo: https://www.tecmundo.com.br/programacao/2082-o-que-e-algoritmo-.htm
Pereira, L. (2012). Principais Algoritimos de Ordenação. Fonte: Luan Pereira Blog: https://luancorrea.wordpress.com/2012/07/21/principais-algoritmos-de-ordenacao/
17