APS POTA

Prévia do material em texto

ATIVIDADE PRÁTICA SUPERVISIONADA
PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO
	OBJETIVOS DE APRENDIZAGEM
	Analisar os principais algoritmos de ordenação através da realização de experimentos empíricos.
	ATIVIDADES A SEREM DESENVOLVIDAS
Analisar o tamanho da entrada de dados para um programa de computador é importante para a escolha dos melhores algoritmos e estruturas de dados que serão utilizadas no desenvolvimento. Por exemplo, se em um programa é necessário ordenar por nota um conjunto de alunos de uma turma com 30 alunos, qualquer algoritmo de ordenação poderá ser utilizado. Porém, se é necessário ordenar um vetor com 1 milhão de compras em um e-commerce, a escolha do algoritmo de ordenação terá um grande impacto no tempo de execução da aplicação. 
Baseado no problema descrito, realizar um estudo comparativo entre os algoritmos de ordenação Bubble Sort, Selection Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort, utilizando como parâmetro o número de comparações realizadas por cada algoritmo. Deverão ser gerados 6 vetores de inteiros aleatórios com cada um dos seguintes tamanhos: 5, 10, 50, 100, 1.000 e 10.000. Em seguida, ordenar todos os vetores através de cada um dos métodos de ordenação propostos e contar o número de comparações entre os elementos em cada ordenação realizada. Ao final, gerar gráficos contendo o número médio de comparações realizadas por cada algoritmo para cada tamanho de vetor como os exemplos abaixo: 
DESENVOLVIMENTO
Como foram gerados os vetores aleatórios
Os vetores foram gerados a partir do algoritmo abaixo. Foi utilizado a classe Random para gerar números aleatórios e dentro disso limitamos o maior numero para 20000 e também criamos a condição que nenhum numero do vetor fosse repetido.
 public static int[] gerar(int n) {
 int numero;
 int[] num = new int[n];
 Random r = new Random();
 for(int i=0; i<num.length; i++){
 numero = r.nextInt(20000) + 1;
 for(int j=0; j<num.length; j++){
 if(numero == num[j] && j != i){
 numero = r.nextInt(20000) + 1;
 }else{
 num[i] = numero;
 }
 }
 }
 return num;
 }
Como foram adaptados os algoritmos para realizar a contagem do número de comparações; 
Foram iniciadas variáveis para funcionar como contador de comparações e para isso estas variáveis foram colocadas antes de cada if ou while.
O que foi desenvolvido para que cada algoritmo ordenasse os mesmos vetores que os demais; 
É atribuído ao vetor “v”, no método principal, o vetor gerado pelo método “gerar” e com isso todos os métodos dos algoritmos de ordenação recebem o mesmo vetor para ser ordenado.
 public static void main(String[] args) throws IOException {
 //Scanner e entrada do tamanho dos vetores
 Scanner entrada = new Scanner(System.in); 
 int numAleatorio;
 System.out.println("Insira o tamanho do vetor: ");
 numAleatorio = entrada.nextInt();
 //Classe para gerar o vetor com a quantidade de elementos escolhida
 int[] v = gerar(numAleatorio);
 
 System.out.println("\nVetor Inicial: " + Arrays.toString(v));
 bubbleSort(v); 
 selectionSort(v);
 insertionSort(v);
 heapSort(v); 
 System.out.println("\nVetor Heap: " + Arrays.toString(v));
 System.out.println("--> Comparações Heap: " + contadorheap);
 int i = 0;
 int f = v.length;
 mergeSort(v, i, f);
 System.out.println("\nVetor Merge: " + Arrays.toString(v));
 System.out.println("--> Comparações Merge: " + contadormerge);
 quickSort(v, 0, v.length - 1);
 System.out.println("\nVetor Quick: " + Arrays.toString(v));
 System.out.println("--> Comparações Quick: " + contadorquick);
 }
 public static int[] gerar(int n) {
 int numero;
 int[] num = new int[n];
 Random r = new Random();
 for(int i=0; i<num.length; i++){
 numero = r.nextInt(20000) + 1;
 for(int j=0; j<num.length; j++){
 if(numero == num[j] && j != i){
 numero = r.nextInt(20000) + 1;
 }else{
 num[i] = numero;
 }
 }
 }
 return num;
 }
