Referente a algoritmos de ordenação, qual a opção correta?

Em uma busca na internet acerca de um determinado produto, os resultados podem ser ordenados de forma crescente ou decrescente pelo preço e pela nota dada por consumidores sobre a utilização do produto procurado.

Com base em seu conhecimento sobre as características dos algoritmos de ordenação, analise as afirmativas a seguir.

I. O algoritmo de ordenação Inserção tem a complexidade de n×log(n) comparações.

II. Um algoritmo de ordenação é considerado estável, caso ele não altere a posição relativa dos itens que apresentam o mesmo valor.

III. No algoritmo Quicksort, a escolha do elemento pivô influencia o desempenho do algoritmo. Em geral, com o pivô na posição central, ele apresenta uma complexidade de n×log(n) comparações.

IV. O algoritmo de ordenação Bubblesort e o Inserção fazem, em média, o mesmo número de comparações.

Estão corretas as afirmativas

A) I e II, apenas.

B) I e III, apenas.

C) II e IV, apenas.

D) I, III e IV, apenas.

E) II, III e IV, apenas.

Algoritmos

•

PUC-MINAS

6

0

6

0

3

JoaoSilva Silva

04/12/2022

💡 3 Respostas

Gustavo Pereira

09.05.2023

A opção correta é a letra D) I, III e IV, apenas.

I. O algoritmo de ordenação Inserção tem a complexidade de n^2 comparações, não n×log(n). Portanto, essa afirmativa está incorreta.

II. Um algoritmo de ordenação é considerado estável quando ele não altera a ordem de elementos com chaves iguais. Ou seja, se dois elementos tiverem a mesma chave, o algoritmo de ordenação estável preserva a ordem original desses elementos. Essa afirmativa está correta.

III. A escolha do elemento pivô no algoritmo Quicksort é fundamental para a eficiência do algoritmo. Se o pivô estiver sempre no início ou no final da lista, pode ocorrer o pior caso do algoritmo, com complexidade de n^2 comparações. Quando o pivô está no meio, a complexidade é n×log(n) comparações, em geral. Essa afirmativa está correta.

IV. O algoritmo Bubblesort tem complexidade de n^2 comparações, enquanto o algoritmo Inserção tem complexidade de n^2 comparações no pior caso, mas é mais eficiente que Bubblesort na maioria dos casos. Portanto, essa afirmativa está incorreta.

Dessa forma, as afirmativas corretas são I, III e IV.

1

0