Qual das seguintes afirmativas sobre o algoritmo de ordenaçã...

Alternativa Correta: B - MergeSort é um algoritmo de ordenação estável, preservando a ordem relativa de elementos iguais.

O MergeSort é um dos algoritmos de ordenação mais estudados e utilizados. Ele pertence à categoria de algoritmos de ordenação baseados em comparação e utiliza a técnica de Divisão e Conquista para ordenar os elementos.

A seguir, vamos analisar cada uma das alternativas para entender por que a alternativa B é a correta e por que as outras estão incorretas:

Alternativa A: MergeSort tem uma complexidade de tempo média pior do que a do QuickSort.

Essa afirmativa está incorreta. Ambos MergeSort e QuickSort têm uma complexidade de tempo média de O(n log n). No entanto, o MergeSort tem uma complexidade de tempo garantida de O(n log n) no pior caso, enquanto o QuickSort pode degradar-se para O(n²) no pior caso, dependendo da escolha do pivô.

Alternativa B: MergeSort é um algoritmo de ordenação estável, preservando a ordem relativa de elementos iguais.

Esta é a alternativa correta. O MergeSort é, de fato, um algoritmo estável. Isso significa que ele mantém a ordem relativa dos elementos iguais, uma característica importante em muitos contextos onde a estabilidade da ordenação é necessária.

Alternativa C: MergeSort sempre divide o array em partes de tamanhos iguais, independentemente da estrutura dos dados.

Essa afirmativa está incorreta. O MergeSort divide o array ao meio sempre que possível, mas se o número de elementos for ímpar, uma das partes terá um elemento a mais. Portanto, ele não sempre divide em partes de tamanhos exatamente iguais.

Alternativa D: MergeSort é um algoritmo in-place, ou seja, não requer espaço adicional proporcional ao número de elementos a serem ordenados.

Essa afirmativa está incorreta. O MergeSort não é um algoritmo in-place. Ele requer espaço adicional proporcional ao número de elementos a serem ordenados para armazenar os arrays temporários usados durante o processo de mesclagem. Essa necessidade de espaço adicional é uma das desvantagens do MergeSort quando comparado a outros algoritmos como o QuickSort.

Gostou do comentário? Deixe sua avaliação aqui embaixo!

MACETE: O "BIM" é estável (Mantém ordem de elementos iguais)!!

BUBLE

INSERT

MERGE

A - Falso: Ambos os algoritmos Quick Sort e Merge Sort possuem a mesma complexidade assintótica para casos médios e melhores, porém diferem no pior caso, com Quick Sort tendo O(n²) operações e Merge ainda com O(n log n).

B - Verdadeiro: Merge Sort é um dos algoritmos estáveis (BIM), pois nunca ocorre a mudança de posição relativa de elementos iguais durante o particionamento e junção.

C - Falso: Dependendo da implementação, um vetor de 3 elementos pode ser dividido em 1 e 2 elementos, ou 2 e 1 elementos. Então, considerando o caso mencionado, nem sempre o vetor será divido exatamente em partes de tamanhos iguais.

D - Falso: Esse é o caso do Quick Sort, que realiza a ordenação no vetor de origem, sem necessidade de um vetor auxiliar. O Merge Sort utiliza um vetor auxiliar para a junção ordenada das partes particionadas.