EDI Projeto 02 (Documentação)

Prévia do material em texto

UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
1 Professor e orientador do Projeto II da disciplina Estrutura de Dados I 
2 Discentes da disciplina Estrutura de Dados I 
 
 
 
 
MÉTODOS DE ORDENAÇÃO 
 
 
 
Prof. Dr. Alcides Xavier Benicasa1 < alcides@ufs.br> 
Gilmario dos Santos Silva2 <gilmariosantos1@gmail.com> 
Humberto Cardoso Lima2 <humberto.c.lima18@gmail.com> 
 Matheus Carneiro N. Da Silva2 <matcar007@gmail.com> 
 
 
RESUMO 
 
 
 
A Estrutura de Dados I, possui em sua essência fazer com que o aluno entenda 
como os dados são organizados em determinados momentos. Este trabalho 
procura demonstrar a aplicação de métodos de ordenação, eles são utilizados 
para melhorar o desempenho das aplicações, sejam elas, na inserção de 
dados ou na pesquisa. Este trabalho foi desenvolvido em linguagem de 
programação Java utilizando a IDE Eclipse. 
 
PALAVRAS-CHAVES: Estrutura, Dados, desempenho, métodos, Linguagem Java e 
Aplicação. 
 
ABSTRACT: 
 
Title: “METHODS OF ORDINATION” 
 
Data Structure I essentially has the student understand how the data is organized at 
certain times. This work seeks to demonstrate the application of sorting methods, they 
are used to improve the performance of applications, be they in data insertion or in 
research. This work was developed in Java programming language using the Eclipse 
IDE. 
 
KEYWORDS: Structure, Data, Performance, Methods, Java Language and Application. 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
 
1 INTRODUÇÃO 
 
A apresentação deste projeto faz parte à avaliação final da disciplina 
Estrutura de Dados I, sendo assim, neste momento procura-se demonstrar o 
entendimento do conteúdo apresentado pelo professor em sala de aula. Serão 
trabalhados os métodos de ordenação. 
Quando os usuários estão utilizando seus aplicativos que requer 
busca ou gravação de dados, nem imagina o “trabalho” complexo que o 
software terá que fazer para deixar tudo organizado, amigável ao olho humano, 
ordenado da forma que o operador quer. A aplicação é quem se preocupa em 
fazer o trabalho pesado para que o utilizado da aplicação nem perceba o que 
está acontecendo em background. 
Aplicação da estrutura de dados pode ser implantada na maioria dos 
sistemas existentes hoje no mercado, desde uma simples ordenação de pastas 
no Sistema Operacional Windows, até buscas em banco de dados de pessoas 
de uma agência bancária. 
Será demonstrada uma aplicação feita em Java, para mostrar as 
funcionalidades de cada método e seus respectivos desempenhos. Desta 
forma fica mais fácil de entender como é o comportamento de cada método em 
tempo de execução. Os métodos utilizado neste projeto são: BubbleSort, 
SelectionSort, InsertionSort, Shellsort, HeapSort, MergeSort e QuickSort. 
As possibilidades de utilização são bem diversificadas, nosso estudo 
de caso foi para desenvolver um Software no qual pode fazer as operações 
que cada tem por função, ou seja, reconhecer um ordenar dados. O programa 
foi desenvolvido em linguagem Java. 
 
2 DESENVOLVIMENTO DOS MÉTODOS DE ORDENAÇÃO 
 
Os métodos de ordenação pega os dados que estão desordenados 
e através de seu parâmetro de funcionamento deixa em ordem, todos fazem a 
mesma coisa, ordena dados. Porém, o que diferencia um do outro é custo que 
desta operação, seja em tempo, ou consumo de memória do computador. 
O entendimento de cada funcionalidade que cada método faz é de 
extrema importância para o sucesso ou não de uma aplicação, pois sem esse 
conhecimento, ao invés de aumentar o desempenho da aplicação, ele pode 
diminuir. Já com o entendimento do que cada método faz e conhecimento da 
base de dados e tipos de dados que quer ordenar, o programador pode decidir 
em utilizar um tipo que seja mais adequada. 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
2.1 Linguagem Java 
 
A história começa em 1991, em San Hill Road empresa filiada a Sun 
(da qual hoje pertence a empresa Oracle), formado pelo time de engenheiros 
lliderados por Patrick Naugthon, Sun Fellow e James Gosling. 
A linguagem de programação chamada de Oak (carvalho) foi criada 
pelo chefe do projeto James Gosling. A explicação da origem do nome foi que 
enquanto pensava numa estrutura de diretórios para a linguagem, observava 
pela janela um carvalho. Mas esse nome já estava registrado, então o nome 
acabou surgindo na cafeteria local da cidade onde tomavam café. “Java”, pois 
era o nome da terra de origem do café, que os programadores da equipe 
apreciavam nessa cafeteria, por isso que a logo do Java é um café. 
Dentro das características, o principal item é o fator da 
“Independência de plataforma”. Hoje a maioria das linguagens sofrem na 
transferência de plataforma quando o sistema desenvolvido tem que migrar 
para outra plataforma, pois quando compilado um programa a ação do 
compilador é transformar o arquivo-fonte em código de máquina. 
 
3 SOBRE O PROJETO 
 
O desenvolvimento da aplicação foi feito para ordenar dados, foi 
utilizado a linguagem de programação Java, a IDE eclipse e o componente 
WindowBuilder. Tendo como estrutura principal localizado no pacote ordena a 
classe OrdenaTodos, bem como as classes: BubbleSort, SelectionSort, InsertSort, 
Shellsort, HeapSort, MergeSort e QuickSort. Temos também a classe 
DemonstracaoGrafica localizada no pacote gráfico, esta é a responsável pela 
demonstração gráfica das operações e analise de complexidade dos métodos. 
 
3.1 Opções e funcionalidades 
Quando o sistema é executado aparecerá a tela com 7 botões um 
para cada método, ao clicar no botão correspondente a um algoritmo aparecerá 
a label com a análise de complexidade e comparações do método desejado. 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
 
Figura 1 - Tela de Início 
3.2 Bubble Sort 
 
Este método é o mais simples e por sua vez o menos eficiente, ele 
funciona basicamente comparando o elemento da posição k pelo elemento da 
posição k+1. Desta forma o número de comparações, onde K é o número de 
itens no vetor: k*(k-1)/2 ou cerca de k2 /2. 
 
Figura 2 - Esquema de Funcionamento 
 É verificado se o 3 é maior que 5, por essa condição ser falsa, não há 
troca. 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
 É verificado se o 5 é maior que 1, por essa condição ser verdadeira, há 
uma troca. 
 É verificado se o 5 é maior que 2, por essa condição ser verdadeira, há 
uma troca. 
 É verificado se o 5 é maior que 4, por essa condição ser verdadeira, há 
uma troca. 
 O método retorna ao início do vetor realizando os mesmos processos de 
comparações, isso é feito até que o vetor esteja ordenado 
 
 
 
 
 
 
 
 
Figura 3 – Código do Método Bubble Sort 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
3.3 Selection Sort 
 
Este método pega um elemento do vetor e compara com todos os 
outros, caso ele seja o menor, movimenta até o início do vetor, depois pega 
outro elemento e faz a mesma comparação para procurar o segundo menor 
valor(ou maior depende da ordem requerida). 
 
Figura4 – Esquema de Funcionamento 
 Neste passo o primeiro número escolhido foi o 3, ele foi comparado com 
todos os números à sua direita e o menor número encontrado foi o 1, 
então os dois trocam de lugar. 
 O mesmo processo do passo 1 acontece, o número escolhido foi o 5 e o 
menor número encontrado foi o 2. 
 Não foi encontrado nenhum número menor que 3, então ele fica na 
mesma posição. 
 O número 5 foi escolhido novamente e o único número menor que ele à 
sua direita é o 4, então eles trocam. 
 Vetor já ordenado. 
 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
 
Figura 5 – Código Fonte do Método 
3.4 Insertion Sort 
 
A eficiência deste algoritmo ocorre em listas pequenas e/ou médias, 
neste exemplo a lista é percorrida da esquerda para direita, ao avançar ele 
deixa os elementos mais a esquerda ordenados. 
 
Figura 06 - Esquema de Funcionamento 
 Neste passo é verificado se o 5 é menor que o 3, como essa condição é 
falsa, então não há troca. 
 É verificado se o quatro é menor que o 5 e o 3, ele só é menor que o 5, 
então os dois trocam de posição. 
 É verificado se o 2 é menor que o 5, 4 e o 3, como ele é menor que 3, 
então o 5 passa a ocupar a posição do 2, o 4 ocupa a posição do 5 e o 3 
ocupa a posição do 4, assim a posição do 3 fica vazia e o 2 passa para 
essa posição. 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
O mesmo processo de comparação acontece com o número 1, após esse 
processo o vetor fica ordenado. 
 
Figura 7 - Código do Método Insert Sort 
 
3.5 Shell Sort 
Baseado na ordenação por inserção, mas adiciona um novo recurso 
que melhora muito o desempenho da ordenação por inserção. 
 A razão da eficiência do algoritmo ainda não é conhecida. 
 Ninguém ainda foi capaz de analisar o algoritmo. 
 A sua análise contém alguns problemas matemáticos muito difíceis. 
 A começar pela própria sequência de incrementos. 
 O que se sabe é que cada incremento não deve ser múltiplo do anterior. 
 Conjecturas referente ao número de comparações para a sequência de 
Knuth: Conjectura 1 : C(n) = O(n1,25) Conjectura 2 : C(n) = O(n (ln n)2 ) 
 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
 
