Как реализуется nth_element?

Ответ 1

Вы задали два вопроса: титульный

Как реализуется nth_element?

Что вы уже ответили:

Существует много претензий к StackOverflow и в других местах, где nth_element является O (n) и что он обычно реализуется с помощью Introselect.

Что я также могу подтвердить, глядя на мою реализацию stdlib. (Подробнее об этом позже.)

И тот, где вы не понимаете ответа:

Как алгоритм может переключаться между QSort и Median-of-Medians?

Давайте посмотрим на псевдокод, который я извлек из своего stdlib:

nth_element(first, nth, last)
{ 
  if (first == last || nth == last)
    return;

  introselect(first, nth, last, log2(last - first) * 2);
}

introselect(first, nth, last, depth_limit)
{
  while (last - first > 3)
  {
      if (depth_limit == 0)
      {
          // [NOTE by editor] This should be median-of-medians instead.
          // [NOTE by editor] See Azmisov comment below
          heap_select(first, nth + 1, last);
          // Place the nth largest element in its final position.
          iter_swap(first, nth);
          return;
      }
      --depth_limit;
      cut = unguarded_partition_pivot(first, last);
      if (cut <= nth)
        first = cut;
      else
        last = cut;
  }
  insertion_sort(first, last);
}

Не вдаваясь в подробности о ссылочных функциях heap_select и unguarded_partition_pivot, мы можем ясно видеть, что nth_element дает introselect 2 * log2(size) шаги разбиения (в два раза больше, чем необходимо для быстрого выбора в лучшем случае), пока heap_select пинает и решает проблему навсегда.

Ответ 2

Код STL (версия 3.3, я думаю):

template <class _RandomAccessIter, class _Tp>
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
                   _RandomAccessIter __last, _Tp*) {
  while (__last - __first > 3) {
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1))));
    if (__cut <= __nth)
      __first = __cut;
    else 
      __last = __cut;
  }
  __insertion_sort(__first, __last);
}

Немного упростите это:

template <class Iter, class T>
void nth_element(Iter first, Iter nth, Iter last) {
  while (last - first > 3) {
    Iter cut =
      unguarded_partition(first, last,
                          T(median(*first,
                                   *(first + (last - first)/2),
                                   *(last - 1))));
    if (cut <= nth)
      first = cut;
    else 
      last = cut;
  }
  insertion_sort(first, last);
}

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

Как вы теперь увидите, он многократно разбивает диапазон, пока в оставшемся диапазоне не останется меньше четырех элементов, которые затем просто сортируются.

Теперь, почему это O (n)? Во-первых, окончательная сортировка до трех элементов - это O (1) из-за максимума трех элементов. Теперь остается повторное разбиение. Разделение само по себе является O (n). Здесь каждый шаг уменьшает количество элементов, которые необходимо коснуться на следующем шаге, поэтому у вас есть O (n) + O (n/2) + O (n/4) + O (n/8), который равен меньше, чем O (2n), если вы суммируете его. Так как O (2n) = O (n), вы в среднем имеете сложность линейного текста.

Ответ 3

Отказ от ответственности: я не знаю, как std::nth_element реализуется в любой стандартной библиотеке.

Если вы знаете, как работает Quicksort, вы можете легко изменить его, чтобы делать то, что необходимо для этого алгоритма. Основная идея Quicksort заключается в том, что на каждом шаге вы разбиваете массив на две части, так что все элементы, меньшие, чем точка поворота, находятся в левом суб-массиве, а все элементы, равные или превышающие опорные точки, находятся в правой поддиапазоне, (Модификация Quicksort известная как тройная Quicksort создает третий суб-массив со всеми элементами, равными осями поворота. Затем правый вспомогательный массив содержит только запись строго больше, чем стержень.), То Quicksort протекает рекурсивно сортировки левого и правого суб -arrays.

Если вы хотите только переместить n-й элемент на место, вместо того, чтобы рекурсировать в оба под-массива, вы можете сказать на каждом шаге, нужно ли вам спускаться в левый или правый под-массив. (Вы знаете это, потому что n-й элемент в отсортированном массиве имеет индекс n, поэтому он становится вопросом сравнения индексов.) Итак - если ваш Quicksort не пострадает от наихудшего вырождения - вы примерно вдвое уменьшаете размер оставшегося массива на каждом шаге, (Вы никогда больше не смотрите на другой вспомогательный массив.) Поэтому в среднем на каждом шаге вы имеете дело с массивами следующих длин:

• & Theta; (N)
• & Theta; (N/2)
• & Theta; (N/4)
• ...

Каждый шаг является линейным по длине массива, с которым он имеет дело. (Вы зацикливаете его один раз и решаете, в какой суб-массив каждый элемент должен идти в зависимости от того, как он сравнивается с точкой опоры.)

Вы можете видеть, что после шагов & Theta; (log (N)) мы в конечном итоге достигнем массива singleton и закончим. Если вы суммируете N (1 + 1/2 + 1/4 +...), вы получите 2 N. Или в среднем случае, так как мы не можем надеяться, что стержень всегда будет точно быть медианным, что-то на порядок & theta; (N).