Algoritmos de Ordenação em Java

Prévia do material em texto

Pesquisa, Ordenação e Técnicas de Armazenamento
Algoritmos de ordenação
Atividade Pratica Supervisionada
Fernando Roberto Sedano Sanchez RA: 21208264
Linguagem de programação: Desenvolvido na linguagem de programação Java. 
Método de geração de vetores aleatórios: Utilizamos um método da biblioteca da linguagem Java chamado Math.ramdon que tem objetivo de gerar numeros aleatórios. 
Adaptação dos algoritmos para realizarem a contagem do numero de comparações: Criamos uma variável em todos os algoritmos que soma toda vez que ocorre comparação no algoritmo e no final ela é imprimida. 
Criação de um método para que cada algoritmo ordenasse os mesmos vetores que os demais: Foi criado um método que cópia um vetor em outro elemento por elemento, e ele é usado antes de cada algoritmo para colocar o vetor em desordem. 
Analise do desempenho dos algoritmos: O desempenho dos algoritmos foi realizado através de gráficos de barra. 
Solução Proposta
Preenche o vetor com elementos aleatórios de 0 até seu tamanho
Gera um valor randômico de 0.0 até menores que 1.0 e multiplica 
pelo tamanho do vetor convertendo o valor para INT
Salva os elementos do vetor a no vetor b um por um
Algoritmos de ordenação – Bubble Sort
É um método de ordenação por troca que atua comparando sucessivamente pares de elementos e mudando-os de posição quando se apresentam fora da ordem desejada.
Complexidade Computacional:
Pior caso O (n²) 
Melhor caso O (n) 
Caso médio O (n²) 
Coloca os maiores al final
Percorre o vetor , caso tenha que trocar
algum valor ele percorre o vetor outra vez 
Se não tiver trocado nenhum valor ele termina de percorrer
Variável para saber quando parar de percorrer o vetor
Variável para contar a quantidade de comparações
Salva o tamanho do vetor
É um algoritmo bastante simples, por seleção, que é recomendado para conjuntos pequenos de dados. 
O algoritmo do Selection Sort consiste em três passos: 
• Navegue pelo vetor até encontrar o menor valor desse vetor; 
• Remova esse valor do vetor e insira na primeira posição do vetor de resposta; 
• Repita esse passo para cada item presente no vetor. 
Complexidade computacional: Para todos os casos será sempre O (n²) 
Algoritmos de ordenação – Selection Sort
Procura o menor e coloca o começo 
Salva o primeiro índice como o que possui o menor elemento
Caso exista algum valor menor do que o que esta no começo ele 
Troca o valor do mínimo e depois troca os elementos da posição
Algoritmo simples, por inserção, que percorre um vetor de elementos da esquerda para a direita. 
Complexidade computacional:
Pior caso O (n²) 
Melhor caso O (n) 
Caso médio O (n²) 
Algoritmos de ordenação – Insertion Sort
Vai de esquerda para a direita deixando a esquerda ordenada 
Acrescenta quando ocorre comparação mas não ocorre troca quando da false 
Ordena da direita para a esquerda a cada novo índice 
Acrescenta quando acontece troca
Utiliza uma árvore Heap como estrutura intermediária para efetuar a ordenação. 
Max-heap ➔ árvore binária quase completa em que cada pai é maior ou igual que qualquer de seus filhos. 
Min-heap ➔ árvore binária quase completa em que cada pai é menor ou igual que qualquer de seus filhos. 
Complexidade computacional: 
Para todos os casos será O (n log (n))
Algoritmos de ordenação – Heap Sort
Usa arvores para ordenar vetores
Cria a arvore
Ao criar a arvore o maior valor já fica ordenado 
A cada iteração a arvore diminui 
Chamada apenas uma vez , no inicio , para criar a arvore
O inicio é o ultimo pai do vetor
Cada vez que arruma o arvore , o maior valor fica na primeira posição
Troca o primeiro filho
Troca o segundo filho
Se o trocar não mudar quer dizer que o pai é maior que seus filhos 
Merge Sort é um dos algoritmos de ordenação que possuem a estratégia divisão e conquista.
Consiste dividir o problema em “partes” menores, e repetir o processo para cada uma dessas partes.
Complexidade computacional:
Para todos os casos sua complexidade será O (Log (n))
Algoritmos de ordenação – Merge Sort
Copia o elementos do vetor do inicio até o meio no vetoraux
Copia os elementos do vetor do meio até o fim no vetoraux ao contrario 
Compara os menores valores do lado esquerdo do vetor com os menores do lado direito
-Mais rápido que se conhece
-Estratégia Dividir-e-conquistar
-Utiliza um pivô 
-Melhor opção para ordenar vetores grandes 
-Instável 
Complexidade computacional:
Melhor caso O (n log n) 
Caso médio O (n log n) 
Pior caso O (n²) 
Algoritmos de ordenação – Quick Sort
Divide o vetor no meio e coloca os valores menores que o
 pivô a esquerda e os maiores a direita
