Existe um grande número de implementações para algoritmos de ordenação. Um dos fatores ...

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:

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