Questão de Tecnologia da Informação

Existe um grande número de implementações para algoritmos de ordenação. Um dos fatores a serem considerados, por exemplo, é o número máximo e médio de comparações que são necessárias para ordenar um vetor com n elementos. Diz-se também que um algoritmo de ordenação é estável se ele preserva a ordem de elementos que são iguais. Isto é, se tais elementos aparecem na sequência ordenada na mesma ordem em que estão na sequência inicial. Analise o algoritmo abaixo, onde a é um vetor e “i, j, lo e hi” são índices do vetor: algoritmo ordena(A, lo, hi) se lo < hi então p := particao(A, lo, hi) ordena(A, lo, p - 1) ordena(A, p + 1, hi) algoritmo particao(A, lo, hi) pivot := A[hi] i := lo repita para j := lo até hi se A[j] < pivot entao troca A[i] com A[j] i := i + 1 troca A[i] com A[hi] return i Com relação ao algoritmo apresentado, avalie as afirmações a seguir. I. O algoritmo precisa de um espaço adicional O(n) para a pilha de recursão. II. O algoritmo apresentado é um algoritmo de ordenação recursivo e estável. III. O algoritmo precisa, em média, de O(n log n) comparações para ordenar n itens. IV. O uso do primeiro elemento do vetor como “pivot” é mais eficiente que usar o último. É correto apenas o que se afirma em