Explicar os resultados dos experimentos com base na literatura
Problema
Com o propósito de conceder uma solução para certos problemas, temos algoritmos de ordenação, cada problema possui um algoritmo adequado a uma solução mais rápida e adequada, um tipo de busca e um método para organizar. Descrevendo o passo para chegar a uma solução, em alguns casos, os algoritmos de ordenação genéricos não servem para resolver e com isso as vezes precisamos altera-lo.
Algoritmos de Ordenação
Algoritmo de ordenação, em ciência da computação, é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem, crescente ou decrescente. Em outras palavras, efetua sua ordenação completa ou parcial. O objetivo da ordenação é facilitar a recuperação dos dados de uma lista.
Bubble Sort
É simples, mas o menos eficiente. Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1, e assim por diante. 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ário, tornando o algoritmo ineficiente para listas muito grandes.
Para listas já ordenadas em ordem crescente é o único algoritmo que não realiza movimentações, mas em compensação é o que tem o maior tempo e o maior número de comparações. Não só em listas já ordenadas, mas em todos os casos o bubble sort se mostrou um algoritmo ineficiente.
Selection Sort
Este algoritmo é baseado em 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
Na lista de ordem 1, o Insertion sort se mostrou mais eficiente que todos os outros algoritmos em relação ao tempo e comparações. Na lista de ordem 2 foi menos eficiente do que o selection sort e na lista de ordem 3 a diferença de tempo entre o insertion e o selection foi pequena.
Heap Sort
O heapsort utiliza uma estrutura de dados chamada heap binário para ordenar os elementos a medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada. Um heap binário é uma árvore binária mantida na forma de um vetor.
O heap é gerado e mantido no próprio vetor a ser ordenado. Para uma ordenação crescente, deve ser construído um heap máximo (o maior elemento fica na raiz). Para uma ordenação decrescente, deve ser construído um heap mínimo (o menor elemento fica na raiz).
Merge Sort
O Mergesort é classificado como ordenação por partição, que parte do princípio de
"dividir para conquistar". Este princípio é uma técnica que foi utilizada pela primeira
vez por Anatolii Karatsuba em 1960 e consiste em dividir um problema maior em
problemas pequenos, e sucessivamenteaté que o mesmo seja resolvido diretamente.
Esta técnica realiza-se em três fases:
Divisão: o problema maior é dividido em problemas menores e os problemas menores
obtidos são novamente divididos sucessivamente de maneira recursiva.
Conquista: o resultado do problema é calculado quando o problema é pequeno o
suficiente.
Combinação: os resultados dos problemas menores são combinados até que seja
obtida a solução do problema maior. Algoritmos que utilizam o método de partição são
caracterizados por serem os mais rápidos dentre os outros algoritmos pelo fato de sua
complexidade ser, na maioria das situações, O(nlogn). Os dois representantes mais
ilustres desta classe são o quicksort e o mergesort.
Quick sort
O Quick sort é o algoritmo mais eficiente na ordenação por comparação. Nele se escolhe um elemento chamado de pivô, a partir disto é organizada a lista para que todos os números anteriores a ele sejam menores que ele, e todos os números posteriores a ele sejam maiores que ele. Ao final desse processo o número pivô já está em sua posição final. Os dois grupos desordenados recursivamente sofreram o mesmo processo até que a lista esteja ordenada.
O quick sort certamente é o algoritmo mais eficiente em listas totalmente desordenadas, ele se torna muito eficiente em relação aos outros no quesito de tempo. Na lista de ordem 3 e na de ordem 2 a diferença de tempo do quick sort em comparação aos outros foi absurdamente grande.
ALGORITMO GERADO
package aps;
import static aps.heap.contadorheap;
import static aps.heap.heapSort;
import static aps.bubble.bubbleSort;
import static aps.selection.selectionSort;
import java.io.IOException;
import java.util.Random;
import java.util.Arrays;
import java.util.Scanner;
public class apspota { //PRINCIPAL
 private static int contadorquick = 0;
 private static int contadormerge = 0;
 public static void main(String[] args) throws IOException {
 //Scanner e entrada do tamanho dos vetores
 Scanner entrada = new Scanner(System.in); 
 int numAleatorio;
 System.out.println("Insira o tamanho do vetor: ");
 numAleatorio = entrada.nextInt();
 //Classe para gerar o vetor com a quantidade de elementos escolhida
 int[] v = gerar(numAleatorio);
 
 System.out.println("\nVetor Inicial: " + Arrays.toString(v));
 bubbleSort(v); 
 selectionSort(v);
 insertionSort(v);
 heapSort(v); 
 System.out.println("\nVetor Heap: " + Arrays.toString(v));
 System.out.println("--> Comparações Heap: " + contadorheap);
 int i = 0;
 int f = v.length;
 mergeSort(v, i, f);
 System.out.println("\nVetor Merge: " + Arrays.toString(v));
 System.out.println("--> Comparações Merge: " + contadormerge);
 quickSort(v, 0, v.length - 1);
 System.out.println("\nVetor Quick: " + Arrays.toString(v));
 System.out.println("--> Comparações Quick: " + contadorquick);
 }
 
