Questão nº 27
Questão de Tecnologia da Informação · FGV TJ-MS 2024 (nº 27)
FGV2024Técnico de Nível Superior - Analista de SistemasTecnologia da Informação
Gabarito: Bver comentário ↓
Bárbara implementa um algoritmo de ordenação estável cuja complexidade temporal média OT pertence a O(n.logn) e cuja complexidade espacial OE pertence a O(n), sendo n o tamanho do vetor a ser ordenado.
O algoritmo implementado é o:
- Aquick sort;
- Bmerge sort; (alternativa correta)
- Cbubble sort;
- Dinsertion sort;
- Eselection sort.
Resposta comentada
Gabarito Alternativa B
Algoritmos de ordenação organizam elementos em uma sequência específica. A estabilidade garante que a ordem relativa de elementos com valores iguais seja mantida, enquanto a complexidade temporal mede o tempo de execução e a complexidade espacial mede o uso de memória.
- (A) Incorreta: O quick sort geralmente não é um algoritmo de ordenação estável, embora sua complexidade temporal média seja O(n log n) e espacial média seja O(log n) (pode ser O(n) no pior caso).
- (B) Correta: O merge sort é um algoritmo estável, possui complexidade temporal média O(n log n) e complexidade espacial O(n) devido à necessidade de um array auxiliar para a fusão.
- (C) Incorreta: O bubble sort é estável e tem complexidade espacial O(1), mas sua complexidade temporal média é O(n²), o que é superior a O(n log n).
- (D) Incorreta: O insertion sort é estável e tem complexidade espacial O(1), mas sua complexidade temporal média é O(n²), o que é superior a O(n log n).
- (E) Incorreta: O selection sort não é um algoritmo estável e sua complexidade temporal média é O(n²), embora sua complexidade espacial seja O(1).
Fonte: FGV TJ-MS 2024 Técnico de Nível Superior - Analista de Sistemas (Caderno Tipo 1). Reproduzida para fins de estudo.