Ao desenvolver algoritmos de ordenação para sistemas
que processam grandes volumes de dados
heterogêneos, a estabilidade é um critério técnico
fundamental para preservar a ordem relativa de
elementos com chaves idênticas. No contexto do
algoritmo Timsort (Algoritmo de Ordenação Híbrido), que
é o padrão em diversas linguagens modernas, a
eficiência é alcançada através da identificação de
sequências de dados já ordenadas. Considerando o
funcionamento interno deste algoritmo para a otimização
de recursos de memória e tempo, assinale a alternativa
correta.

Question

Ao desenvolver algoritmos de ordenação para sistemas
que processam grandes volumes de dados
heterogêneos, a estabilidade é um critério técnico
fundamental para preservar a ordem relativa de
elementos com chaves idênticas. No contexto do
algoritmo Timsort (Algoritmo de Ordenação Híbrido), que
é o padrão em diversas linguagens modernas, a
eficiência é alcançada através da identificação de
sequências de dados já ordenadas. Considerando o
funcionamento interno deste algoritmo para a otimização
de recursos de memória e tempo, assinale a alternativa
correta. Alternativa A: O algoritmo em questão é classificado como instável,
pois prioriza a velocidade de execução em sistemas
de Tempo Real (Real-Time Systems) sobre a
preservação da ordem original de registros que
possuem valores de chaves duplicadas. Ou Alternativa B: A eficiência do Timsort (Algoritmo de Ordenação
Híbrido) deriva da substituição integral da
recursividade por uma estrutura de Pilha (Stack)
estática, o que elimina a necessidade de memória
auxiliar durante a fase de Merge (Intercalação). Ou Alternativa C: A identificação de "runs" (sequências ordenadas) no
Timsort (Algoritmo de Ordenação Híbrido) é aplicada
exclusivamente em vetores que já ultrapassaram o
limite de memória da Cache L1 (Cache de Nível Um)
do processador central. Ou Alternativa D: O Timsort (Algoritmo de Ordenação Híbrido) utiliza a
técnica de identificação de "runs" (sequências
ordenadas) e aplica uma estratégia de intercalação
adaptativa que garante complexidade de tempo de
pior caso igual a O(nlogn).

Qconcursos · Accepted Answer

Alternativa [D] O Timsort (Algoritmo de Ordenação Híbrido) utiliza a
técnica de identificação de "runs" (sequências
ordenadas) e aplica uma estratégia de intercalação
adaptativa que garante complexidade de tempo de
pior caso igual a O(nlogn). Gabarito: DFundamento decisivo: O decisivo era a definição técnica do Timsort apresentada na base: um algoritmo estável que identifica runs naturais/ordenadas e as intercala de forma adaptativa, com pior caso O(nlogn). Isso torna correta a alternativa D.Tema central: Características do TimsortAnálise das alternativasAErradaEstá errada por erro de classificação: afirma que o Timsort é instável, mas a base afirma expressamente que ele é estável. Portanto, contraria uma característica fundamental do algoritmo.BErradaEstá errada porque confunde a existência de uma pilha de runs com eliminação de memória auxiliar no merge. Segundo a base, a fase de intercalação do Timsort não elimina memória auxiliar; logo, a afirmação sobre dispensar memória auxiliar não se sustenta.CErradaEstá errada porque atribui à detecção de runs uma condição operacional que não define o algoritmo: ultrapassar a cache L1. Pela base, a identificação de runs é uma estratégia de adaptatividade aos dados de entrada, não algo aplicado exclusivamente por causa desse limite de hardware.DCertaA alternativa D está correta porque descreve os elementos essenciais do Timsort segundo sua definição técnica consagrada: identificação de runs naturais/ordenadas e intercalação adaptativa. Além disso, a alternativa preserva a garantia assintótica indicada na base, que é pior caso O(nlogn). Esse é o conjunto de características que sustenta tecnicamente o algoritmo cobrado na questão.Pegadinha da questãoA questão explorou confusões reais entre adaptatividade e instabilidade, entre uso de pilha de runs e ausência de memória auxiliar no merge, e entre característica algorítmica e jargão de hardware como cache L1.Dica para questões semelhantesSe a alternativa trouxer runs ordenadas, estabilidade e intercalação adaptativa com pior caso O(nlogn), ela está alinhada ao núcleo do Timsort.Não conclua que um algoritmo é in-place ou que dispensa memória auxiliar só porque usa pilha ou evita certa forma de recursão.Descarte como suspeita qualquer descrição que transforme detalhe de hardware, como cache L1, em critério definidor do funcionamento do algoritmo.

🚀 Mais performance?

🚀 Mais performance?

Ao desenvolver algoritmos de ordenação para sistemas que pr...

Gabarito comentado

Gabarito: D

Clique para visualizar este gabarito

Questões de assuntos semelhantes

Provas relacionadas