 private static void insertionSort(int[] vetor) {
 int contador = 0;
 int x, j;
 for (int i = 1; i < vetor.length; i++) {
 x = vetor[i];
 j = i-1;
 contador++;
 while((j>-0)&& vetor[j]>x){
 vetor[j+1]=vetor[j];
 j=j-1;
 }
 vetor[j+1]=x;
 }
 System.out.println("\nVetor Insertion: " + Arrays.toString(vetor));
 System.out.println("--> Comparações Insertion: " + contador);
 }
 
 private static int quickSort(int[] vetor, int inicio, int fim) {
 
 if (inicio < fim) {
 contadorquick++;
 int posicaoPivo = separar(vetor, inicio, fim);
 quickSort(vetor, inicio, posicaoPivo - 1);
 quickSort(vetor, posicaoPivo + 1, fim);
 }
 return contadorquick;
 } 
 private static int separar(int[] vetor, int inicio, int fim) {
 int pivo = vetor[inicio];
 int i = inicio + 1, f = fim;
 while (i <= f) {
 contadorquick++;
 if (vetor[i] <= pivo) {
 contadorquick++;
 i++;
 } else if (pivo < vetor[f]) {
 
 f--;
 } else {
 
 int troca = vetor[i];
 vetor[i] = vetor[f];
 vetor[f] = troca;
 i++;
 f--;
 }
 }
 vetor[inicio] = vetor[f];
 vetor[f] = pivo;
 return f;
 }
 
 public static void mergeSort(int[] vet, int i, int f) {
 contadormerge++;
 if (i < f) {
 int m = (i + f) / 2;
 mergeSort(vet, i, m);
 mergeSort(vet, m + 1, f);
 intercala(vet, i, m, f);
 }
 }
 public static void intercala(int[] vet, int i, int m, int f) {
 int vet2[] = new int[vet.length];
 for (int j = i; j <= m; j++) {
 vet2[j] = vet[j];
 }
 for (int g = m + 1; g < f; g++) {
 vet2[f + m - g] = vet[g];
 }
 int x = i;
 int z = f - 1;
 for (int k = i; k < f; k++) {
 contadormerge++;
 if (vet2[x] <= vet2[z]) {
 vet[k] = vet2[x];
 x = x + 1;
 } else {
 vet[k] = vet2[z];
 z = z - 1;
 }
 } System.out.println(contadormerge);
 }
 
