INEP, ENADE

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.

1. I. O algoritmo precisa de um espaço adicional O(n) para a pilha de recursão.
2. II. O algoritmo apresentado é um algoritmo de ordenação recursivo e estável.
3. III. O algoritmo precisa, em média, de O(n log n) comparações para ordenar n itens.
4. IV. O uso do primeiro elemento do vetor como “pivot” é mais eficiente que usar o último.

É correto apenas o que se afirma em