Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — CETAP 2023

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq843167
Banca
CETAP
Órgão
SANTA CASA-PA
Ano
2023
Nível
Superior
Cargo
Analista de Sistemas
Algoritmos de ordenação são técnicas fundamentais na área da computação e são utilizados para organizar e ordenar coleções de dados, como listas ou arrays, de acordo com critérios específicos. Esses algoritmos têm uma ampla gama de aplicações em sistemas computacionais e são essenciais para a eficiência e eficácia de processos, nas mais diversas áreas do mundo do trabalho. Considere o algoritmo de ordenação ilustrado no pseudocódigo abaixo:função sort(lista, esquerda, direita)se esquerda < direitapivo_index = particionar(lista, esquerda, direita)sort(lista, esquerda, pivo _index - 1)sort(lista, pivo_index + 1, direita)função particionar(lista, esquerda, direita)pivo = lista[direita] # escolhendo o pivo como últimoelementoi = esquerda - 1para j de esquerda até direita -1se lista[j] <= pivoi=i+ 1trocar(lista[i], lista[j])trocar(lista[i + 1 ], lista[direita]) # colocando o pivo em suaposição corretaretornar i + 1# Inicializando o algoritmo com os índices apropriadoslista= [valores a serem ordenados]sort(lista, 0, comprimento(lista)-1)Qual das alternativas abaixo corresponde ao algoritmo em questão?
  1. AHeap Sort.
  2. BBubble Sort.
  3. CMerge Sort.
  4. DCounting Sort.
  5. EQuick Sort.
Revelar gabarito e comentário

GabaritoE — Quick Sort.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Algoritmos de Ordenação: Quick Sort

Gabarito: letra E. O pseudocódigo descreve o algoritmo Quick Sort com particionamento de Lomuto (pivô = último elemento). A função sort chama particionar que rearranja os elementos em torno de um pivô e retorna seu índice; a seguir, o algoritmo ordena recursivamente as duas sublistas (esquerda e direita). Essa estrutura (divisão por pivô + recursão) é a marca registrada do Quick Sort, diferente dos outros algoritmos listados.

O Quick Sort é um algoritmo de ordenação baseado em divisão e conquista, amplamente utilizado por sua eficiência média O(n log n). O particionamento de Lomuto é um dos métodos mais didáticos, escolhendo o último elemento como pivô.

Alternativa A — ❌ Incorreta

Heap Sort utiliza uma estrutura de heap (árvore binária) para ordenar, não realiza particionamento em torno de um pivô e não tem recursão com sublistas esquerda/direita.

Alternativa B — ❌ Incorreta

Bubble Sort percorre a lista trocando elementos adjacentes até que esteja ordenada, sem recursão ou função de particionamento.

Alternativa C — ❌ Incorreta

Merge Sort divide a lista ao meio recursivamente e depois intercala as metades ordenadas. Não há pivô nem particionamento; a divisão é sempre pelo índice central.

Alternativa D — ❌ Incorreta

Counting Sort é um algoritmo de ordenação por contagem (não baseado em comparações), que conta ocorrências de valores dentro de um intervalo conhecido. Não utiliza recursão nem trocas.

Alternativa E — ✅ Correta ⟵ GABARITO

Quick Sort implementa exatamente o pseudocódigo dado: escolhe um pivô (último elemento), particiona a lista de modo que todos os elementos menores ou iguais fiquem à esquerda e os maiores à direita, e então chama recursivamente o próprio algoritmo para as sublistas. A função particionar retorna a posição final do pivô. É a descrição clássica do Quick Sort com particionamento de Lomuto.

Gabarito: letra E.

Link permanente: /questoes/qq843167