comparando metodos de ordenação

Prévia do material em texto

FACULDADES INTEGRADAS DE CARATINGA 
CURSO DE CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: Ordenação e pesquisa 
PROFESSOR: Maicon Ribeiro NOME: Leone Duarte de oliveira 
TURMA: 3º Período SEMESTRE / ANO: 1º / 2018 
DATA DE ENTREGA: 03/04/2018 
Revisão 01 
01 – Caracterize com suas palavras os seguintes métodos de ordenação. 
a) Selection Sort 
O selection sort e um método de ordenação onde se compara o valor de uma posição com 
suas posições a seguir e troca caso seja necessário dessa forma sempre se envia o menor 
para o começo, ao mesmo tempo em que o tamanho do vetor vai sendo diminuído, ele e 
executado até que o vetor esteja completamente organizado. 
b) Insertion Sort 
O insertion e um método de ordenação onde se verifica do começo do vetor para o final, 
sempre que encontrar um número menor ele e trocado e também e verificado com todos 
os seus antecessores, dessa fora o vetor vai sendo organizado em tempo de inserção. 
c) Bubble Sort 
O bubble sort verifica de dois a dois e sempre envia o maior para o final, ele gira por todo 
o vetor procurando o maior valor naquele momento, e vai organizando os mesmos no 
final ao mesmo tempo que encurta o vetor. 
d) Merge Sort 
O merge sort funciona de forma recursiva dividindo o vetor em, vetores de uma posição 
e depois remonta o vetor, organizando recursivamente até sobrar somente dois vetores, 
daí se compara e organiza para ficar completo. 
e) Heap Sort 
O heap sort consiste em usar o método heap máximo para dividir o vetor, em uma arvore 
de forma sempre mandar o maior valor para a primeira posição, daí basta retirar esse 
valor e rodar a função quantas vezes forem necessárias. 
02 – Quais métodos se comportam de modo melhor e pior nas seguintes situações: 
a) Vetor aleatório de tamanho pequeno 
Melhor: Selection sort. Pior: merge sort. 
b) Vetor aleatório de tamanho grande 
Melhor: merge sort. Pior: insertion sort. 
 
c) Vetor crescente de tamanho pequeno 
Melhor: bubble sort. Pior: heap sort 
 
d) Vetor crescente de tamanho grande 
Melhor: bubble sort. Pior: heap sort. 
 
e) Vetor decrescente de tamanho pequeno 
Melhor: heap sort. Pior: Insertion sort 
 
f) Vetor decrescente de tamanho grande 
Melhor: heap sort. Pior: bubble sort 
 
03 – Explique como é possível a partir de uma determinada posição x calcular e encontrar as 
posições de seu pai e seu irmão em uma árvore binária feita com um vetor. Crie um algoritmo 
capaz de encontrá-los. 
Se x for par: 
Pai do filho direito = (x / 2) – 1. 
Filho da direita = (x * 2) + 2. 
 Se x for ímpar: 
 Filho da esquerda = (x * 2) + 1. 
Pai do filho esquerdo = (x - 1) / 2. 
 
 
 
04 – Mostre um Heap-Máximo do seguinte vetor: 
 
23 3 15 78 1 103 5 65 29 47 
 103 
 78 65 
 47 29 23 15 
 5 3 1 
 
 
 
 
 
 
05– Mostre o passo a passo da ordenação pelo MergeSort do seguinte vetor: 
 
23 3 15 78 1 103 5 65 29 47 
 
23- 3- 15- 78- 1 | 103- 5- 65- 29- 47 
 
23-3-15 | 78-1 103-5-65 | 29-47 
 
23-3 | 15 | 78 | 1 103-5 | 65 | 29 | 47 
 
23 | 3 | 15| 78 |1 103 | 5 | 65 | 29 | 47 
 
 
 
 
 
 
 
 
 
06 – Mostre o passo a passo da ordenação pelo BubbleSort do seguinte vetor: 
 
23 3 15 78 1 103 5 65 29 47 
3 15 23 1 78 5 65 29 47 103 
3 15 1 23 5 65 29 47 78 103 
3 1 15 5 23 29 47 65 78 103 
1 3 5 15 23 29 47 65 78 103