DP_APS_18B6_Metodos de Ordenação

Prévia do material em texto

UNIP – UNIVERSIDADE PAULISTA 
Curso de Ciência da Computação 
 
 
 
 
 
 
 
 
ATIVIDADES PRÁTICAS SUPERVISONADAS - APS 
 
Algoritmos de Ordenação 
 
 
 
Daniel Ferreira da Silva - RA – D11CFD2 
 
 
 
 
 
São José dos Campos, 30 de maio de 2022. 
 
 
 
UNIP – UNIVERSIDADE PAULISTA 
Curso de Ciência da Computação 
 
 
 
 
 
 
 
 
ATIVIDADES PRÁTICAS SUPERVISONADAS - APS 
Curso de Ciência da Computação 
 
 
 
 
 
 
 
 
 
Atividades Práticas Supervisionadas do 
2º Semestres do Curso de Ciência da 
Computação da Universidade 
Paulista – UNIP. 
 
Coordenador: Prof. Fernando A. Gotti 
 
 
 
 
São José dos Campos, 30 de maio de 2022 
RESUMO 
Esse trabalho tem como objetivo demonstrar alguns dos métodos de 
ordenação mais conhecidos, BubbleSort, SelectionSort e InsertSort; demonstrar 
como funcionam e seus principais pontos positivos e negativos como desempenho e 
limitações. 
Palavras-chave: Ordenação, BubbleSort, SelectionSort, InsertSort. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ABSTRACT 
This work aims to demonstrate some of the methods of Most popular sorting, 
BubbleSort, SelectionSort and InsertSort; demonstrate how they work and their main 
strengths and weaknesses such as performance and limitations. 
 
Keywords: Sorting, BubbleSort, SelectionSort, InsertSort.. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
SUMÁRIO 
1. INTRODUÇÃO .................................................................................................. 6 
2. REFERENCIAL TEÓRICO ............................................................................... 7 
3. DESENVOLVIMENTO .................................................................................... 10 
4. RESULTADO .................................................................................................. 12 
5. CONCLUSÃO ................................................................................................. 13 
7. REFERÊNCIAS BIBLIOGRÁFICAS ................................................................. 14 
APÊNDICE. ........................................................................................................... 15 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1. INTRODUÇÃO 
 
De acordo com o prof. Dr. Os métodos de ordenação de João Luís Garcia Rosa 
(2011) destinam-se a simplificar, de forma mais rápida e económica a procura de 
informação específica num grande conjunto de informação. 
Algoritmos de ordenação em ciência da computação são algoritmos que 
colocam os elementos de uma determinada sequência em uma determinada ordem, 
ou seja, realizam uma ordenação total ou parcial sobre eles. Existem várias razões 
para ordenar uma sequência. Uma delas é o acesso mais eficiente aos seus dados. 
Reinaldo Fortes (2014) destaca o fato de que nenhum método é considerado 
universalmente superior a todos os outros. É necessário analisar o problema e, com 
base nas características dos dados, decidir qual o método mais adequado para ele. 
De acordo com o ebook Estruturas de Dados Usando C (1995) aspectos de 
medida de eficiência: tempo para codificação do programa de ordenação tempo de 
máquina para a execução do programa; espaço de memória necessário. 
Normalmente, o tempo gasto é medido pelo número de operações que são críticas 
para o programa que está sendo executado. Neste caso dos métodos de ordenação, 
as principais operações são: comparação; movimentação dos elementos da lista ou 
troca de posições. Medido analisando o melhor caso, o pior caso e o caso médio. O 
resultado é uma fórmula em função de n (número de registros no arquivo). 
No artigo Algoritmos de ordenação: análise e comparação (2013) no site da 
DEVMIDIA, o método BubbleSort é considerado o mais intuitivo e fácil de 
implementar, mas o menos eficiente. SelectSort Neste tipo de classificação, 
seleciona o menor elemento de um subvetor não classificado e o substitui pelo 
primeiro elemento desse subvetor. Insertsort é um algoritmo de ordenação 
ligeiramente diferente dos outros dois. 
 
 
 
 
2. REFERENCIAL TEÓRICO 
 
2.1. BubbleSort 
O método Bubblesort executa várias iterações na lista. Ele compara itens da lista 
com o item a sua direita executando a troca da posição quando necessário. De 
maneira geral a cada passagem da lista sempre o elemento de maior valor 
desordenada é colocado em sua posição correta. Essencialmente, cada item se 
move como uma “bolha” “subindo para posição correta” (MILLER; RANUM, 2013). 
A Figura 1 mostra a primeira interação. Itens sombreados são os itens que estão 
sendo comparados para ver se estão fora de ordem. Se houver n itens na lista, 
haverá n-1 pares de itens que precisam ser comparados na primeira iteração. Pode-
se observar que quando o valor mais alto da lista é comparado, ele é continuamente 
empurrado para o final da lista (MILLER; RANUM, 2013). 
 