Usa o primeiro elemento como pivô
As duas variáveis começam no fim toda vez que encontra um valor a esquerda 
que é maior do que o pivô , o valor é mandado para a direita
Percorre o vetor da direita para a esquerda , comparando os valores 
na posição esquerda
O pivô deve ser maior do que está a esquerda e menor do que esta a direita
No final do while a posição direita vai representar o meio do vetor
Retorna o meio
Algoritmos de ordenação – Radix Sort
Ordena pelas unidades, depois dezenas , centena , milhares ...
Encontra o maior 
Realiza o CountSort para as unidades , depois para as dezenas , centenas , milhares
-Utiliza um vetor auxiliar para contar a quantidade de elementos no vetor
-Faz a soma da frequência dos elementos
-Usa a soma das frequências para descobrir o índice dos elementos em um novo vetor
Complexidade computacional:
Para todos os casos sua complexidade será O (n)
Algoritmos de ordenação – Count Sort
Neste CountSort tem o normal e o utilizado no RadixSort dependendo do tipo 0= normal , 1 = radix
Procura maior valor do vetor
Cria um vetor com tamanho = ao maior valor do vetor
Mas 1 , com isso existe um índice para cada valor possível no vetor
Coloca 0 em todos os índices do vetorAux
Percorre o vetor e acrescenta 1 em cada índice do VetorAux caso encontre o Valor no vetor, com isso não temos os valores mas temos a quantidade que os valores se repetem ( em relação a sua casa decimal)
Percorre o vetor e acrescenta 1 em cada índice do vetorAux caso
Encontre o valor no vetor , com isso não temos os valores mas temos a quantidade
que os valores se repetem
Agora ele percorre o vetorAux acrescentando em 1 o valor
I +(i-1) dessa forma teremos a frequência dos elementos
Coloca os valores ordenados em relação a casa decimal
No vetor final
Coloca os valores ordenados no vetorfinal
Copia o vetorFinal no vetor
-Utiliza ‘baldes’ para ordenar
-Divide os elementos do vetor em baldes
-Utiliza o Insertion Sort para ordenar os baldes e depois concatena eles
-Parecido com o Count Sort, porém sem a frequência
Complexidade computacional:
Pior Caso O (n²) 
Melhor = Médio Caso O (n)
Algoritmos de ordenação – Bucket Sort
Usa baldes para ordenar os vetores
Procura maior valor do vetor
Cria bucket com tamanho igual ao maior valor
do vetor mas 1 , com isso existe um índice para cada valor
possível no vetor
Percorre o vetor e acrescenta 1 em cada índice do bucket caso encontre o valor no vetor , com isso não temos os valores mas temos a quantidade que os valores se repetem
Agora ele percorre o bucket , caso o bucket na posição i tenha um valor diferente de 0 quer dizer que o valor do índice dele existe no vetor , com isso ele acrescenta o índice quantas vezes ele estiver registrado no bucket
Analise de desempenho – Vetor 5 posições
Analise de desempenho – Vetor 50 posições
Analise de desempenho – Vetor 100 posições
Analise de desempenho – Vetor 1000 posições
Analise de desempenho – Vetor 10000 posições
Analise de desempenho – Vetor 10 posições