Questões de Concurso sobre Mergesort (mescla)

Bárbara implementa um algoritmo de ordenação estável cuja complexidade temporal média O_T pertence a O(n.logn) e cuja complexidade espacial O_E pertence a O(n), sendo n o tamanho do vetor a ser ordenado.

O algoritmo implementado é o:

Julgue o item seguinte a respeito dos conceitos de algoritmo de ordenação.

O algoritmo merge sort ordena os elementos de um vetor percorrendo este diversas vezes e, a cada passagem, deslocando até o topo o maior elemento da sequência.

Analise as assertivas abaixo sobre notação big-O e complexidade de algoritmos, observando as afirmações sobre algoritmos de ordenamento:

I. O algoritmo quicksort tem uma complexidade no caso médio de Θ(nlog(n)).

II. O algoritmo mergesort tem uma complexidade no pior caso de O(n log(n)).

III. O algoritmo bubble sort tem uma complexidade no melhor caso de Ω(n).

IV. O algoritmo selection sort tem uma complexidade no melhor caso de Ω(n).

Quais estão corretas?

Sobre o Método de Ordenação Merge Sort, é CORRETO afirmar que:

O método de ordenação conhecido por merge sort é usualmente implementado de maneira recursiva e realiza o ordenamento basicamente separando o vetor de dados em análise em duas partes, até que haja a comparação de apenas dois elementos para se verificar se há a necessidade de troca da posição. Depois, também de maneira recursiva, esses elementos vão sendo novamente reagrupados até que o vetor seja retornado na ordem ascendente ou descendente, conforme o interesse, como esquematizado na figura a seguir.

Fonte: IFSP, 2022.

Considerando o trecho de código a seguir e o vetor B=[10, 9, 8, 7, 6, 5, 4, 3, 2, 1], é correto afirmar que, no print(A) da linha 7 com o ordenamento ascendente do vetor B, a resposta da sua saída será:

Uma fábrica de software foi contratada para desenvolver um produto de análise de riscos. Em determinada funcionalidade desse software, é necessário realizar a ordenação de um conjunto formado por muitos números inteiros. Que algoritmo de ordenação oferece melhor complexidade de tempo (Big O notation) no pior caso?

Os Algoritmos de ordenação colocam os elementos de uma dada sequência em uma certa ordem. As ordens mais usadas são a numérica e a lexicográfica. Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente. Selecione abaixo a alternativa que indica alguns dos mais conhecidos métodos de ordenação: