Atividade Pesquisa e Ordenação de Dados

1 - Comente com suas palavras sobre divisão e conquista.

Divisão e conquista se dá pela técnica de dividir um grande

problema - que demandaria muito tempo de execução sendo

solucionado como um todo - em pequenas partes mais simples de

solucionar e juntá-las novamente após todas solucionadas. Pode não

parecer, mas reduz e muito a quantidade de tempo e esforço que

um algoritmo pode precisar para solucionar um problema.

2 - Faça uma análise crítica e uma comparação dos dois

algoritmos de divisão e conquista:

a. Merge Sort

O Merge sort é um algoritmo calcado no conceito de divisão e

conquista, ele ao ordenar uma lista, divide esta em listas

menores, ordena cada uma dessas sublistas e ao combiná-las

temos como resultado a lista completamente ordenada.

b. Heap Sort

Já o Heap sort usa o mesmo princípio que a ordenação por

seleção, encontrando o elemento mínimo, colocando ele no

“início” e repetimos esse processo com os restantes itens da

lista. Entretanto, visualmente, o Heap sort atua numa estrutura

de dados diferente da trabalhada no Merge sort, enquanto o

merge usa uma estrutura de lista e subdivisões dela, o Heap

sort usa uma estrutura de árvore binária com os valores dados

num array.

3 - Compare a eficiência de cada um deles no tocante a:

a. Quem tem o menor número de trocas e por que?

O merge sort, por que a cada vez que o heap sort é realizado

numa subárvore ele precisa ser analisar de novo para garantir

que aquela subárvore é uma árvore binary heap, caso

contrário, mais trocas serão feitas até que ela esteja correta.

b. Quem é mais eficiente quando os itens estão na ordem

reversa?

O merge sort, pois ele vai agir como se estivesse ordenando

uma lista embaralhada, entretanto, vai precisar fazer mais

trocas, já o heap sort vai precisar fazer mais trocas e após essas

trocas ele ainda vai precisar verificar se o nó raiz ainda é o

menor ou maior valor, dependendo do problema.

c. Quem é mais eficiente quando os itens estão quase

ordenados?

Quase é um conceito vago, mas partindo do