Enunciado:
Considere o algoritmo insertion sort representado abaixo como um programa escrito em C:

void insertsort(int x[], int n)
{
   int i, k, y;
   for (k = 1; k < n; k++)
   {
      y = x[k];
      for (i = k-1; i >= 0 && y < x[i]; i--)
         x[i+1] = x[i];
      x[i+1] = y;
   }
}

onde x[] é um vetor de inteiros quaisquer e n é o número de elementos desse vetor, com n > 0. Quanto a sua eficiência, podemos afirmar que:

A) melhor caso ocorre quando o vetor x[] está ordenado em ordem decrescente
B) melhor caso ocorre quando o vetor x[] está ordenado em ordem crescente
C) melhor caso ocorre quando o vetor x[] não está ordenado
D) independentemente da ordem em que se encontram os elementos do vetor x[], o algoritmo possui sempre a mesma eficiência
E) NDA

Autor: Alexandro Baldassin