Как оптимизировать quicksort

Ответ 1

В Quick-sort вы выбираете случайный стержень, который ограничивает массив до двух половин, большинство шансов на то, что он может быть меньше,

например. Размер массива 100, ось сворачивает массив до 40/60, 40 - меньшего размера.

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

Учтите, что сортировка вставки будет вести себя плохо, если ваш массив отсортирован в обратном порядке (худший случай).

Что касается материала рекурсии, вам нужно всего лишь изменить стоп-регистр рекурсии быстрой сортировки → array size <= 10 stop и отсортировать весь массив (который намного меньше на этом этапе рекурсии) используя inserting сортировка.

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

  Quick-sort()
      choose a pivot
      move the smaller elements from left
      move the bigger elements from right
      quick-sort on the bigger half of the array

      if half is less then X
         only then do an insertion sort on the other half <- this is a tail recursion insertion sort 
      else
         quick sort on this half also

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

Ответ 2

Существует несколько способов сделать стандартную quicksort более эффективной. Чтобы реализовать первый совет со своего поста, вы должны написать что-то вроде:

void quicksort(int * tab, int l, int r)
{
   int q;
   while(l < r)
   {
      q = partition(tab, l, r);
      if(q - l < r - q) //recurse into the smaller half
      {
         quicksort(tab, l, q - 1);
         l = q + 1;
      } else
      {
         quicksort(tab, q + 1, r);
         r = q - 1;
      }
   }
}

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

void quicksort2(int * tab, int l, int r)
{
    int le, ri, q;
    init stack;
    push(l, r, stack);
    while(!empty(stack))
    {
        //take the top pair of values from the stack and set them to le and ri
        pop(le, ri, stack);
        if(le >= ri)
            continue;
        q = partition(tab, le, ri);
        if(q - le < ri - q) //smaller half goes first
        {
            push(le, q - 1, stack);
            push(q + 1, ri, stack);
        } else
        {
            push(q + 1, ri, stack);
            push(le, q - 1, stack);
        }
    }
    delete stack;
}

Затем вы можете приступить к реализации другого совета с вашего сообщения. Для этого вы должны установить произвольную константу, назовите ее CUT_OFF примерно на 20. Это скажет ваш алгоритм, когда он должен переключиться на сортировку вставки. Это должно быть довольно просто (вопрос добавления одного оператора if), чтобы изменить предыдущий пример, чтобы он переключился на сортировку вставки после того, как он достиг точки CUT_OFF, поэтому я оставлю вас на этом.

Что касается метода разделения, я бы рекомендовал использовать раздел Lomuto вместо Hoare.

Однако, если ваши данные уже предварительно отсортированы, вы можете рассмотреть возможность использования другого алгоритма. По моему опыту, сортировка слияния натуральных рядов, реализованная в связанном списке, является очень хорошим выбором, если ваши данные предварительно отсортированы.

Ответ 3

Я написал некоторое время назад алгоритм на основе быстрой сортировки, который вы можете найти там (на самом деле это алгоритм выбора, но также можно использовать алгоритм сортировки):

• http://processors.wiki.ti.com/index.php/Top_K_Elements_Sort_For_DSP_With_Index_Ordering

Уроки, которые я извлек из этого опыта, следующие:

• Тщательно настройте петлю разделов вашего алгоритма. Это часто недооценивается, но вы получаете значительное повышение производительности, если позаботиться о написании циклов, что компилятор/процессор сможет конвейер программного обеспечения. Это само по себе привело к выигрышу около 50% в процессорах.
• Небольшие виды ручного кодирования дают вам крупную победу в форме.. Когда количество элементов, подлежащих сортировке в разделе, составляет не более 8 элементов, просто не надо пытаться рекурсивно, но вместо этого реализуйте жестко кодированный вид, используя только ifs и swaps (посмотрите на функцию fast_small_sort в этом коде), Это может привести к выигрышу около 50% в циклах процессора, что дает быстрой сортировке такую ​​же практическую производительность, как хорошо написанная "сортировка слияния".
• Проведите время, чтобы выбрать лучшее значение поворота, когда обнаружен "плохой" выбор поворота. Моя реализация начинается с использования "медианы медианного" алгоритма для выбора поворота, когда выбор точки сводит к тому, что одна сторона находится под 16% оставшихся элементов, подлежащих сортировке. Это стратегия смягчения для наихудших характеристик быстрой сортировки и помогает гарантировать, что на практике верхняя граница также O (n * log (n)) вместо O (n ^ 2).
• Оптимизация для массивов с большим количеством равных значений (при необходимости). Если массивы, подлежащие сортировке, имеют множество равных значений, которые стоит оптимизировать, поскольку это приведет к плохому выбору стержня. В моем коде я делаю это, подсчитывая все записи массива, равные значению поворота. Это позволяет мне быстрее обрабатывать стержень и все равные значения в массиве и не ухудшает производительность, когда это неприменимо. Это еще одна стратегия снижения производительности для наихудшего случая, она помогает уменьшить использование стека худшего случая, резко уменьшая уровень рекурсии.

