Algoritmos | Clasificación | Pregunta 1 – Part 6

¿Cuál es la recurrencia para el peor de los casos de QuickSort y cuál es la complejidad del tiempo en el peor de los casos?
(A) La recurrencia es T(n) = T(n-2) + O(n) y la complejidad del tiempo es O(n^2)
(B) La recurrencia es T(n) = T(n-1) + O( n) y la complejidad del tiempo es O(n^2)
(C) La recurrencia es T(n) = 2T(n/2) + O(n) y la complejidad del tiempo es O(nLogn)
(D) La recurrencia es T(n) = T(n/10) + T(9n/10) + O(n) y la complejidad del tiempo es O(nLogn)

Respuesta: (B)
Explicación: El peor caso de QuickSort ocurre cuando el pivot elegido es siempre una de las esquinas elementos en una array ordenada. En el peor de los casos, QuickSort llama recursivamente a un subproblema con tamaño 0 y otro subproblema con tamaño (n-1). Entonces la recurrencia es

T(n) = T(n-1) + T(0) + O(n)

La expresión anterior se puede reescribir como

T(n) = T(n-1) + O(n)

void exchange(int *a, int *b)
{
  int temp;
  temp = *a;
  *a   = *b;
  *b   = temp;
}
   
int partition(int arr[], int si, int ei)
{
  int x = arr[ei];
  int i = (si - 1);
  int j;
   
  for (j = si; j <= ei - 1; j++)
  {
    if(arr[j] <= x)
    {
      i++;
      exchange(&arr[i], &arr[j]);
    }
  }
   
  exchange (&arr[i + 1], &arr[ei]);
  return (i + 1);
}
   
/* Implementation of Quick Sort
arr[] --> Array to be sorted
si  --> Starting index
ei  --> Ending index
*/
void quickSort(int arr[], int si, int ei)
{
  int pi;    /* Partitioning index */
  if(si < ei)
  {
    pi = partition(arr, si, ei);
    quickSort(arr, si, pi - 1);
    quickSort(arr, pi + 1, ei);
  }
}

Cuestionario de esta pregunta