std :: partition quick sort реализация

Question

Я думал, что моя реализация ниже работает, но, видимо, нет. Любые идеи о том, что не так с этой быстрой сортировкой, используя std::partition? У меня есть версия, использующая версию nth_element, которая работает с очень похожим и более простым кодом, чем это.

template <typename It> 
void quickSort (const It& lowerIt, const It& upperIt) 
{ 
    auto d = upperIt - lowerIt ; 
    if (d < 2) 
    return; 

    auto midIt = lowerIt + d/2; 

    using T = typename std::iterator_traits<It>::value_type; 

    T midValue = *midIt; 

    auto pIt = std::partition (lowerIt, upperIt, [midValue](T i) { return i < midValue; }); 

    quickSort(lowerIt, pIt); 
    quickSort(pIt + 1, upperIt); 
} 

Использование раздела:

Перед:

83, 86, 77, 15, 93, 35, 86, 92, 49, 21,

После:

21, 15, 77, 35, 49, 83, 86, 92, 86, 93,

Answer 1

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

• выбрать поворотный элемент
• своп шарнирный элемент с *std::prev(upperIt)
• использования std::partition на полигоне [lowerIt, std::prev(upperIt))
• своп pIt с *std::prev(upperIt)
• вызова быстро -sort рекурсивно, как в вашем коде

Вот Исправленная версия кода:

template <typename It> 
void quickSort(It lowerIt, It upperIt) 
{ 
    using std::swap; 
    auto size = std::distance(lowerIt, upperIt); 
    if (size > 1) { 
     auto p = std::prev(upperIt); 
     swap(*std::next(lowerIt, size/2), *p); 
     auto q = std::partition(lowerIt, p, [p](decltype(*p) v) { return v < *p; }); 
     swap(*q, *p); 
     quickSort(lowerIt, q); 
     quickSort(std::next(q), upperIt); 
    } 
} 

Answer 2

Ваш код имеет несколько серьезных проблем. Давайте рассмотрим их индивидуально.

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

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

Во-вторых, как и почти все, что использует итераторы, std::partition предполагает полуоткрытый диапазон - то есть, что первые точки итераторов на начало диапазона, а вторые очки итераторов просто мимо конца диапазон. Это означает, что вы хотите, чтобы ваши рекурсивные вызовы быть:

quicksort(lowerIt, pIt); 
quicksort(pIt, upperIt); 

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

Для «серьезной» реализации Quicksort есть несколько других деталей вы, вероятно, хотите изменить, а, например, останавливая рекурсию, когда размер раздела получает вниз на что-то вроде 20 пунктов, а затем, когда вы закончите таким образом, сделайте сортировку вставки по всей коллекции, чтобы все было в ее конечном месте отдыха (так сказать).

Аналогичным образом, чтобы избежать переполнения стека, вы обычно хотите отсортировать меньшее из двух разделов. Это гарантирует, что пространство стека никогда не будет превышать O (log N). Как и в настоящее время, пространство стека может быть наихудшим случаем O (N).