 public static int[] gerar(int n) {
 int numero;
 int[] num = new int[n];
 Random r = new Random();
 for(int i=0; i<num.length; i++){
 numero = r.nextInt(20000) + 1;
 for(int j=0; j<num.length; j++){
 if(numero == num[j] && j != i){
 numero = r.nextInt(20000) + 1;
 }else{
 num[i] = numero;
 }
 }
 }
 return num;
 }
}
package aps;
import java.util.Arrays;
public class bubble extends apspota {
 
 public static void bubbleSort(int[] vetor) {
 int aux;
 int contadorbubble = 0;
 boolean controle;
 
 for (int i = 0; i < vetor.length; i++) {
 controle = true;
 for (int j = 0; j < (vetor.length-1); j++) {
 contadorbubble ++;
 if (vetor[j] > vetor[j + 1]) {
 aux=vetor[j];
 vetor[j]=vetor[j+1];
 vetor[j+1]=aux; 
 controle = false;
 }
 }
 if(controle){
 break;
 }
 }
 System.out.println("\nVetor Bubble: " + Arrays.toString(vetor));
 System.out.println("--> Comparações Bubble: " + contadorbubble);
 }
 
}
package aps;
public class heap extends apspota{
 
 public static int contadorheap;
 
 public static void heapSort(int[] v) {
 
 
 buildMaxHeap(v);
 int n = v.length;
 for (int i = v.length - 1; i > 0; i--) {
 swap(v, i, 0);
 maxHeapify(v, 0, --n);
 }
 }
private static void buildMaxHeap(int[] v) {
 for (int i = v.length / 2 - 1; i >= 0; i--)
 maxHeapify(v, i, v.length);
 }
 private static void maxHeapify(int[] vetor, int pos, int tamanhoDoVetor) 
 { 
 int max = 2 * pos + 1, right = max + 1; 
 contadorheap++;
 if (max < tamanhoDoVetor) 
 { 
 contadorheap++;
 if (right < tamanhoDoVetor && vetor[max] < vetor[right]) 
 max = right;
 contadorheap++;
 if (vetor[max] > vetor[pos]) 
 { 
 swap(vetor, max, pos);maxHeapify(vetor, max, tamanhoDoVetor); 
 } 
 } 
}
 public static void swap(int[] v, int j, int aposJ) {
 int aux = v[j];
 v[j] = v[aposJ];
 v[aposJ] = aux;
 }
 }
package aps;
import java.util.Arrays;
public class selection extends apspota{
 
 public static void selectionSort(int[] vetor) {
 int contadors = 0;
 for(int i = 0; i < vetor.length; i++){
 int menor = i;
 
 for(int j = i+1; j < vetor.length; j++){ 
 contadors++;
 if(vetor[j] < vetor[menor]){
 menor = j;
 }
 }
 mudar(vetor,i,menor);
 
 } 
 System.out.println("\nVetor Selection: " + Arrays.toString(vetor));
 System.out.println("--> Comparações Selection:"+ contadors);
 
 }
 
 public static void mudar(int[] vetor, int i, int menor) {
 int aux = vetor[i];
 vetor[i] = vetor[menor];
 vetor[menor] = aux; }	}
RESULTADO
Os gráficos abaixo foram gerados a partir da média dos valores obtidos a partir da execução do algoritmo em cinco vezes.
Valores para vetor de 5 posições:
Valores para vetor de 10 posições:
Valores para vetor de 50 posições:
Valores para vetor de 100 posições:
Valores para vetor de 1000 posições:
Valores para vetor de 10000 posições:
REFERÊNCIAS
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.2.5
http://www2.dcc.ufmg.br/livros/algoritmos-java/cap4/transp/completo1/cap4.pdf
Análise Da Complexidade De Algoritmos
http://www.ruirossi.pro.br/livros/li-rui-pcj-cap19.pdf
Estrutura de Dados – UNICAMP - André Pereira Giacon, Dandara Contieri Folis, Diego Narciso Hernandes e Fernanda Cristina Spadotim
https://www.ft.unicamp.br/liag/siteEd/