APS - UNIP - JAVA

Prévia do material em texto

UNIVERSIDADE PAULISTA – UNIP
CIÊNCIA DA COMPUTAÇÃO
 
 
 
 
Francisco Mateus Vasconcelos - N144327
Marcelo Menezes dos Santos Oliveira - B4964F0
Pedro Henrique Adornelas de Britto - N1635F8
 
 
 
 
 
 
 
ATIVIDADES PRÁTICAS SUPERVISIONADAS: ORDENAÇÃO DE DADOS
 
 
 
 
 
 
 
 
 
 
São Paulo
2018
Francisco Mateus Vasconcelos 
Marcelo Menezes dos Santos Oliveira
Pedro Henrique Adornelas de Britto
 
 
 
 
 
 
 
 
 
 
 
ATIVIDADES PRÁTICAS SUPERVISIONADAS: ORDENAÇÃO DE DADOS 
 
 
 
 
 
Trabalho apresentado como requisito para aprovação no 4o semestre da disciplina de Atividades Práticas Supervisionadas (APS) do curso de Ciência da Computação – UNIP.
 
 
 
São Paulo
2018
Objetivo 
Este trabalho tem como objetivo iniciar os estudos e aprimorar nosso conhecimento na área da ciência da computação, mais especificamente no uso de linguagens específicas para criação de programas com algoritmos de ordenação. Neste trabalho, utilizaremos uma linguagem orientada a objetos para ilustrar situações reais onde a programação poderá ser utilizada, iremos utilizar a linguagem Java juntamente com a IDE (Ambiente de Desenvolvimento Integrado) Eclipse para a confecção e manutenção do programa criado.
 	Será desenvolvido através da ferramenta ECLIPSE um programa orientado a objeto com foco principal em ordenação de dados, utilizamos três algoritmos de ordenação para exibir os dados.
	 
	
	
Sumário
1.	Introdução
Diariamente o ser humano tem a necessidade de trabalhar com dados ordenados. Como por exemplo, a lista telefônica que cataloga os registros por Ordem alfabética ou até mesmo ao criar uma planilha em Excel e classificar os registros conforme for necessário, conforme a humanidade avança o número de dados também aumenta, com isso, há necessidade de algoritmos de ordenação que suportem grandes quantidades de registros são necessários diariamente.
	Algoritmo de ordenação tem como objetivo principal catalogar os elementos e ordenar obedecendo a uma determinada ordem, basicamente eles efetuam a ordenação e organização dos dados que estão dentro de um vetor. O processo de ordenação pode garantir uma melhora no desempenho de pesquisa, ao realizar uma pesquisa sequência evita a varredura completa dentro de um vetor, otimizando a pesquisa e o retorno de dados. 
	Algoritmo de ordenação em ciência da computação normalmente é um vetor com N elementos, através de um algoritmo que coloca os elementos em uma sequência de ordem numérica ou lexicográfica( quando ordenamos palavras ou textos). Em outras palavras, efetua sua ordenação completa ou parcial. 
A ordenação pode ser realizada dentro de uma matriz do valor mais baixo para o mais alto (ordem crescente) ou ainda mais alto para o mais baixo (ordem crescente), sem essa ordenação todo e qualquer tipo de pesquisa realizada se torna muito lento é difícil. 
	Existem milhares de razões para realizar uma ordenação, dentre delas é a possibilidades de acessar os dados de uma forma mais eficiente, tornando o retorno da informação mais dinâmica e com maior velocidade, também é possível agrupar os dados em classes e a atualização de arquivos sequenciais. 
Os algoritmos de ordenação mais simples e mais utilizados para realizar a ordenação de dados: Bubble Sort (ordenação tipo bolha), SelectSort (ordenação por seleção).	
2.	Algoritmos de ordenação 
	Algoritmo é uma forma de resolução de problemas. Podendo ser implementado com qualquer sequência de valores, objetos que possuam uma lógica infinita, de forma que possa fornecer uma sequência lógica. 
2.1	Insertion Sort
	Algoritmo simples, com uma performance ruim para grande quantidades de itens a serem ordenados. Normalmente utilizado em pequenas listas de ordenação. Um exemplo bem simples de ordenação por inserção é a forma de classificamos as cartas de baralho em nossas mãos, ao recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma que as cartas obedeçam a ordenação. Sistema de ordenação funciona dessa forma:
Algoritmo pega o valor inicial e realiza a comparação que está entrando com os outros itens, até que se sua posição seja encontrada. Essa comparação é feita em direção à esquerda. 
Se o valor que está sendo comparado for menos que o valor em questão, ele será deslocado para a direita, desta forma será aberto um novo espaço para inserir o valor na posição vazia; 
Finalmente ao encontrar um item maior ou não haver mais itens, significa que você encontrou a posição que este item deve estar: coloque o item “chave” na posição correspondente.
2.2	Bubble Sort
O algoritmo de ordenação BubbleSort é aplicado em arrays e listas dinâmicas. Sua função é ordenar os valores em forma crescente ou decrescente, basicamente ele pega o valor da posição atual e realiza a comparação com a próxima posição, caso a posição atual for maior que a posição posterior, algoritmo realiza a troca dos valores, caso o valor da posição atual seja menor que a posição posterior a troca não é realizada, processo será realizado até comparar todos os valores do array/lista dinâmica, esse foi um exemplo de ordenação descrente, caso deseje realizar a ordenação crescente, deve se realizar a comparação da posição atual com o valor a ser comparado, caso o valor da posição atual seja menor que o posterior, o algoritmo realizará a troca de posições, caso o valor da posição atual seja maior que o da posição posterior, não realiza a troca, apenas indo a posição posterior +1.
Esse algoritmo e de baixa complexidade, normalmente utilizado com poucos registros, pois ele percorrera o vetor quantas vezes for necessário, tornando algoritmo muitas vezes bastante lento e de pouca eficiência.
2.3	Selection Sort
Ordenação por seleção é um algoritmo que consiste em organizar os dados de forma que sempre o menor valor (ou o maior) passe à primeira posição de um vetor, em seguida o segundo menor na segunda posição, e assim sucessivamente.
O algoritmo é composto por um laço externo e um interno. O externo controla o índice inicial e o interno percorre os demais índices do vetor.
A primeira iteração inicia-se no índice 0 do laço externo, a cada iteração soma-se uma unidade até o final do vetor, o laço interno inicia a iteração no índice do externo + 1 percorrendo o restante do vetor da mesma forma.
	
3.	Desenvolvimento	
Para o desenvolvimento deste programa, abordamos 3 tipos de ordenação: Insert Sort, Select Sort e Bubble Sort.
Como base inicial do programa possuímos alguns checkbox relacionados a groupbox, os mesmo disponibilizam opções de ordenação para livre escolha do usuário, um TextArea onde é exibido os números desordenados(randômicos) ao abrir o programa, dois botões onde um dos ordena o array exibido na caixa de texto e um botão para fechar o programa.
Após a escolha de ordenação, o usuário deve clicar no botão “Ordenar”. Ao ser pressionado, o mesmo dispara um Action Command “ordenar” assim entrando na condição da classe void ordenar(). Ao entrar nesta classe verificamos a opção selecionada pelo usuário, utilizando o getState(), como vemos abaixo:
if(this.NOMECHECKBOX.getState() == true) {
	...codigo
} else if(this.NOMECHECKBOX2.getState() == true) {
	...codigo2
}
Após reconhecer a opção selecionada pelo usuário, o programa executa o algoritmo de ordenação dentro da mesma. Junto a este algoritmo também e calculado o tempo para a realização de toda a ordenação, utilizando o System.currentTimeMillis(), verificando o tempo de início e o tempo final:
long tempoInicial = System.currentTimeMillis();
long tempoFinal = System.currentTimeMillis();
double time = (tempoFinal - tempoInicial) / 1000d;
Desta forma inserimos o tempo dentro de um Label exibida na tela junto a opção selecionada.
Ao finalizar toda ordenação e executado o método void limparTela(), o qualdefine as opções de checkbox com o valor de “false”:
public void limparTela() {
this.selectionSort.setState(false);
	this.insertSort.setState(false);
	this.bubbleSort.setState(false);
}
A qualquer momento, a partir da execução do programa, o usuário tem ao seu alcance o botão de sair. Este botão ao receber um clique, envia um Action Command “sair”, o qual entra em uma condição if e executa a seguinte linha de código:
System.exit(0); (Este comando fecha o programa)
4.	Resultado e Discussões.
O programa de ordenação foi desenvolvimento em linguagem JAVA, para a realização dos testes, foram gerados os dados aleatoriamente, através do método Math.random, os registros gerados aleatórios foram armazenados no ARRAY “intArray” e exibido através do componente “intArray[x]” (sendo que “x” e uma variante).
Foi efetuado os testados e analisados os três métodos de ordenação com diversas quantidades de dados, podemos observar que todos os métodos de ordenação escolhidos tem um bom desempenho de ordenação com um array que possua até 80 registros, retornando e exibido a ordenação em tela em poucos segundos. 
Em seguida, realizamos mais uma análise de desempenho e eficiência de cada método de ordenação, porém desta vez com um array que contendo cerca de 1000 registros. O desempenho de ordenação apresentou certa lentidão,sistema demorou para retornar os dados ordenados, nos três diferentes métodos que possui o programa.
4.1	Teste InsertionSort
De acordo com testes realizados, conseguimos analisar o desempenho entre ordenar 80 registros e 1000 registros. Segue abaixo os testes realizados e seus respectivos tempos de ordenação:
Registros desordenados (80):
Registros ordenados (80):
 Tempo de ordenação médio de 0.017 milisegundos.
