Блог

Я знаю, как рассчитать сложность только для быстрой сортировки и сортировки по вставке, но когда я смешиваю их…

Вот код:

 #define THRESHOLD 50

// regular insertion sort
void isort(int *array, size_t n) {
  int key, i, j;
  for(j = 1; j < n; j  ){
    key = array[j];
    i = j - 1;
    while (array[i] > key amp;amp; i>=0) {
      array[i   1] = array[i];
      i--;
    }
    array[i   1] = key;
  }
}

// modified quick sort
static void sort(int *array, int start, int end) {
  if (end - start > THRESHOLD) {
    int pivot = array[start];
    int l = start   1;
    int r = end;
    while(l < r) {
       if (array[l] < pivot) {
          l  = 1;
       } else if ( array[r] >= pivot )  {
          r -= 1;
       } else {
          swap(amp;array[l], amp;array[r]);
       }
    }
    if (array[l] < pivot) {
      swap(amp;array[start], amp;array[l]);
      l -= 1;
    } else {
      l -= 1;
      swap(amp;array[start], amp;array[l]);
    }

    sort(array, start, l);
    sort(array, r, end);
  } else {
    isort(array, end - start   1);
  }
}
  

Подводя итог: это рекурсивная быстрая сортировка, за исключением того, что, когда входящий вектор ниже порогового значения, используется сортировка по вставке.

Как мне рассчитать временную сложность для наилучшего, среднего и наихудшего случаев?

Часть, которая сбивает с толку, заключается в том, что, когда размер раздела достигает 50 или меньше, мы выполняем сортировку по вставке. Конкретное значение (50) не так важно, поэтому я переключу его на 64 для немного более простых вычислений. При выполнении рекурсивной формулы для среднего случая qsort мы предполагаем, что сортировка раздела размером 64 требует операций log (64) * 64, что, по-видимому, является константой. Обратите внимание, что 64 является константой, и сортировка 64 элементов с помощью insert займет порядок O (64 * 64) даже в худшем случае. Это все еще константа. Таким образом, мы изменим только константу сложности асимптотического поведения qsort, но не будем изменять саму функцию.

При этом я хочу сказать, что выполнение другого алгоритма ниже фиксированного порога может изменить постоянный коэффициент вашего алгоритма, но это не изменит его сложность. Это останется неизменным для всех случаев, которые вы упомянули.