LISTA_DE_EXERCICIO_DE_PESQUISA_E_ORDENACAO_-_PATRICIA_FERNANDES_DO_CARMO

Prévia do material em texto

Disciplina: Pesquisa e Ordenação 
Professor: José Couto Júnior 
Aluna: Patrícia Fernandes do Carmo 
 
 
 
 
 
Lista de Exercícios 1 
 
 
1. Observe o trechos de pseudocódigos a seguir: 
 
A 
 
 
 
 
 
 
 
 
B 
 
 
 
 
 
 
 
 
 
 
C 
 
 
 
 
 
 
 
 
 
 
 
Sobre os pseudocódigos na tabela anterior responda: 
 
a. Que método de ordenação está relacionado com trecho de código A ? 
Justifique sua resposta explicando o método de ordenação e sua relação com o código. 
 
Método Bolha - No pseudocódigo tem uma descrição "n - 1" é onde faz a comparação entre os 
elementos "N" do vetor com seu sucessor levando até o a posição "0" que satisfaz a condição de 
ordem crescente. 
 
 
b. O código B representa uma melhoria do primeiro algoritmo. Observe e indique as 
diferenças entre o código anterior, quais melhorias foram realizadas, o papel do FLAG os 
impactos positivos destas melhorias na ordenação 
 
O Metodo "FLAG" foi usado apenas para evitar iterações inúteis isso é interessante, pois 
economiza tempo e memoria facilitando todo o processo. 
 
c. Que método de ordenação está relacionado com trecho de código C? 
Justifique sua resposta explicando o método de ordenação e sua relação com o código. 
 
Método seleção, pois o algoritmo de ordenação por seleção possui dois laços de repetição, os quais 
são responsáveis por pegar o elemento atual e compará-lo com seus sucessores, ao final das 
comparações de cada iteração, o elemento atual trocará de lugar com o menor sucessor encontrado 
durante aquela iteração. Esse método realiza poucas operações de swap. Seu desempenho 
costuma ser superior ao do método bolha, mas inferior ao do método inserção. Nesse método a lista 
está dividida em parte esquerda, já ordenada, e parte direita em possível desordem, além disso, os 
elementos da parte esquerda são todos menores ou iguais aos da parte direita. 
Cada interação consiste em selecionar o menor elemento da parte direita (pivô) e trocá-lo com o 
primeiro elemento a parte direita. Se a lista possui n elementos, após n – 1 iterações ela estará 
ordenada. No código é evidente que o Algoritmo Seleção realiza (n 2 – n) / 2 e sua complexidade 
temporal pertence a O (n2). O Algoritmo Seleção necessita de apenas quatro variáveis escalares 
para fazer o seu trabalho, sendo assim a complexidade espacial desse método é O (1). 
 
2. Sobre as figuras a seguir responda: 
 
a) Que algoritmo foi utilizado para ordenar o vetor a seguir? Justifique sua resposta 
indicando o passo a passo deste algoritmo de ordenação 
 
 
 
 
 
 
 
 
 
 
 
 
 
O Selection Sort, pois esse método pega o elemento atual e percorre o conjunto procurando 
verificar se ele é o menor elemento do conjunto. Se o elemento escolhido não for o menor, ele 
trocará de lugar com o menor elemento. subsequente. Estando este elemento já ordenado, 
procura-se o segundo menor elemento, e assim por diante até obter todos os elementos 
ordenados. É o conteúdo de um vetor após cada iteração do laço mais externo do Algoritmo, 
onde a parte esquerda da lista aparece sombreada. Aqui o método Seleção é não estável. Na 
figura acima é possível observar que na lista original o elemento inicial é o 10, e ao percorrer o 
conjunto verificou-se que o menor elemento subsequente é o 2, assim, o elemento inicial 10 troca 
de lugar com o menor elemento. Em seguida, o elemento a ser comparado é o da posição 
seguinte a já ordenada, no caso é o elemento 4, e após ser comparado com os demais 
elementos subsequentes o menor elemento encontrado é o 3, acontece a troca de posição entre 
o elementos 3 e 4. Avançamos para o elemento seguinte da posição seguinte a já ordenada, o 
elemento 5, ao ser comparado com os subsequentes obtém o elemento 4 como menor, há a 
troca de posições desses elementos. Em seguida ao comparar o elemento atual, o elemento 10, 
com seu subsequente, o elemento 10, não há inferioridade do elemento subsequente em 
questão, o que faz com que não haja troca de posições e aí algoritmo é encerrado. 
 
