Questão FC374698
Qual das seguintes afirmativas sobre o algoritmo de ordenação MergeSort é verdadeira?
Algoritmos e Lógica de Programação
Instituto Consulplan · 2024
Qual das seguintes afirmativas sobre o algoritmo de ordenação MergeSort é verdadeira?
- MergeSort tem uma complexidade de tempo média pior do que a do QuickSort.
- MergeSort é um algoritmo de ordenação estável, preservando a ordem relativa de elementos iguais.
- MergeSort sempre divide o array em partes de tamanhos iguais, independentemente da estrutura dos dados.
- MergeSort é um algoritmo in-place, ou seja, não requer espaço adicional proporcional ao número de elementos a serem ordenados.
Mostrar resposta e comentário
Gabarito
B
Comentário do professor
MergeSort é realmente um algoritmo estável: isto significa que, quando há dois ou mais elementos com a mesma chave, sua ordem relativa no resultado final permanece a mesma que tinham na entrada.
O motivo está na etapa de merge. Ao combinar duas sublistas ordenadas, a rotina de mesclagem, normalmente, escolhe primeiro o elemento da sublista esquerda quando as chaves são iguais. Dessa forma, elementos iguais vindos da esquerda mantêm-se antes dos iguais vindos da direita, preservando a ordem original.
Vale notar que a estabilidade depende de como o procedimento de merge é implementado; a implementação padrão que usa um buffer auxiliar e adota a escolha pela esquerda em empates garante a propriedade estável.
Conteúdo do catálogo FC Concursos · Atualizado em