Prévia do material em texto
1 Prof. Galdir Reges Tópicos Visão geral Ordenação por seleção Ordenação por inserção Ordenação por intercalação (MergeSort) Atividades Introdução 2 Pesquisa diagnóstica Introdução 3 Brainstorming: como ordenar rapidamente uma prateleira de livros pela ordem alfabética do titulo? Algoritmos de Ordenação Ordenar/classificar dados (isto é, colocar os dados em alguma ordem particular como crescente ou decrescente) é uma das aplicações mais importantes da computação. ▪ Um banco classifica todos os cheques pelo número de conta, de modo que possa preparar extratos bancários individuais no final de cada mês. ▪ As companhias telefônicas classificam suas listas de assinantes por sobrenome e, depois, pelo primeiro nome para facilitar a localização de números de telefone. ▪ Praticamente todas as empresas devem classificar alguns dados e, muitas vezes, volumes GIGANTESCOS deles. Classificar dados é um problema intrigante, que faz uso intensivo do computador e que atrai esforços intensos de pesquisa. Introdução 4 Algoritmos de Ordenação (2) É importante entender que o resultado final — o array classificado — será o mesmo, independentemente do algoritmo que você utiliza para classificar o array. Vamos ver três algoritmos de classificação comuns. ▪ Os dois primeiros — classificação por seleção e classificação por inserção — são fáceis de programar, mas ineficientes. O último algoritmo — a classificação por intercalação (merge) — é muito mais rápido que os outros dois mas é mais difícil de programar. Focamos a classificação de arrays de dados de tipo primitivo, ou seja, ints. Também é possível classificar arrays de objetos de classe. Introdução 5 Custo de acesso nos algoritmos Ordenação Interna (Ordenação de Vetores) ▪ Todos os elementos cabem na memória RAM e o custo de acesso é desprezado. Ordenação Externa (Ordenação de Arquivos) ▪ Somente parte dos elementos cabem na memória RAM e o custo de acesso (disco) torna-se determinante. Introdução 6 Ordenação por seleção Fácil de implementar mas ineficiente. Funcionamento: ▪ Toma o primeiro elemento como referência ▪ Procura pela menor elemento entre os n-1 elementos restantes ▪ Troca a posição do menor elemento com o elemento de referência ▪ Resultado parcial : o primeiro elemento é o menor elemento ▪ Toma o segundo elemento como referência ▪ Procura pela menor elemento entre os n-2 elementos restantes ▪ Troca a posição do menor elemento com o elemento de referência ▪ Resultado parcial: o segundo elemento é o segundo menor elemento ▪ Repete o processo anterior até que o elemento n-1 seja usado como referência ▪ Resultado final: conjunto ordenado Introdução 7 34 8 64 51 32 21 Ordenação por Seleção - Exemplo ref min min 8 34 64 51 32 21 ref min min min 8 21 64 51 32 34 ref min min min 8 21 32 51 64 34 ref min min 8 21 32 34 64 51 ref min min 8 21 32 34 51 64 Ordenação por seleção – Exemplo (3) https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.ht ml Introdução 9 https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html Ordenação por seleção (2) Como um exemplo, considere o array ▪ 34, 56, 4, 10, 77, 51, 93, 30, 5, 52 O algoritmo primeiro determina que o menor elemento desse array está contido no índice 2. O programa troca 4 por 34, resultando em ▪ 4, 56, 34, 10, 77, 51, 93, 30, 5, 52 O programa então determina o menor valor entre os elementos restantes (todos os elementos, exceto 4). O programa troca 5 por 56, resultando em ▪ 4, 5, 34, 10, 77, 51, 93, 30, 56, 52 Na terceira iteração, o programa determina o próximo menor valor (10) e o troca por 34. ▪ 4 5 10 34 77 51 93 30 56 52 O processo continua até que o array seja completamente classificado. ▪ 4 5 10 30 34 51 52 56 77 93 Introdução 10 Implementação da ordenação por seleção Demonstração do desenvolvimento em IDE Imagem do código será apresentada online Introdução 11 Ordenação por Seleção - Análise Ordena com custo (n^2 – n) / 2 no melhor, pior e médio casos Qual o Big O? ▪ O(n^2) O fato do arquivo já estar ordenado não ajuda em nada no tempo de execução, pois o tempo de execução continua a ser quadrático Introdução 12 Ordenação por Inserção Algoritmo simples que se assemelha ao processo de ordenação de uma mão de baralho Introdução 13 Ordenação por Inserção (2) Funcionamento: ▪ O algoritmo de inserção começa na posição 1 do vetor (posição de referência) e consiste de n-1 passos ▪ Para cada passo p, o algoritmo procura a posição adequada do elemento de referência entre p elementos anteriores do vetor ▪ Caso o elemento anterior seja “maior” do que o elemento de referência, desloca-se o elemento uma posição no vetor, abrindo espaço paro o elemento de referência ▪ Após cada passo, o algoritmo garante que os p elementos anteriores do vetor estão ordenados ▪ A posição de referência é atualizada para o próximo elemento no vetor Introdução 14 34 8 64 51 32 210 8 34 64 51 32 210 8 34 64 51 32 210 8 34 64 64 32 210 Ordenação por Inserção - Exemplo ref=8 ref=64 ref=51 ref=51 34 34 64 51 32 210 ref=8 8 34 51 64 32 210 8 32 34 51 64 210 8 34 51 64 32 210 8 34 51 64 64 210 8 34 51 51 64 210 ref=32 ref=32 ref=32 8 34 34 51 64 210 ref=32 ref=210 8 32 34 51 64 210 Ordenação por Inserção – Exemplo (2) Ordenação por Inserção – Exemplo (3) https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.ht ml Introdução 17 https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html Análise da Ordenação por Inserção Chaves inicialmente ordenadas ▪ Ordena com custo (n – 1) no melhor caso ▪ Qual o big O? • O(n) Chaves inicialmente ordenadas na ordem reversa ▪ Ordena com custo (n^2 - n) / 2 = no pior caso ▪ Qual o Big O? • O(n^2) Chaves distribuídas aleatoriamente ▪ Ordena com custo (n2 - n) / 4 = O(n^2) no caso médio Introdução 18 Implementação da ordenação por inserção Baseado no código da ordenação da seleção, e na descrição do da ordenação por inserção, desenvolva o código da ordenação por inserção. ▪ Lembrando o funcionando: • O algoritmo de inserção começa na posição 1 do vetor (posição de referência) e consiste de n-1 passos • Para cada passo p, o algoritmo procura a posição adequada do elemento de referência entre p elementos anteriores do vetor • Caso o elemento anterior seja “maior” do que o elemento de referência, desloca-se o elemento uma posição no vetor, abrindo espaço paro o elemento de referência • Após cada passo, o algoritmo garante que os p elementos anteriores do vetor estão ordenados • A posição de referência é atualizada para o próximo elemento no vetor Introdução 19 Atividade – Algoritmo de ordenação Implemente e descubra qual o algoritmo de ordenação comparando seu comportamento com os apresentados em: https://www.cs.usfca.ed u/~galles/visualization/C omparisonSort.html Introdução 20 declare X[5], j ,i, aux numérico //carregando os números no vetor para i=0 até 4 faça início escreva “Digite o “, i +1, “o número: “ leia X[i] fim //ordenando de forma crescente para j=1 até 4 faça inicio //laço que percorre da ultima posição a posição j do vetor para i=4 até j faça passo -1 inicio se(X[i] < X[i-1]) então inicio aux=X[i] X[i]=X[i-1] X[i-1]=aux fim fim fim //mostrando o vetor ordenado para i=0 ate 4 faça inicio escreva i+1,”o número: “, X[i] fim fim+algoritmo https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html Ordenação por Intercalação - MergeSort MergeSort é um excelente exemplo de um algoritmo recursivo que utiliza o mecanismo de dividir para conquistar para resolver o problema de ordenação. Introdução 21 Ordenação por Intercalação – MergeSort (2) Funcionamento: ▪ A operação fundamental do algoritmo MergeSort é fundir dois vetores já ordenados, tendo como resultado um vetor também ordenado. ▪ Como osvetores de entrada já estão ordenados, a obtenção do vetor resultante pode ser feita com somente uma passagem pelos dados de entrada. ▪ O algoritmo MergeSort funciona através da divisão recursiva do vetor original em duas partes até que a ordenação das partes se torne trivial (somente 1 elemento). ▪ Recursivamente, o algoritmo remonta as partes ordenadas até obter o vetor final ordenado. Introdução 22 MergeSort - Exemplo 14 5 2 7 3 6 13 8 14 5 2 7 3 6 13 8 14 5 2 7 3 6 13 8 14 5 2 7 3 6 13 8 5 14 2 7 3 6 8 13 2 5 7 14 3 6 8 13 2 3 5 6 7 8 13 14 2 3 52 5 7 14 3 6 8 13 2 3 2 5 7 14 3 6 8 13 22 5 7 14 3 6 8 13 2 5 7 14 3 6 8 13Operação mais complicada : Fusão de dois vetores ordenados, resultando um vetor também ordenado MergeSort – Fundindo dois Vetores Ordenados 2 3 5 6 72 5 7 14 3 6 8 13 2 3 5 62 5 7 14 3 6 8 13 2 3 5 6 7 8 13 14 2 5 7 14 3 6 8 13 2 3 5 6 7 8 13 2 5 7 14 3 6 8 13 2 3 5 6 7 82 5 7 14 3 6 8 13 MergeSort – Exemplo (3) https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.ht ml Introdução 25 https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html Análise do MergeSort Ordena com custo O(n log n) O problema com o MergeSort é que a memória requerida dobra por causa do vetor temporário. Existe também o problema do trabalho adicional de copiar os elementos para o vetor temporário e de volta para o vetor original. Esta característica faz do algoritmo de MergeSort uma péssima escolha para algoritmos de ordenação interna, mas a estratégia de fusão de vetores ordenados é emblemática nos algoritmos de ordenação externa. Introdução 26 Implementação da ordenação intercalação (MergeSort) Professor apresenta o código funcionando. Copiar, compilar e testar o código disponível no site do curso. Introdução 27 Codigo parte 1 Introdução 28 Codigo parte2 Introdução 29 Parte 4 Introdução 30 Part 5 Introdução 31 Experimentos de análise Testar o tempo de execução de pior caso dos algoritmos de ordenação por seleção, inserção e intercalação com arrays com 100, 1.000, 10.000 e 100.000 elementos. Registar os tempos em planilha e gerar gráfico comparativo. Introdução 32 Tópicos Visão geral Ordenação por seleção Ordenação por inserção Ordenação por intercalação (MergeSort) Atividades Introdução 33 Referências DEITEL, P. Java: Como Programar. Pearson, 2016. Ascencio, Ana. Araújo, Graziela. Estruturas de dados : algoritmos, análise da complexidade e implementações em JAVA e C/C++. São Paulo: Pearson Prendice Hall, 2010. DOBRUSHKIN, Vladimir A. Métodos para Análise de Algoritmos. LTC, 03/2012. ZIVIANI, Nivio. Projeto de Algoritmos: com implementações em JAVA e C++. Cengage Learning Editores, 03/2012. Introdução 34