Figura 8 – Código do Método Shell 
3.6 Heap Sort 
É baseada no princípio de funcionamento da ordenação por seleção, 
ele seleciona o menor vetor, troca pelo item da primeira posição, repete a 
operação para os demais, só que a partir do segundo, troca pelo segundo 
menor, terceiro menor, etc. Aplicações: Sistemas operacionais, paginação de 
memória, ordenação, simulação de eventos. 
 
Figura 10 - Código Heap Sort 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
 
Figura 11 - Código Heap Sort 
 
3.7 Merge Sort 
 
Ele divide a quantidade de dados em pequenos pedaços e aplica a 
recursividade para resolver primeiro os problemas pequenos e depois junta 
todos para forma um todo. 
 
 
Figura 12 - Esquema Merge Sort 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
3.8 Quick Sort 
 
“Dividir para conquistar”, este método divide os dados em dois 
subvetores, o quick sort é realizado na primeira metade do vetor através da 
recursividade, depois realiza a operação no outro lado. No processo primeiro 
define um “pivô”, todos os dados da esquerda é menor e os da direita são 
maiores. Desta forma este é o método mais eficiente. 
 
Figura 23 - Esquema Merge Sort 
 O número 3 foi escolhido como pivô, nesse passo é procurado à sua 
direita um número menor que ele para ser passado para a sua 
esquerda. O primeiro número menor encontrado foi o 1, então eles 
trocam de lugar. 
 Agora é procurado um número à sua esquerda que seja maior que ele, o 
primeiro número maior encontrado foi o 5, portanto eles trocam de lugar. 
 O mesmo processo do passo 1 acontece, o número 2 foi o menor 
número encontrado, eles trocam de lugar. 
 O mesmo processo do passo 2 acontece, o número 4 é o maior número 
encontrado, eles trocam de lugar. 
 O vetor desse exemplo é um vetor pequeno, portanto ele já foi 
ordenado, mas se fosse um vetor grande, ele seria dividido e 
recursivamente aconteceria o mesmo processo de escolha de um pivô e 
comparações. 
 
4 CONCLUSÃO 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
 
O estudo da Estrutura de Dados é válido como parte da formação do 
estudante de Sistema de Informação, fazendo com que o discente conheça a 
estrutura de funcionamento dos métodos de ordenação, assim, tem-se a 
compreensão mais aprofundada das funcionalidades dos métodos de 
ordenação, desta forma quando precisar utilizar uma estrutura saberá, de 
acordo com os dados, qual método utilizar. O trabalho ajudou na compreensão 
do conteúdo apresentado em sala de aula pelo Professor. 
 
5 REFERÊNCIAS 
 
BENICASA, Alcides Xavier. Notas de Aula: Estrutura de Dados I, UFS, 2017.2. 
WindowBuilder. Disponível em: < 
http://help.eclipse.org/oxygen/index.jsp?topic=/org.eclipse.wb.doc.user/html/inst
allation/index.html> . Acesso em 28 de fevereiro de 2018. 
Algoritmos de ordenação: análise e comparação. Disponível em: < 
https://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-
comparacao/28261> . Acesso em 02 de março de 2018. 
Ordenação com Selection Sort, Insertion Sort, Bubble Sort, Merge Sort, 
Quick Sort, Heap Sort em Java. Disponível em: < 
http://www.kelvinsantiago.com.br/ordenacao-com-selection-sort-insertion-sort-
bubble-sort-merge-sort-quick-sort-heap-sort-em-java/>. Acesso em 03 de 
março de 2018. 
Algoritmos e Estruturas de Dados II: Ordenação – Shellsort. Disponível em: < 
https://web.inf.ufpr.br/menotti/ci056-2015-2-1/slides/aulaORDShellSort.pdf>. 
Acesso em 04 de março de 2018. 
Algoritmos e Estruturas de Dados II: Ordenação: Heapsort. Disponível em: < 
http://homepages.dcc.ufmg.br/~cunha/teaching/20121/aeds2/heapsort.pdf>. 
Acesso em 04 de março de 2018. 
Estrutura de Dados e Algoritmos. Disponível em: < 
http://www.cos.ufrj.br/~rfarias/cos121/aula_07.html>. Acesso em 04 de março 
de 2018. 
UNIVERSIDADE FEDERAL DE SERGIPE 
DEPARTAMENTO DE SISTEMA DE INFORMAÇÃO 
SISTEMAS DE INFORMAÇÃO – CAMPUS ITABAIANA 
PROJETO 02 DE ESTRUTURAS DE DADOS I 
 
Métodos de Ordenação. Disponível em: < 
https://marikonishi.wordpress.com/category/metodos-de-ordenacao/>. Acesso 
em 05 de março de 2018. 
Estrutura de Dados. Disponível em: < http://slideplayer.com.br/slide/86368//>. 
Acesso em 05 de março de 2018.