Questão 16 — Ordenação — Divisão e Conquista (Quicksort) (Algoritmos e Estruturas de Dados) — Serviço de Seleção do Pessoal da Marinha (SSPM) · Marinha do Brasil 2025

Algoritmos e Estruturas de Dados Ordenação — Divisão e Conquista (Quicksort)

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

Marinha do Brasil · Oficial dos Quadros Complementares (CP-QC-CA-FN) — Sistemas de Armas · Caderno Amarela

Gabarito disponível

De acordo com Cormen (2012), o quicksort, como a ordenação por intercalação, aplica o paradigma de divisão e conquista. Assim, assinale a opção que apresenta o processo de três etapas do método de divisão e conquista para ordenar um subarranjo típico A[p .. r].

Selecione uma alternativa A) Divisão, ordenação e intercalação. B) Correlação, pequenas amostras e variância. C) Permutação, particionamento e amplitude total. D) Conquista, variância e permutação. E) Divisão, conquista e combinação.

Resolução comentada

Divisão e conquista tem três etapas: dividir, conquistar e combinar.

No quicksort, divide-se A[p..r] em dois subarranjos por particionamento. Depois os subarranjos são conquistados (ordenados recursivamente) e, por fim, combinados. Como a ordenação é feita no próprio arranjo, a combinação não exige trabalho.

Análise das alternativas

A mistura termos da ordenação por intercalação. B, C e D trazem termos estatísticos ou alheios ao paradigma, como variância, amplitude e correlação.

Referência: CORMEN (2012), cap. 7 (Quicksort).

Resolução comentada do VaiConcursos.