QuickSort медленнее, чем станд :: сортировать

Question

У меня есть быстрая_сортировка код (С ++), который выглядит как этот

template< typename BidirectionalIterator, typename Compare > 
BidirectionalIterator quick_sort_partition(BidirectionalIterator left, BidirectionalIterator right, Compare cmp) { 
    BidirectionalIterator q = left - 1; 
    std::mt19937 gen(time(0)); 
    std::uniform_int_distribution<int> uid(0, right - left - 1); 
    int pivot_1 = uid(gen) ; 
    BidirectionalIterator randomNum = pivot_1 + left; 
    std::iter_swap(randomNum, right); 
    bool index = 0; 
    for (BidirectionalIterator i = left; i < right; i++){ 
     if (*i < *right){ 
      ++q; 
      std::iter_swap(q, i); 
     } 
     if (*i == *right){ 
      index = 1 - index; 
      if(index){ 
       ++q; 
       std::iter_swap(q, i); 
      } 
     } 
    } 

    ++q; 
    std::iter_swap(q, right); 


    return q; 

} 
template< typename BidirectionalIterator, typename Compare > 
void quick_sort(BidirectionalIterator first, BidirectionalIterator last, Compare cmp) { 
    if (first < last){ 
     BidirectionalIterator q = quick_sort_partition(first, last, cmp); 
     quick_sort(first, q - 1, cmp); 
     quick_sort(q + 1, last, cmp); 
    } 
} 

но он медленнее (более 6 раз), чем станд :: сортировать на больших испытаний.

Любые идеи, почему?

Как оптимизировать мой код для хорошей работы?

Answer 1

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

Есть ряд оптимизаций, которые могут быть использованы, среди них:

• Это характерно для «быстрой сортировки» на самом деле быть реализован в виде гибридного сорта, который падает обратно (скажем) Вставка Сортировка для разделов меньше определенного фиксированного порога. Как только вы попадаете на небольшие разделы, накладные расходы Quick Sort имеют тенденцию преодолевать преимущества асимптотической сложности.

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

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

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