Question

A abordagem do algoritmo MergeSort é bem mais complexa do que as implementadas nos algoritmos BubbleSort e SelectionSort, porém o seu esforço computacional é reduzido. Para cada divisão, porém, faz-se necessária a criação de um novo vetor na memória e, no caso de ordenação de arquivos muito grandes, a utilização de memória pode ser excessiva.



OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.



Assinale a alternativa correta correspondente à forma como é feita a ordenação pelo algoritmo MergeSort.

Alternativas
Alternativa 1:
Em dois laços de repetição, o elemento atual é removido, sua posição ideal é procurada no vetor e, uma vez encontrada, o elemento é reinserido.

Alternativa 2:
Em dois laços de repetição, os elementos são comparados e trocados conforme o caso, fazendo os valores maiores "flutuarem" para o final do arranjo.

Alternativa 3:
O vetor é dividido em várias partes iguais menores, em que é feita a ordenação em cada uma delas. Depois o vetor é reunido já com valores ordenados.

Alternativa 4:
O vetor é percorrido em um laço de repetição e os elementos são adicionados em um segundo vetor, fazendo a comparação para verificar a ordenação.

Alternativa 5:
O vetor é dividido em duas partes, essas partes são re-divididas e assim por diante até que cada parte tenha um elemento. Depois é feita a junção, ordenando essas partes.

Answer 1

Sobre a ordenação do algoritmo MergeSort podemos observar que Alternativa 5:  O vetor é dividido em duas partes, essas partes são re-divididas e assim por diante até que cada parte tenha um elemento. Depois é feita a junção, ordenando essas partes.

A idéia básica do Merge Sort é criar uma sequência ordenada a partir de duas outras também ordenadas.

Para isso, o algoritmo Merge Sort divide a sequência original em pares de dados, agrupa estes pares na ordem desejada; depois as agrupa as sequências de pares já ordenados, formando uma nova sequência ordenada de quatro elementos, e assim por diante, até ter toda a sequência ordenada.

Espero ter ajudado.