Надеюсь, это поможет, Лоран.

Ответ 4

Вы можете взглянуть на TimSort, который для не полностью случайных данных работает лучше, чем quicksort (они имеют одинаковую асимптотическую сложность, но TimSort имеет более низкие константы)

Ответ 5

Недавно я нашел эту оптимизацию. Он работает быстрее, чем std:: sort. Он использует сортировку выбора на небольших массивах и медиану 3 в качестве элемента разделения.

Это моя реализация на С++:

const int CUTOFF = 8;

template<typename T>
bool less (T &v, T &w)
{
    return (v < w);
}

template<typename T>
bool eq (T &v, T &w)
{
    return w == v;
}

template <typename T>
void swap (T *a, T *b)
{
    T t = *a;
    *a = *b;
    *b = t;
}

template<typename T>
void insertionSort (vector<T>& input, int lo, int hi) 
{
    for (int i = lo; i <= hi; ++i)
    {
        for (int j = i; j > lo && less(input[j], input[j-1]); --j)
        {
            swap(&input[j], &input[j-1]);
        }
    }
}


template<typename T>
int median3 (vector<T>& input, int indI, int indJ, int indK)
{
    return (less(input[indI], input[indJ]) ?
            (less(input[indJ], input[indK]) ? indJ : less(input[indI], input[indK]) ? indK : indI) :
            (less(input[indK], input[indJ]) ? indJ : less(input[indK], input[indI]) ? indK : indI));
}


template <typename T>
void sort(vector<T>& input, int lo, int hi) 
{ 
    int lenN = hi - lo + 1;

    // cutoff to insertion sort
    if (lenN <= CUTOFF) 
    {
        insertionSort(input, lo, hi);
        return;
    }

    // use median-of-3 as partitioning element
    else if (lenN <= 40) 
    {
        int median = median3(input, lo, lo + lenN / 2, hi);
        swap(&input[median], &input[lo]);
    }

    // use Tukey ninther as partitioning element
    else  
    {
        int eps = lenN / 8;
        int mid = lo + lenN / 2;
        int mFirst = median3(input, lo, lo + eps, lo + eps + eps);
        int mMid = median3(input, mid - eps, mid, mid + eps);
        int mLast = median3(input, hi - eps - eps, hi - eps, hi); 
        int ninther = median3(input, mFirst, mMid, mLast);
        swap(&input[ninther], &input[lo]);
    }

    // Bentley-McIlroy 3-way partitioning
    int iterI = lo, iterJ = hi + 1;
    int iterP = lo, iterQ = hi + 1;

    for (;; ) 
    {
        T v = input[lo];
        while (less(input[++iterI], v))
        {
            if (iterI == hi) 
                break;
        }
        while (less(v, input[--iterJ]))
        {
            if (iterJ == lo)    
                break;
        }
        if (iterI >= iterJ) 
            break;
        swap(&input[iterI], &input[iterJ]);
        if (eq(input[iterI], v)) 
            swap(&input[++iterP], &input[iterI]);
        if (eq(input[iterJ], v)) 
            swap(&input[--iterQ], &input[iterJ]);
    }
    swap(&input[lo], &input[iterJ]);

    iterI = iterJ + 1;
    iterJ = iterJ - 1;
    for (int k = lo + 1; k <= iterP; ++k) 
    {
        swap(&input[k], &input[iterJ--]);
    }
    for (int k = hi  ; k >= iterQ; --k)
    {
        swap(&input[k], &input[iterI++]);
    }

    sort(input, lo, iterJ);
    sort(input, iterI, hi);
}