b) Que algoritmo foi utilizado para ordenar o vetor a seguir? justifique sua resposta 
indicando o passo a passo deste algoritmo de ordenação 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Resposta: O algoritmo utilizado foi o Insertion Sort. Nesse método considera-se que a lista está 
dividida em parte esquerda já ordenada, e parte direita em possível desordem. É fácil perceber 
que se a lista possui n elementos, após n – 1 inserções ela estará ordenada. E para inserir o pivor 
percorre-se a parte esquerda, da direita para a esquerda, deslocando apenas os elementos 
maiores que um pivor uma posição para direita. Esse algoritmo requer apenas três variáveis 
escalares e sua complexidade espacial é O(1). Ele é estável. 
 
3. Pesquise sobre o algoritmo de ordenação ShellSort e responda: Quais valores para h 
foram sugeridos pelos pesquisadores Donald L. Shell Donald Knuth, e Robert Sedgewick. 
Explique a sequência de valores de h gerados e quais fórmulas para gerar h foram 
sugeridas por estes cientistas da computação. Feito isso explique como funciona este 
algoritmo de ordenação. 
 
- Foi proposto por Shell em 1959 uma extensão do algoritmo por inserção; O algoritmo 
de inserção é aplicado utilizando uma distância h entre os elementos. Desse modo, os 
elementos que estão muito distantes de sua posição real são aproximados mais 
rapidamente para a posição relativa à ordenação; Sequencias de h têm sido 
experimentadas. Shell sugeriu usar potências de 2 como valores de h, por exemplo: para 
ordenar uma lista de 100 elementos seriam utilizados os números 64,32,16,8,4,2 e 1 como 
valores de h. 
 
- Donald Knuth mostrou que h(s) = 3 * h(s-1) + 1 e h(1) = 1 é difícil de ser superado por 
outra série de saltos em mais do que 20% das ocasiões. Ele sugeriu calcular os valores 
de h usando a seguinte fórmula de recorrência: h = 3 * h + 1. Como o último valor de h 
tem que ser 1 usando essa fórmula, o valor anterior de h seria 4. Antes de 4, o valor de 
h seria 13 e assim por diante. Ex: Para ordenar uma lista de 100 elementos seriam 
utilizados os números 40,13,4 e 1 como valores de h. 
 
- Robert Sedgewick propôs a sequência h i = 4
 i + 3 . 2 i −1 + 1 para i ≥ 1 
h 0 = 1 
A sequência h = 1, 8, 23, 77, 281, 1073, 4193, 16577,..., que segundo Sedgewick, é mais 
rápida que a proposta por Knuth de 20 a 30% 
 
4. Considere as figuras a seguir: 
 
 
 02 
 
 
 
 
 
 
 
 
 
a) Que método está sendo utilizado na figura 01? 
 
Resposta: Mergesort 
 
b) O método da figura 01 é recursivo? Justifique sua resposta indicando trechos de códigos 
deste algoritmo em linguagem JAVA 
 
Sim. 
/** 
* Método chamado recursivamente que divide o vetor ao meio e depois chama 
mesclagem e ordenação os dos elementos. 
 * 
 * @ param inicio Posição inicial do conjunto. 
 * @ param fim Posição final do conjunto. 
 */ 
 public static void dividir(int inicio, int fim) { 
 // Se o inicio for menor que o fim, conclui-se que ainda pode dividir o conjunto. 
 if (inicio < fim) { 
 // Pega a posição do meio do conjunto. int meio = (inicio + fim) / 2; 
 // Divide a primeira metade. 
 dividir(inicio, meio); 
 // Divide a segunda metade. 
 dividir(meio + 1, fim); 
 // Junta as metades com os elementos ordenados. 
 mesclar(inicio, meio, fim); 
 } 
 } 
 
