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

StackOverflow https://stackoverflow.com/questions/164163

Вопрос

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

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

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

Это было полезно?

Решение

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

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

Другие советы

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

Обновить:Превращение комментариев в ответ.

мдкесс утвержденный:

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

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

  • Анализ алгоритма поиска Хоара с разделением по медиане из трех (1997) П. Киршенхофер, Х. Продингер, К. Мартинес поддерживают ваше утверждение (что "медиана из трех" - это три случайных элемента).

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

  • Еще одна интересная короткая статья написана М.D.Макилрой, "Убийственный противник для быстрого приготовления", опубликовано в журнале Software-Practice and Experience, Vol.29(0), 1–4 (0 1999).В нем объясняется, как заставить практически любую быструю сортировку вести себя квадратично.

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

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

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

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

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

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

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

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

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

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

Никогда не выбирайте фиксированную опорную точку - на нее можно напасть, чтобы использовать наихудший вариант выполнения 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) (и будет намного быстрее). чем это хромая быстрая сортировка).

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

Не пытайтесь стать слишком умными и комбинируйте стратегии поворота. Если вы скомбинировали медиану 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.5N * log N)

Это проще разбить быстрой сортировкой на три части

<Ол>
  • Функция обмена или замены элемента данных
  • Функция разделения
  • Обработка разделов

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

    Код следующий: 

    /* 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
  };
};

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

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

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

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

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

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

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

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

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top