MO417 - Questão para a prova oral

Número: 2003-004

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 à sua eficiência, podemos afirmar que:

1. o melhor caso ocorre quando o vetor  x[]  está ordenado em ordem decrescente.
2. o melhor caso ocorre quando o vetor  x[]  está ordenado em ordem crescente.
3. o melhor caso ocorre quando o vetor  x[]  não está ordenado.
4. independentemente do estado de ordenação em que se encontra o vetor  x[] , o algoritmo executa sempre o mesmo número de operações.
5. NDA 

Ideia original de:  Alexandro Baldassin