Ответ 6

Рекурсия хвоста - это изменение рекурсивного вызова в цикле. Для QuickSort это было бы что-то вроде:

QuickSort(SortVar)                                                                     
   Granularity = 10                                                            
   SortMax = Max(SortVar)
   /* Put an element after the last with a higher key than all other elements 
      to avoid that the inner loop goes on forever */
   SetMaxKey(SortVar, SortMax+1)

   /* Push the whole interval to sort on stack */               
   Push 1 SortMax                                                              
   while StackSize() > 0                                                       
      /* Pop an interval to sort from stack */
      Pop SortFrom SortTo                                                     

      /* Tail recursion loop */                           
      while SortTo - SortFrom >= Granularity                                

         /* Find the pivot element using median of 3 */                            
         Pivot = Median(SortVar, SortFrom, (SortFrom + SortTo) / 2, SortTo)             
         /* Put the pivot element in front */                                     
         if Pivot > SortFrom then Swap(SortVar, SortFrom, Pivot)

         /* Place elements <=Key to the left and elements >Key to the right */           
         Key = GetKey(SortVar, SortFrom)                                                
         i = SortFrom + 1                                                      
         j = SortTo                                                            
         while i < j                                                        
            while GetKey(SortVar, i) <= Key; i = i + 1; end                          
            while GetKey(SortVar, j) > Key; j = j - 1; end                           
            if i < j then Swap(SortVar, i, j)                                       
         end                                                                   

         /* Put the pivot element back */                            
         if GetKey(SortVar, j) < Key then Swap(SortVar, SortFrom, j)                                         

         if j - SortFrom < SortTo - j then                                  
            /* The left part is smallest - put it on stack */                     
            if j - SortFrom > Granularity then Push SortFrom j-1               
            /* and do tail recursion on the right part */                           
            SortFrom = j + 1                                                   
         end                                                                   
         else
            /* The right part is smallest - put it on stack */                       
            if SortTo - j > Granularity then Push j+1 SortTo                   
            /* and do tail recursion on the left part */                         
            SortTo = j - 1                                                     
         end                                                                   
      end                                                                      
   end                                                                         

   /* Run insertionsort on the whole array to sort the small intervals */    
   InsertionSort(SortVar)                                                          
return                                                                         

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

Если у вас нет стека, вы можете использовать рекурсию вместо этого, но сохраните рекурсию хвоста:

QuickSort(SortVar, SortFrom, SortTo)                                                                     
   Granularity = 10                                                            

   /* Tail recursion loop */                           
   while SortTo - SortFrom >= Granularity                                

      /* Find the pivot element using median of 3 */                            
      Pivot = Median(SortVar, SortFrom, (SortFrom + SortTo) / 2, SortTo)             
      /* Put the pivot element in front */                                     
      if Pivot > SortFrom then Swap(SortVar, SortFrom, Pivot)

      /* Place elements <=Key to the left and elements >Key to the right */           
      Key = GetKey(SortVar, SortFrom)                                                
      i = SortFrom + 1                                                      
      j = SortTo                                                            
      while i < j                                                        
         while GetKey(SortVar, i) <= Key; i = i + 1; end                          
         while GetKey(SortVar, j) > Key; j = j - 1; end                           
         if i < j then Swap(SortVar, i, j)                                       
      end                                                                   

      /* Put the pivot element back */                            
      if GetKey(j) < Key then Swap(SortVar, SortFrom, j)                                         

      if j - SortFrom < SortTo - j then                                  
         /* The left part is smallest - recursive call */                     
         if j - SortFrom > Granularity then QuickSort(SortVar, SortFrom, j-1)           
         /* and do tail recursion on the right part */                           
         SortFrom = j + 1                                                   
      end                                                                   
      else
         /* The right part is smallest - recursive call */                       
         if SortTo - j > Granularity then QuickSort(SortVar, j+1, SortTo)                   
         /* and do tail recursion on the left part */                         
         SortTo = j - 1                                                     
      end                                                                   
   end                                                                         

   /* Run insertionsort on the whole array to sort the small intervals */    
   InsertionSort(SortVar)                                                          
return