Быстрая сортировка: выбор оси

Это зависит от ваших требований. Выбор случайного поворота затрудняет создание набора данных, который генерирует производительность O(N^2). "Медиана из трех" (первая, последняя, средняя) также является способом избежать проблем. Однако остерегайтесь относительной производительности сравнений; если ваши сравнения являются дорогостоящими, то Mo3 делает больше сравнений, чем выбор (одно значение pivot) случайным образом. Записи базы данных могут быть дорогостоящими для сравнения.

---

обновление: вытягивание комментариев в ответ.

mdkess утверждает:

'медиана 3' - это не первая последняя середина. Выберите три случайных индекса и возьмите среднее значение этого. Все дело в том, чтобы убедиться, что ваш выбор пивотов не является детерминированным - если это так, худшие данные могут быть довольно легко сгенерированы.

на что я ответил:

• анализ алгоритма поиска Хоара с разделением медианы из трех (1997) P Kirschenhofer, H Prodinger, C Martínez поддерживает ваше утверждение (что "медиана из трех" -это три случайных элемента).

• есть статья, описанная в portal.acm.org речь идет о "наихудшем случае перестановки для медианы из трех Quicksort" Ханну Эркие, опубликованной в Computer Journal, Vol 27, No 3, 1984. [Обновление 2012-02-26: получил текст для статьи. Раздел 2 'алгоритм' начинается так:'С помощью медианы из первого, среднего и последнего элементов A[L:R] в большинстве практических ситуаций могут быть достигнуты эффективные разбиения на части довольно равных размеров.' таким образом, он обсуждает первый-средний-последний подход Mo3.]

• еще одна короткая статья, которая интересна является М. Д. Макилрой, "убийца противника для Quicksort", опубликовано в Software-Practice and Experience, Vol. 29(0), 1-4 (0 1999). Это объясняет, как заставить вести себя почти любой Quicksort квадратично.

• AT&T Bell Labs Tech Journal, Oct 1984 "теория и практика в построении рабочей процедуры сортировки" состояния "Хоар предложил разбиение вокруг медианы нескольких случайно выбранных строк. Седжвик [...] рекомендуется выбрать медиану первого [...] последний.[ ..] и средний". Это указывает на то, что оба метода для "медианы трех" известны в литературе. (Обновление 2014-11-23: статья, похоже, доступна по адресу IEEE Xplore или Уайли - если у вас есть членство или готовы платить комиссии.)

• "проектирование функции сортировки" J L Bentley и M D McIlroy, опубликованные в Software Practice and Experience, Vol 23 (11), ноябрь 1993 года, подробно обсуждают эти вопросы, и они выбрали адаптивный алгоритм разбиения, частично основанный на размере набора данных. Существует много обсуждений компромиссов для различных подходы.

• поиск Google для "медианы из трех" работает довольно хорошо для дальнейшего отслеживания.

Спасибо за информацию; раньше я сталкивался только с детерминированной "медианой трех".

Хех, я только что преподавал этот класс.

есть несколько вариантов.
Просто: выберите первый или последний элемент диапазона. (плохо на частично отсортированном входе) Лучше: выберите пункт в середине диапазона. (лучше на частично отсортированном входе)

однако выбор любого произвольного элемента рискует плохо разбить массив размера n на два массива размера 1 и n-1. Если вы делаете это достаточно часто, ваш quicksort рискует стать O (n^2).

одно улучшение, которое я видел, - это медиана выбора(первый, последний, средний); В худшем случае он все еще может перейти к O(n^2), но вероятностно это редкий случай.

для большинства данных достаточно выбрать первый или последний. Но, если вы обнаружите, что вы часто сталкиваетесь с худшими сценариями (частично отсортированным вводом), первым вариантом будет выбрать центральное значение( которое является статистически хорошим стержнем для частично отсортированных данных).

Если вы все еще столкнувшись с проблемами, затем идите по срединному маршруту.

никогда не выбирайте фиксированный pivot - это может быть атаковано, чтобы использовать худший случай вашего алгоритма o(n^2) runtime, который просто напрашивается на неприятности. Наихудший случай выполнения Quicksort происходит, когда результаты секционирования в один массив из 1 элемента и один массив из n-1 элементов. Предположим, вы выбрали первый элемент в качестве раздела. Если кто-то подает массив в ваш алгоритм, который находится в порядке убывания, ваш первый пивот будет самым большим, поэтому все остальное в массиве переместится влево его. Затем, когда вы рекурсию, первый элемент будет опять большая, так что еще раз все поставить с левой стороны от него, и так далее.

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

Если вы абсолютно хотите гарантировать выполнение o(nlgn) для алгоритма, метод columns-of-5 для нахождения медианы массива выполняется за O(n) время, что означает, что рекуррентное уравнение для quicksort в худшем случае будет T(n) = O (n) (найти медиану) + O (n) (раздел) + 2T (n/2) (рекурсия влево и вправо.) По основной теореме это O (n lg n). Тем не менее, постоянный фактор будет огромным, и если наихудшая производительность является вашей основной заботой, используйте вместо этого сортировка слиянием, которая в среднем немного медленнее, чем quicksort, и гарантирует время O(nlgn) (и будет намного быстрее, чем этот хромой медианный quicksort).

объяснение медианы алгоритма медиан

Не пытайтесь стать слишком умным и комбинировать поворотные стратегии. Если вы объединили медиану 3 со случайным поворотом, выбрав медиану первого, последнего и случайного индекса в середине, то вы все равно будете уязвимы для многих распределений, которые отправляют медиану 3 квадратичных (так что ее на самом деле хуже, чем простой случайный поворот)

Например, распределение органа трубы (1,2,3...N / 2..3,2,1) первый и последний будут равны 1, а случайный индекс будет некоторым числом больше 1, принимая медиана дает 1 (либо первый, либо последний), и вы получаете чрезвычайно несбалансированное разбиение.

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

Если вы сортируете случайную доступную коллекцию (например, массив), лучше всего выбрать физический средний элемент. При этом, если массив полностью отсортирован (или почти отсортирован), два раздела будут близки к четным, и вы получите лучшую скорость.

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

однако для связанного списка выбор чего-либо, кроме первого, только ухудшит ситуацию. Он выбирает средний элемент в списке, вам нужно будет пройти через него на каждом шаге раздела-добавление операции O(N/2), которая выполняется logN раз, делая общее время O (1.5 N *log N) , и это если мы знаем, как долго список, прежде чем мы начнем-обычно мы этого не делаем, поэтому нам нужно будет шагнуть полностью, чтобы посчитать их, затем шаг на полпути, чтобы найти середину, а затем шаг через третий раз, чтобы сделать фактический раздел: O (2.5 N * log N)

проще разбить quicksort на три секции, делая это

1. функция элемента данных Exchange или swap
2. функции раздел
3. обработка разделы

это только немного более неэффективно, чем одна длинная функция, но намного легче понять.

код ниже:

/* This selects what the data type in the array to be sorted is */

#define DATATYPE long

/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */

void swap (DATATYPE *x, DATATYPE *y){  
  DATATYPE Temp;

  Temp = *x;        // Hold current x value
  *x = *y;          // Transfer y to x
  *y = Temp;        // Set y to the held old x value
};


/* This is the partition code */

int partition (DATATYPE list[], int l, int h){

  int i;
  int p;          // pivot element index
  int firsthigh;  // divider position for pivot element

  // Random pivot example shown for median   p = (l+h)/2 would be used
  p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point

  swap(&list[p], &list[h]);                   // Swap the values
  firsthigh = l;                                  // Hold first high value
  for (i = l; i < h; i++)
    if(list[i] < list[h]) {                 // Value at i is less than h
      swap(&list[i], &list[firsthigh]);   // So swap the value
      firsthigh++;                        // Incement first high
    }
  swap(&list[h], &list[firsthigh]);           // Swap h and first high values
  return(firsthigh);                          // Return first high
};



/* Finally the body sort */

void quicksort(DATATYPE list[], int l, int h){

  int p;                                      // index of partition 
  if ((h - l) > 0) {
    p = partition(list, l, h);              // Partition list 
    quicksort(list, l, p - 1);        // Sort lower partion
    quicksort(list, p + 1, h);              // Sort upper partition
  };
};

В идеале pivot должен быть средним значением во всем массиве. Это уменьшит шансы на получение худшего случая производительности.

сложность быстрой сортировки сильно зависит от выбора значения pivot. например, если вы всегда выбираете первый элемент в качестве опорного, сложность алгоритма становится такой же худшей, как O(n^2). вот такой умный метод, чтобы выбрать поворотный элемент- 1. выбрать первый, средний, последний элемент массива. 2. сравните эти три числа и найдите число, которое больше одного и меньше другого, т. е. медиана. 3. сделайте этот элемент как поворотный элемент.

выбор оси по этому метод разбивает массив почти на две половины и, следовательно, сложность сводится к O(nlog (n)).

в среднем медиана 3 хороша для малого n. медиана 5 немного лучше для большего n. девятый, который является "медианой трех медиан трех", еще лучше для очень большого n.

чем выше вы идете с выборкой, тем лучше вы получаете по мере увеличения n, но улучшение резко замедляется по мере увеличения образцов. И вы несете накладные расходы на отбор и сортировку образцов.

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

вы можете вычислить его путем округления (массив.длина / 2).

в действительно оптимизированной реализации метод выбора pivot должен зависеть от размера массива - для большого массива он окупается, чтобы тратить больше времени на выбор хорошего pivot. Без полного анализа я бы предположил, что" середина o(log(n)) элементов " -это хорошее начало, и это имеет дополнительный бонус, не требующий дополнительной памяти: используя хвостовой вызов на более крупном разделе и разбиение на месте, мы используем ту же самую o(log(n)) дополнительную память почти на каждом этапе алгоритма.