Figura 1 – Exemplo de aplicação do algoritmo de ordenação BubleSort 
 
FONTE: (Panda, 2022) 
 
2.2. SelecSort 
Pode se dizer que o SelectionSort é uma melhora do BubbleSort por realizar 
uma troca a cada interação pela lista. O SelectionSort procura pelo valor mais alto 
enquanto faz uma interação e, depois de completá-la, coloca-o na posição correta. 
Assim como o BubbleSort, depois da primeira interação, o maior item sempre está 
na posição correta. Depois da segunda interação, o próximo maior item também vai 
para a posição adequada. O processo continua dessa forma até o penúltimo item, já 
que o item final deverá estar no lugar certo depois da penúltima interação (MILLER; 
RANUM 2013); como demostrado na Figura 2. 
Figura 2 - Exemplo de aplicação do algoritmo de ordenação SelectSort 
 
FONTE: (Panda, 2022) 
2.3. InsertSort 
InsertSort é diferente dos demais métodos citados. Ele cria uma lista no final da 
lista original, na qual irá servir de suporte onde serão inseridos os elementos 
ordenados. Cada item da lista original é comparado com os elementos da lista 
ordenada e inserido em sua posição correta na lista ordenada. A Figura 3 mostra a 
execução do InsertSort. Os elementos mais escuros pertencem a lista de suporte 
com os elementos ordenados cada passagem (MILLER; RANUM 2013). 
 
Figura 3 - Exemplo de aplicação do algoritmo de ordenação InsertSort 
 
FONTE: (Panda, 2022) 
Apensar do número de comparações para o InsertSort ser o mesmo que para o 
BubbleSort e SelectSort n−1, a operação realizada na ordenação dos elementos é a 
inserção do valor na lista, processo que requer menos processamento em 
comparação a troca de valores, método utilizado pelo BubbleSort e SelectSort. Com 
relação a desempenho, o InsertSort mostra melhores resultados (MILLER; RANUM, 
2013). 
3. DESENVOLVIMENTO 
 
3.1. Leitura dos dados 
Para teste dos algoritmos foi solicitado a ordenação de conjunto de dados 
armazenados em txt, sendo eles de 1000, 5000 e 10000 elementos, para leitura do 
dos arquivos e armazenamento em uma lista foi utilizado o método loadtxt da 
biblioteca Numpy como mostrado na Figura 4. 
 
Figura 4 - Trecho do código que efetua a leitura do conjunto de dados utilizados para 
comparação dos algoritmos 
 
Fonte: Autoria Própria 
3.2. BubbleSort 
O método BubbleSort recebe a lista carregada com os dados do txt e se inicia 
com a tomada o momento do início da execução; posteriormente utilizado para 
medição da performance do algoritmo e a definição de algumas classes necessárias, 
em seguida da inicio ao laço de repetição “while” onde há a implementação da lógica 
do algoritmo, após o termino do laço de repetição há a tomada do momento de 
finalização da ordenação, em seguida é salvo a lista ordenada em um txt de saída e 
o método se encerra retornando o tempo de execução da ordenação da lista. A 
implementação do método está ilustrada na Figura 5. 
 
Figura 5 - Trecho do código correspondente ao algoritmo BubbleSort 
 
Fonte: Autoria Própria 
 
3.3. SelectionSortO método SelectionSort segue o mesmo modelo de início e fim que o 
implementado no BubbleSort, a implementação da logica do método tem início no 
laço de repetição “for”. A implementação do método está ilustrada na Figura 6. 
 
Figura 6 - Trecho do código correspondente ao algoritmo SelectionSort 
 
Fonte: Autoria Própria 
 
3.4. InsertSort 
A implementação do método está ilustrada na Figura 7. 
 
Figura 7 - Trecho do código correspondente ao algoritmo InsertSort 
 
Fonte: Autoria Própria 
4. RESULTADO 
 
4.1. Comparação do tempo de execução. 
Tabela 1 - Tempo de execução ms 
Algoritmo 1000_numbers.txt 5000_numbers.txt 10000_numbers.txt
BubbleSort 247 6268 25025
SelectionSort 125 3192 12784
InserSort 0 2 5 
Fonte: Autoria Própria 
Figura 8 - Gráfico comparativo 
 
Fonte: Autoria Própria 
 
O BubbleSort obteve de longe o pior desempenho em todos os conjuntos de 
dados, demorando o dobro do tempo em comparação ao SelectSort, e o tempo de 
execução tanto do BubbleSort como SelectionSort aumentaram de forma 
exponencial, conforme o número de elemento aumenta no conjunto de dados, ao 
contrário do InsertSort que apresentou de longe o melhor desempenho e o aumento 
do tempo de execução ocorreu de forma linear conforme o número de elementos 
aumentava. 
 
 
5. Conclusão 
 