c) Explique passo a passo deste método de ordenação e indique como funciona a fase 
de INTERCALAÇÃO deste método 
 
O algoritmo Mergesort utiliza o princípio de dividir para conquistar, sendo assim, o conjunto inicial 
é dividido ao meio, esses dois subconjuntos são divididos da mesma forma e assim 
sucessivamente até termos diversos subconjuntos compostos por apenas 1 elemento. Logo 
após é feita a comparação dos elementos subconjuntos filhos de 1 elemento apenas que foram 
gerados do subconjunto pai de 2 elementos, colocando os elementos ordenados em um novo 
subconjunto filho, mas agora formado por 2 elementos ordenados.Em seguida, esse novo 
subconjunto filho com 2 elementos ordenados é comparado com o outro subconjunto filho 
ordenado, também de 2 elementos, que fazia parte do subconjunto pai com 4 elementos. Então 
é criado um novo subconjunto filho com 4 elementos ordenados, o qual terá seus elementos 
comparados com os de seu irmão, e gerarão um novo conjunto pai com os 8 elementos 
ordenados. E assim sucessivamente será feito até obter um conjunto pai totalmente ordenado, 
com os mesmos elementos do conjunto inicial desordenado. A classificação por intercalação 
consiste em dividir o vetor de chaves a ser classificado em dois ou mais, ordená-los 
separadamente e, depois intercalá-los dois a dois, formando cada par intercalado, 
novos segmentos, ordenados, os quais serão intercalados entre si, repetindo-se o 
processo até que resulte apenas um segmento ordenado que seria o próprio vetor 
ordenado. 
 
d) Que método está sendo utilizado na figura 02? 
 
Resposta: Quicksort. 
 
e) O método da figura 02 é recursivo? Justifique sua resposta indicando trechos de 
códigos deste algoritmo em linguagem JAVA 
 
Resposta: Sim. 
/** 
 * Divide o vetor ao meio recursivamente, tendo como base o pivô, e depois mescla e ordena 
os elementos. 
 * 
 * @param inicio Inicio do vetor a ser ordenado. 
 * @param pivo Pivô do vetor a ser ordenado. 
 * @param fim Fim do vetor a ser ordenado. 
 */ 
 public static void ordenacao_quick_sort(int[] vetor, int inicio, int fim) { 
 // Pivo do vetor. 
 int pivo; 
 // Se o inicio é menor que o fim, temos elementos para particionar. 
 if (inicio < fim) { 
 // O pivo é retornado depois de particionar o vetor. 
 pivo = particionar(vetor, inicio, fim); 
 // Ordena o vetor do inicio para o meio. 
 ordenacao_quick_sort(vetor, inicio, pivo); 
 // Ordena o vetor do meio para o fim 
 ordenacao_quick_sort(vetor, pivo + 1, fim); } 
 } 
 
f) Como é feita a escolha do Pivô no método da figura 02? existem outras 
possibilidades? Quais são? 
 
Foi feito através da escolha da mediana do conjunto. Sim, ou pela média aritmética ou 
pela escolha aleatória de um elemento. 
 
 
5. No caso do quicksort, considere que o pivô é o elemento central e apresente a 
ordenação do vetor A = {2, 5, 32, 21, 102, 1, 11, 24, 35, 44, 56}. Informe a quantidade de 
comparações e trocas efetuadas. 
 
Foram feitas 15 trocas e 19 comparações 
 
 
 
 
 
6. Dada a sequência de números: 3 4 9 2 5 8 2 1 7 4 6 2 9 8 5 1, ordene-a em ordem 
crescente segundo os seguintes algoritmos, apresentando a sequência obtida após 
cada passo do algoritmo: 
 
 a. MergeSort 
 
 
 
 
b. QuickSort