Рубрики

Алгоритмы | Сортировка | Вопрос 1

Что такое повторение для наихудшего случая быстрой сортировки и какова временная сложность в худшем случае?
(A) Повторение — это T (n) = T (n-2) + O (n), а сложность по времени — O (n ^ 2)
(B) Рецидив равен T (n) = T (n-1) + O (n), а сложность по времени равна O (n ^ 2).
(C) Рецидив равен T (n) = 2T (n / 2) + O (n), а сложность по времени равна O (nLogn).
(D) Рецидив равен T (n) = T (n / 10) + T (9n / 10) + O (n), а временная сложность равна O (nLogn).

Ответ: (Б)
Объяснение: Наихудший случай быстрой сортировки возникает, когда выбранная опорная точка всегда является одним из угловых элементов в отсортированном массиве. В худшем случае QuickSort рекурсивно вызывает одну подзадачу с размером 0, а другую подзадачу с размером (n-1). Так что повторение

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

Вышеупомянутое выражение может быть переписано как

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);

}

   
/ * Реализация быстрой сортировки
arr [] -> Массив для сортировки
si -> Начальный индекс
ei -> Конечный индекс
* /

void quickSort(int arr[], int si, int ei)

{

  int pi;    / * Индекс разделения * /

  if(si < ei)

  {

    pi = partition(arr, si, ei);

    quickSort(arr, si, pi - 1);

    quickSort(arr, pi + 1, ei);

  }

}

Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | Сортировка | Вопрос 1

0.00 (0%) 0 votes