No trabalho foi apresentado alguns dos métodos de ordenação mais conhecidos, 
foi explicado como funcionam, seus desempenhos e foram também aplicados na 
prática em uma aplicação. Em relação aos desempenhos dos métodos, o InsetSort 
foi o algoritmo mais eficiente nos conjuntos de dados utilizados. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7. REFERÊNCIAS BIBLIOGRÁFICAS 
 
8 Algoritmos de Ordenação | Uma Introdução à Programação Disponível em: < 
https://bookdown.org/jessicakubrusly/programacao-estatistica/algoritmos-de-
ordenacao.html> Acesso em: 01 abr. 2022. 
Aaron Ai Tenenbaum, Yedidyah Langsam, Moshe J. Augenstein, 2013. 
“Estrutura de Dados I“. Disponível em: 
https://www.cin.ufpe.br/~garme/public/(ebook)Estruturas%20de%20Dados%20Usan
do%20C%20(Tenenbaum).pdf . Acesso em 30 de maio de 2022. 
Algoritmos de ordenação: análise e comparação, 2013. Disponível em: < 
https://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-
comparacao/28261>. Acesso em: 01 abr. 2022. 
FORTES, Prof. Reinaldo 2013. UFOP. “Estrutura de Dados I“. Disponível em: 
http://www.decom.ufop.br/reinaldo/site_media/uploads/2013-02-bcc202/aula_12_-
_bubblesort-selectionsort-insertionsort_(v1).pdf. Acesso em 30 de maio de 2022. 
GARCIA ROSA, Prof. Dr. João Luís 2011. USP. “Métodos de Ordenação “. 
Disponível em: http://wiki.icmc.usp.br/images/b/b3/SCC501Cap4.pdf . Acesso em 30 
de maio de 2022. 
https://bookdown.org/jessicakubrusly/programacao-estatistica/algoritmos-de-ordenacao.html
https://bookdown.org/jessicakubrusly/programacao-estatistica/algoritmos-de-ordenacao.html
https://www.cin.ufpe.br/~garme/public/(ebook)Estruturas%20de%20Dados%20Usando%20C%20(Tenenbaum).pdf
https://www.cin.ufpe.br/~garme/public/(ebook)Estruturas%20de%20Dados%20Usando%20C%20(Tenenbaum).pdf
https://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-comparacao/28261
https://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-comparacao/28261
http://www.decom.ufop.br/reinaldo/site_media/uploads/2013-02-bcc202/aula_12_-_bubblesort-selectionsort-insertionsort_(v1).pdf
http://www.decom.ufop.br/reinaldo/site_media/uploads/2013-02-bcc202/aula_12_-_bubblesort-selectionsort-insertionsort_(v1).pdf
http://wiki.icmc.usp.br/images/b/b3/SCC501Cap4.pdf
MILLER; RANUM, Brad e David, 2013. Problem Solving with Algorithms and Data 
Structures using Python. Disponível em: < 
https://runestone.academy/ns/books/published/pythonds/index.html l> . Acesso em: 
01 abr. 2022. 
 
 
APÊNDICE. 
 
import time 
from tkinter import N 
import numpy 
 
def BubbleSort(list): 
 init = time.time() 
 trocas = True 
 passo = len(list)-1 
 while passo > 0 and trocas: 
 trocas = False 
 for i in range(passo): 
 if list[i]>list[i+1]: 
 trocas = True 
 temp = list[i] 
 list[i] = list[i+1] 
 list[i+1] = temp 
 passo = passo-1 
 fimt = time.time() 
 txtsaida = open("lista_BoubbleSort.txt","w") 
 
 for d in list: 
 txtsaida.write(f"{d}\n") 
 return fimt-init 
 
def SelectionSort(list): 
 init = time.time() 
 for prencher in range(len(list)-1,0,-1): 
 pMax=0 
 for local in range(1,prencher+1): 
 if list[local]>list[pMax]: 
 pMax = local 
 
 temp = list[prencher] 
 list[prencher] = list[pMax] 
 list[pMax] = temp 
 fimt = time.time() 
 txtsaida = open("lista_SelectionSort.txt","w") 
 for d in list: 
 txtsaida.write(f"{d}\n") 
 return fimt-init 
 
 
 
 
def InsertionSort(list): 
 init = time.time() 
 
 for ind in range(1,len(list)): 
 valoratual = list[ind] 
 posicao = ind 
 
 while posicao>0 and list[posicao-1]>valoratual: 
 list[posicao]=list[posicao-1] 
 posicao = posicao-1 
 list[posicao]=valoratual 
 
 fimt = time.time() 
 txtsaida = open("lista_InsertionSort.txt","w") 
 for d in list: 
 txtsaida.write(f"{d}\n") 
 return fimt-init 
 
 
list= numpy.loadtxt("10000_numbers.txt") 
print("Tempo de execução BubbleSort: ",BubbleSort(list),"\n") 
print("Tempo de execução SelectionSort: ",SelectionSort(list),"\n") 
print("Tempo de execução InsertionSort: ",InsertionSort(list))