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.
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.
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).
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.
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).
A complexidade de caso médio representa o tempo de execução esperado de um algoritmo, considerando a distribuição típica das entradas possíveis para um conjunto de 𝑛 elementos a serem ordenados.
Considerando a análise assintótica, o algoritmo de ordenação que apresenta complexidade de tempo de execução de caso médio O(log (n)n), sendo O(.) a notação em Big-O, é o
A
bucket sort com insertion sort (assumindo distribuição uniforme dos elementos).
Os métodos bottom‑up iniciam a discretização com uma lista vazia de pontos de corte e, durante a discretização, novos pontos são inseridos dividindo os valores em intervalos menores.
Um programador utilizou o código a seguir, escrito em C, para ordenar um vetor de tamanho médio.
void ordenar(int *vetor, int tamanho) {
int x , y , valor;
int intervalo= 1;
while(intervalo <tamanho) {
intervalo= 3*intervalo+1;
}
while (intervalo> 1) {
intervalo/= 3;
for(x= intervalo; x < tamanho; x++) {
valor= vetor[x];
y = x- intervalo;
while (y >= 0 && valor< vetor[y]) {
vetor [ y +intervalo]= vetor[y];
y-= intervalo;
}
vetor [y +intervalo]= valor;
}
}
}
O algoritmo em que o código se baseia utiliza um método de quebra sucessiva da sequência a ser ordenada e implementação da ordenação por inserção na nova sequência obtida , sendo denominado:
