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

Question

При реализации быстрой сортировки одна из вещей, которую вам нужно сделать, это выбрать опору. Но когда я смотрю на псевдокод, подобный приведенному ниже, неясно, как мне выбрать пивот. Первый элемент списка? Что-то еще?

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

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

Answer 1

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

Кроме того, если вы реализуете это самостоятельно, существуют версии алгоритма, которые работают на месте (т. Е. Без создания двух новых списков и последующего их объединения).

Answer 2

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

---

Обновление: добавление комментариев в ответ.

MDKESS заявлено:

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

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

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

• Есть статья, описанная на portal.acm.org , посвященная «Перестановке наихудшего случая для быстрой медианы-три» Ханну Эркио, опубликованная в The Computer Journal, том 27 , № 3, 1984. [Обновление 2012-02-26: Получил текст для статьи . Раздел 2 «Алгоритм» начинается: « Используя медиану первого, среднего и последнего элементов A [L: R], эффективные разбиения на части довольно равных размеров могут быть достигнуты в большинстве практических ситуаций. 'Таким образом, речь идет о подходе Mo3 с первым-средним-последним.]

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

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

• «Проектирование функции сортировки» Дж. Л. Бентли и М. Д. Макилроя, опубликованное в «Software Practice and Experience», том 23 (11), ноябрь 1993 г., посвящено широкому обсуждению вопросов, и они выбрали алгоритм адаптивного разделения, основанный частично на размере набора данных. Существует много обсуждений компромиссов для различных подходов.

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

Спасибо за информацию; Раньше я встречал только детерминированную «медиану трех».

Answer 3

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

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

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

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

Answer 6

Проще всего разбить быструю сортировку на три секции

1. Функция обмена или обмена элементов данных
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
  };
};

Answer 7

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

Answer 8

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

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

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

Answer 9

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

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

Answer 10

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

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