Questão 6 — Algoritmos de Ordenação — Complexidade (Algoritmos e Estruturas de Dados) — Serviço de Seleção do Pessoal da Marinha (SSPM) · Marinha do Brasil 2022

Algoritmos e Estruturas de Dados Algoritmos de Ordenação — Complexidade

Serviço de Seleção do Pessoal da Marinha (SSPM) 2022

Marinha do Brasil · Quadro Técnico do Corpo Auxiliar da Marinha (CP-T) — Informática · Caderno Amarela

Gabarito disponível

Assinale a opção em que é realizada, corretamente, a comparação entre diferentes pares de algoritmos de ordenação em termo de suas complexidades.

Selecione uma alternativa A) No pior caso, o tempo de execução do quick sort é menor que o do merge sort. B) A ocupação de espaço em memória do algoritmo quick sort é menor que a do heap sort. C) O tempo de execução no melhor caso do algoritmo bubble sort é menor que o do quick sort. D) O algoritmo merge sort possui menor complexidade em termos de utilização de memória que o algoritmo de ordenação por inserção. E) O algoritmo quick sort possui menor complexidade de utilização de memória que o de ordenação por inserção.

Resolução comentada

No melhor caso, o bubble sort (O(n)) é mais rápido que o quick sort (O(n log n)).

O bubble sort com verificação de troca tem melhor caso O(n), quando a lista já está ordenada. O melhor caso do quick sort é O(n log n). Assim, o tempo do bubble sort nesse caso é menor.

Análise das alternativas

A) Errada: o pior caso do quick sort é O(n²) e o do merge sort é O(n log n). B) Errada: o quick sort usa O(log n) de espaço e o heap sort usa O(1). D) Errada: o merge sort usa O(n) e a inserção usa O(1). E) Errada: o quick sort usa O(log n) e a inserção usa O(1).

Referência: Cormen et al., Algoritmos; Ziviani, Projeto de Algoritmos.

Resolução comentada do VaiConcursos.