Registros desordenados (1000):
Registros ordenados (1000):
 Tempo de ordenação médio de 0.080 milisegundos.
4.2	Teste BubbleSort
Registros desordenados (80):
Registros ordenados (80):
 Tempo de ordenação médio de 0.098 milisegundos.
Registros desordenados (1000):
Registros ordenados (1000):
	 
 Tempo de ordenação médio de 0.090 milisegundos.
4.3	Teste SelectionSort
Registros desordenados (80):
 
Registros ordenados (80):
 
 Tempo de ordenação médio: 0.019 milisegundos.
Registros desordenados (1000):
Registros ordenados (1000):
 Tempo de ordenação médio: 0.090 milisegundos.
5.	Considerações Finais
Através das pesquisas, foi possível realizar um aprofundamento sobre o tema abordado (algoritmos de ordenação de dados de baixa complexidade). 
Podemos compreender a fundo a usabilidade de cada um dos tipos de ordenação, conforme descrito durante o trabalho. Cada algoritmo abordado, tem um objetivo específico, seja ele crescente, descrevente por inserção ou demais tipos, cabe analisar a necessidade e escolher a melhor ferramenta para solucionar o problema em questão, além da usabilidade dos dados, podemos também compreender o desempenho de cada um desses algoritmos, também foi possível observar o tempo de execução, com arrays com pouca quantidades de dados e também com arrays com um grande quantidade de dados.
Após realizar a análise de desempenho, foi observado que o desempenho dos algoritmos de ordenação durante o processamento do programa desenvolvido, respondem muito bem com arrays que possuam até 80 registros, após exceder esse número de registros, foi apresentada certa lentidão para realizar a ordenação de dados, através desta análise, foi possível chegar a conclusão que o desempenho de algoritmos de baixa complexidade tem um desempenho muito bom quando trabalhamos com arrays que tenham até 80 registros, após esse número de registros, podemos observar certa lentidão ao realizar as ordenações.
6.	Referências Bibliográficas
WIKIPEDIA. Insertion Sort. Disponível em:<https://pt.wikipedia.org/wiki/Insertion_
sort>. Acesso em Novembro/2018.
DEVMEDIA. 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 Novembro/2018.
GEEKSOFRGEEKS. Insertion Sort. Disponível em:
<hhttps://www.geeksforgeeks.org/insertion-sort/>. Acesso em Novembro/2018.
PROGRAMADORAPRENDENDO. Algoritmo: Quick Sort. Disponível em:
<http://programadoraprendendo.blogspot.com/2012/11/algoritmo-quick-sort.html>. Acesso em Novembro/2018.
PROGRAMADORAPRENDENDO. Algoritmo: Bubble Sort. Disponível em:
<http://programadoraprendendo.blogspot.com/2012/11/algoritmo-bubble-sort.html>. Acesso em Novembro/2018.
MEDIUM.Algoritmos de Ordenação I: Bubble Sort. Disponível Em:<https://mediu m.com/@henriquebraga_18075/algoritmos-de-ordena%C3%A7%C3%A3o-i-bubble-sort-c162a67261ef>. Acesso em Novembro/2018.
EMBARCANDOS. Algoritmos: Bubble Sort. Disponível em:
<https://www.embarcados.com.br/algoritmos-de-ordenacao-bubble-sort/>. Acesso em Novembro/2018.
COISASDEPROGRAMADOR. Algoritmos de ordenação Bubble Sort 
Disponível em:<https://www.coisadeprogramador.com.br/algoritmos-ordena
cao-bubble-sort/>. Acesso em Novembro/2018.
7.	Linha de Códigos
Classe Principal (main):
public class TelaPrincipal {
	public static void main(String[] args) {
		TelaBase t01 = new TelaBase();
	}
}
Tela Base:
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.io.IOException;
import java.util.Arrays;
import java.util.Random;
import javax.swing.JOptionPane;
import javax.swing.JTextArea;
import javax.swing.JTextField;
import javax.swing.*;
import java.awt.*;
import java.io.*;
public class TelaBase extends Frame 
implements ActionListener{
	Checkbox selectionSort = new Checkbox("Selection Sort");
	Checkbox insertSort = new Checkbox("Insertion Sort");
	Checkbox bubbleSort = new Checkbox("Bubble Sort");
	JTextArea result = new JTextArea();
	
	public int[] intArray = new int[80];
	public int[] vetor = new int[80];
	String[] Resultado = new String[80];
	
	Button ordenar = new Button("Ordenar");
	Button sair = new Button("Sair");
	
	TelaBase(){
		Dimension d01 = new Dimension(1150, 520);
		this.setSize(d01);
		
		this.setTitle("UNIP Paraiso - Ordenaçao");
		this.setLayout(null);
		Label lb02 = new Label("Código");
		lb02.setSize(50, 20);
		lb02.setLocation(1, 1);
		this.add(lb02);
		
		CheckboxGroup grupo = new CheckboxGroup();
		selectionSort = new Checkbox("Selection Sort", grupo, false);
		selectionSort.setBounds(5, 45, 130, 20);
 this.add(selectionSort);
 
 insertSort = new Checkbox("Insert Sort", grupo, false);
 insertSort.setBounds(5, 68, 130, 20);
 this.add(insertSort);
 
 bubbleSort = new Checkbox("Bubble Sort", grupo, false);
 bubbleSort.setBounds(5, 90, 130, 20);
 this.add(bubbleSort);
		for (int i = 0; i < this.intArray.length; i++) {
			this.intArray[i] = (int)(Math.random() * 100);
		}
		
		
		for(int p = 0; p < intArray.length; p++) {
			if(p%40 == 0) {
				result.append("\n");
			}
			Resultado[p] = ""+this.intArray[p]+" ";result.append(" "+Resultado[p]);
		}
		
		
		result.setBounds(150, 35, 980, 465);
 this.add(result);
 
 ordenar.setActionCommand("ordenar");
 ordenar.setBounds(5, 125, 130, 25);
 ordenar.addActionListener(this);
		this.add(ordenar);	
		
		sair.setActionCommand("sair");
 sair.setBounds(25, 460, 90, 25);
 sair.addActionListener(this);
		this.add(sair);	
		this.setResizable(false);
		this.setVisible(true);
	}
	@Override
	public void actionPerformed(ActionEvent arg0) {
		if (arg0.getActionCommand() == "ordenar") {
			try {
				this.ordenar();
			} catch (Exception e) {
				e.printStackTrace();
			}
			this.limparTela();
		} else if(arg0.getActionCommand() == "sair") {
			System.exit(0);
		}
	}
	
	public void ordenar() throws Exception {
		if(this.selectionSort.getState() == true) {
			long tempoInicial = System.currentTimeMillis();
			result.setText("");
			for (int i = 0; i < this.intArray.length - 1; i++) 
	 {
	 int index = i;
	 int num1 = 0;
	 int num2 = 0;
	 for (int j = i + 1; j < this.intArray.length; j++){
	 	if ( this.intArray[j] < this.intArray[index]){ 
	 index = j; 
	 } 
	 } 
	 int smallerNumber = this.intArray[index]; 
	 this.intArray[index] = this.intArray[i]; 
	 this.intArray[i] = smallerNumber; 
	 
	 
	 			if(i%40 == 0) {
	 				result.append("\n");
	 			}
	 			Resultado[i] = ""+this.intArray[i]+" ";
	 			result.append(" "+Resultado[i]);	 		
	 }
			
			long tempoFinal = System.currentTimeMillis();
			 
			 double t = (tempoFinal - tempoInicial) / 1000d;
			
			 Label lb01 = new Label("Tempo de execuçao:");
			 lb01.setBounds(10,220,200,30);
			 this.add(lb01);
			 
			 Label lb02 = new Label(Double.toString(t) + " milisegundos");
			 lb02.setBounds(10,240,200,30);
			 this.add(lb02);
			 
			 Label lb03 = new Label("Ordenado em:");
			 lb03.setBounds(30,160,200,30);
			 this.add(lb03);
			 
			 Label lb04 = new Label("Selection Sort");
			 lb04.setBounds(30,180,200,30);
			 this.add(lb04);
			
		} else if(this.insertSort.getState() == true) {
			long tempoInicial = System.currentTimeMillis();
			result.setText("");
			int n = this.intArray.length; 
	 for (int i=1; i<n; ++i) 
	 { 
	 int key = this.intArray[i]; 
	 int j = i-1; 
	 
	 while (j>=0 && this.intArray[j] > key) 
	 { 
	 	this.intArray[j+1] = this.intArray[j]; 
	 j = j-1; 
	 } 
	 this.intArray[j+1] = key; 
	 }
	 
	 for (int y=0; y<n; ++y) {
	 	if(y%40 == 0) {
 				result.append("\n");
 			}
	 	
	 	Resultado[y] = ""+this.intArray[y]+" ";
 			result.append(" "+Resultado[y]);	
	 }
	 
	 long tempoFinal = System.currentTimeMillis();
			 
			 double t = (tempoFinal - tempoInicial) / 1000d;
			
			 Label lb01 = new Label("Tempo de execuçao:");
			 lb01.setBounds(10,220,200,30);
			 this.add(lb01);
			 
			 Label lb02 = new Label(Double.toString(t) + " milisegundos");
			 lb02.setBounds(10,240,200,30);
			 this.add(lb02);
			 
			 Label lb03 = new Label("Ordenado em:");
			 lb03.setBounds(30,160,200,30);
			 this.add(lb03);
			 
			 Label lb04 = new Label("Insert Sort");
			 lb04.setBounds(30,180,200,30);
			 this.add(lb04);
			
			
		} else if(this.bubbleSort.getState() == true) {
			long tempoInicial = System.currentTimeMillis();
			result.setText("");
			
			int n = this.intArray.length;
	 for (int i = 0; i < n-1; i++)
	 for (int j = 0; j < n-i-1; j++)
	 if (this.intArray[j] > this.intArray[j+1])
	 {
	 int temp = this.intArray[j];
	 this.intArray[j] = this.intArray[j+1];
	 this.intArray[j+1] = temp;
	 }
	 
	 for (int x=0; x<n; ++x) {
	 	if(x%40 == 0) {
 				result.append("\n");
 			}
 			Resultado[x] = ""+this.intArray[x]+" ";
 			result.append(" "+Resultado[x]);	
	 }
	 long tempoFinal = System.currentTimeMillis();
			 
			 double t = (tempoFinal - tempoInicial) / 1000d;
			
			 Label lb01 = new Label("Tempo de execuçao:");
			 lb01.setBounds(10,220,200,30);
			 this.add(lb01);
			 
			 Label lb02 = new Label(Double.toString(t) + " milisegundos");
			 lb02.setBounds(10,240,200,30);
			 this.add(lb02);
			 
			 Label lb03 = new Label("Ordenado em:");
			 lb03.setBounds(30,160,200,30);
			 this.add(lb03);
			 
			 Label lb04 = new Label("Bubble Sort");
			 lb04.setBounds(30,180,200,30);
			 this.add(lb04);
		}
	}	
	public void limparTela() {
		this.selectionSort.setState(false);
		this.insertSort.setState(false);
		this.bubbleSort.setState(false);
	}
}
8. Fichas APS