Algoritmos e Estrutura de Dados · FCC · 2022 | Questão sqc-fc064949

Algoritmos e Estrutura de DadosAlgoritmos

Código: fc064949
Banca: FCC
Órgão: TRT - 19ª Região (AL)
Ano: 2022

Cargo: Técnico Judiciário - Área Apoio Especializado Especialidade: Tecnologia da Informação

Considere um vetor com n elementos. O método de ordenação

Aé chamado de estável (stable) se não altera a posição relativa de elementos com mesmo valor depois da ordenação. Por exemplo, o vetor v[ 77, 55, 22, 33, 44, 22] tem dois elementos iguais a 22; um método de ordenação estável mantém o 22 da posição 3 antes do 22 da posição 6.
Bpor Seleção (Selection Sort) é de ordem de complexidade cúbica ou O (n³) e sua estratégia é ir comparando e trocando os elementos de posição, colocando os maiores nas posições finais do vetor.
Cda Bolha (Bubble Sort) é de ordem de complexidade cúbica ou O (n³) e sua estratégia é ir comparando e trocando os elementos de posição, colocando os menores nas posições iniciais do vetor.
DQuicksort, que é sempre O (log n), utiliza um pivô para dividir o vetor em uma sublista da direita e uma da esquerda, de modo que todo elemento da sublista da esquerda seja maior que os da direita. Em seguida, ordenam-se, pelo mesmo processo, as duas sublistas de forma recursiva.
EQuicksort, devido ao loop interno complexo (que o torna duas vezes mais lento que o Heapsort) não necessita de memória adicional e é sempre O (log n) qualquer que seja a ordem inicial dos elementos. Este é o método a ser usado para aplicações que não podem tolerar variações no tempo esperado de ordenação.

Revelar gabarito e comentário

GabaritoA — é chamado de estável (stable) se não altera a posição relativa de elementos com mesmo valor depois da ordenação. Por exemplo, o vetor v[ 77, 55, 22, 33, 44, 22] tem dois elementos iguais a 22; um método de ordenação estável mantém o 22 da posição 3 antes do 22 da posição 6.

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”.

Métodos de ordenação – estabilidade e complexidade

Gabarito: letra A. A definição de ordenação estável está correta: um algoritmo é estável quando preserva a ordem relativa de elementos de mesmo valor após a ordenação. O exemplo dado ilustra perfeitamente esse conceito. As demais alternativas erram na complexidade ou na descrição do funcionamento dos algoritmos.

A banca testa o conhecimento sobre as características básicas dos principais métodos de ordenação: estabilidade, complexidade de tempo e estratégia de particionamento. Vamos analisar cada alternativa.

Alternativa A — ✅ Correta ⟵ GABARITO

Define corretamente um método estável (stable sort): aquele que não altera a posição relativa de elementos com valores iguais. O exemplo com o vetor [77, 55, 22, 33, 44, 22] e os dois elementos de valor 22 ilustra que, num algoritmo estável, o primeiro 22 (posição 3) permanece antes do segundo 22 (posição 6) após a ordenação. Essa é a definição padrão adotada em estruturas de dados.

Alternativa B — ❌ Incorreta

Afirma que o Selection Sort tem complexidade cúbica O(n³) e que sua estratégia é comparar e trocar colocando os maiores no final. Erro grave de complexidade: o Selection Sort possui complexidade O(n²) no melhor, médio e pior caso. Além disso, sua estratégia típica consiste em selecionar o menor elemento e colocá-lo no início (ou o maior no final, se for a versão decrescente), mas não é definido por trocas constantes – a cada passagem busca o mínimo e realiza uma única troca.

Alternativa C — ❌ Incorreta

Afirma que o Bubble Sort tem complexidade O(n³) e coloca os menores nas posições iniciais. Novamente erro de complexidade: o Bubble Sort é O(n²) (com otimizações pode chegar a O(n) se já ordenado). A descrição de “colocar os menores nas posições iniciais” corresponde à versão ascendente, mas a complexidade está incorreta.

Alternativa D — ❌ Incorreta

Descreve o Quicksort como tendo complexidade sempre O(log n), o que é falso. O Quicksort tem complexidade O(n log n) no caso médio e O(n²) no pior caso (ex.: quando o pivô sempre é o menor ou maior elemento). A complexidade O(log n) é típica de algoritmos de busca binária, não de ordenação. Além disso, inverte a condição: na partição, elementos da sublista da esquerda devem ser menores (e não maiores) que os da direita, considerando o pivô como referência.

Alternativa E — ❌ Incorreta

Também afirma que o Quicksort é sempre O(log n) e que não necessita de memória adicional. Na verdade, o Quicksort utiliza memória extra na pilha de recursão (O(log n) no caso médio, O(n) no pior caso). A complexidade de tempo não é fixa: é O(n log n) médio e O(n²) pior caso. Dizer que ele é “sempre O(log n)” é um erro conceitual grave. A comparação com o Heapsort também é imprecisa: ambos têm complexidade O(n log n) no caso médio, mas o Heapsort é O(n log n) garantido; não se pode afirmar que o Quicksort é “duas vezes mais lento” de forma generalizada.

Gabarito: letra A.

Link permanente: /questoes/fc064949