Questão nº 25
Questão de Tecnologia da Informação · FCC TRT19 2022 (nº 25)
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. (alternativa correta)
- 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.
Resposta comentada
Gabarito Alternativa A
Um método de ordenação estável é aquele que, ao ordenar um conjunto de dados, mantém a ordem relativa original de elementos que possuem o mesmo valor.
(A) Correta: Um método de ordenação é chamado de estável se não altera a posição relativa de elementos com mesmo valor depois da ordenação, exatamente como descrito no exemplo.
(B) Incorreta: O Selection Sort tem complexidade O(), não O(), e sua estratégia é encontrar o menor (ou maior) elemento e colocá-lo na posição correta, não apenas comparar e trocar para colocar os maiores no final.
(C) Incorreta: O Bubble Sort tem complexidade O(), não O(), embora sua estratégia de comparar e trocar adjacentes para mover elementos (menores para o início ou maiores para o final) esteja parcialmente correta.
(D) Incorreta: O Quicksort tem complexidade O() no caso médio e O() no pior caso, nunca O(); além disso, a sublista da esquerda deve conter elementos menores ou iguais ao pivô, e não maiores que os da direita.
(E) Incorreta: O Quicksort não é O() e necessita de memória adicional para a pilha de recursão (O() no caso médio, O() no pior caso); algoritmos como Heapsort ou Merge Sort são preferíveis para aplicações que não toleram variações no tempo de ordenação devido ao pior caso do Quicksort.
Fonte: FCC TRT19 2022 Técnico Judiciário - Área Apoio Especializado - Especialidade Tecnologia da Informação (Caderno Tipo 001). Reproduzida para fins de estudo.