C++ QuickSort Pivot Optimization

Question

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

int* partition (int* first, int* last); 
void quickSort(int* first, int* last) { 
    if (last - first <= 1) return; 

    int* pivot = partition(first, last); 
    quickSort(first, pivot); 
    quickSort(pivot + 1, last); 
} 

int* partition (int* first, int* last) { 
    int pivot = *(last - 1); 
    int* i = first; 
    int* j = last - 1; 

    for (;;) { 
     while (*i < pivot && i < last) i++; 
     while (*j >= pivot && j > first) j--; 
     if (i >= j) break; 
     swap (*i, *j); 
    } 

    swap (*(last - 1), *i); 

    return i; 
} 

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

Как мне это сделать?

Я новичок в сортировке алгоритмов, и мое понимание их еще не завершено.

Answer 1

Просто измените следующие строки:

int pivot = *(last - 1); 
    … 
    swap ((last - 1), i); 

к чему-то вроде:

int* pos = (first + rand(last - first)); 
    int pivot = *pos; 
    … 
    swap (pos, i); 

или

int* pos = mean_of_three((last - 1), (first), ((first + last)/2)); 
    int pivot = *pos; 
    … 
    swap (pos, i); 

где mean_of_three взять 3 указатели и возвращает указатель на среднее значение.

Answer 2

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

Answer 3

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

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

int PickPivotUsingMedian(int a[], int first, int last) 
{ 
int mid = (first+ right)/2; 
if (a[mid ] < a[first]) 
    swap(&a[first],&a[mid ]); 
if (a[last] < a[first]) 
    swap(&a[first],&a[last]); 
if (a[last]< a[mid ]) 
    swap(&a[mid ],&a[last]); 

swap(&a[mid], &a[last - 1]);//since the largest is already in the right. 
return a[last - 1]; 
}