Atividade 3 PesquisaOrdenaçãoEtecnicasDeArmazenamento

Prévia do material em texto

PERGUNTA 1
Ordene os seguintes valores abaixo, utilizando os métodos de HeapSort e QuickSort. Comente o processo de ordenação do números abaixo.
a) HeapSort: 45,93,22,12,55,69,81
b) Quicksort: 45,93,22,12,55,69,81 
OBS: Caso o processo se torne repetitivo, basta informar que o mesmo será feito para os demais números.
Na avaliação dessa atividade o professor/tutor utilizará os seguintes critérios para correção:
O aluno deverá:
- apresenta de forma correta a fundamentação teórica, conforme os recursos didáticos da aula;
- faz a relação adequada entre a teoria e a prática, conforme solicitado;
- apresenta resposta está redigida de forma coesa e coerente, com boa organização de parágrafo;
- na escrita atende as normas da língua portuguesa.
Atenção! Sua resposta deve ser original, elaborado a partir de suas leituras e reflexões. A resposta não deve ter texto copiado de outras fontes sem a devida citação do autor e obra. A citação deve apenas complementar sua resposta.
a) O heapsort utiliza uma estrutura de dados chamada heap, para ordenar os elementos à 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, lembrando-se sempre de manter a propriedade de max-heap.
heap pode ser representada como uma árvore (uma árvore binária com propriedades especiais) ou como um vetor. Para uma ordenação decrescente, deve ser construída uma heap mínima (o menor elemento fica na raiz). Para uma ordenação crescente, deve ser construído uma heap máxima (o maior elemento fica na raiz).
Com a ordenação crescente deve ser construído um heap máximo (o maior elemento fica na raiz). A[i/2] >=A[i ] (ou seja, pai >= filho). Com a ordenação decrescente, deve ser construído um heap mínimo (o menor elemento fica na A [i/2] <=A [i ] (ou seja, pai <= filho)
H {45,93,22,12,55,69,81}
Compara 2i + 1 e 2i+2, pega o vetor de 7 elementos, e divide por 2, (7-1)/2 = 3 o primeiro elemento 3 elemento que é 12 onde é i;
Ai vai verificar 2i +1 e 2i+ 2, como a posição de 12 é 3 elemento chama elemento , no caso 81 de “maior filho” (MF), ai compara MF > i, verdadeiro, então troca de posição com o elemento
45, 93, 22 81, 55, 69,12
Então verifica se existe os elementos 2i+1 e 2i+2, se não existir então pronto e nessa passagem com essa subarvore.
Então i decrementa uma posição, i = 22 e verifica as posições 2i+1=4 e 2i+2=5, logo compara i com as 55 e 69, como 2i+2 é maior troca de lugar com 22<69, e verifica se existe posição de 2i+1 e 2i+2 se não existir não troca.
45, 93, 69, 81, 55, 22,12
Então i decrementa uma posição, i = 93, e verifica as posições 2i+1=3 e 2i+2=4, logo compara i com 69 e 81, como é maior não troca e o i decrementa menos 1. 
E repete os passos com 45 verificando 2i+1 e 2i+2 se maior ele troca, se não ele permanece no lugar e decrementa de 1 e faz a verificação com o próximo elemento até o vetor está ordenado.
b) O algoritmo quicksort é um método de ordenação muito rápido e eficiente, que adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. Os passos são: 
Escolha um elemento da lista, denominado pivô;
Particiona: rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição;
Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;
Q {45,93,22,12,55,69,81 }
Eleger um pivô que é primeiro elemento, 45, e define i como inicio e j no final, 49 e 81 respectivamente, então faz a comparação do i e j com o elemento pivô, se j<49 vai para o lugar onde está o pivô se for menor nada acontece e percorre o vetor para esquerda até i<=J;
 45 -> i = 93; j = 81; 81<45 – na acontece, 69 < 45 – na acontece, 55< 45 – nada acontece, 12 <45 – troca pivô e para o processo, e pergunta j>pivô verdadeira troca de posição com o pivô. Até percorrer o vetor e i<=j; logo na primeira ordenação temos:
12, 45, 22, 93, 55, 69,81
12 = pivô, i = 45 e j = 81, 81 < 12 – nada acontece, 69 < 12 – nada acontece, 55 < 12 - – nada acontece, 93 < 12 – nada acontece, 22< 12 – nada acontece, 45 < 12 – nada acontece, logo i = j então 12 está ordenado.
E assim procede até o ordenamento do vetor;