TL; DR: Проблема заключается в стратегии выбора стержня, которая делает неоднозначные варианты выбора этих типов входов (последовательности A- и V-образной формы). Это приводит к быстрому сортировке, что приводит к «неуравновешенным» рекурсивным вызовам, что, в свою очередь, приводит к тому, что алгоритм работает очень плохо (квадратичное время для A-образных последовательностей).
Поздравляем, вы обнаружили новый (или, скорее, семейство входов) для версии quicksort, которая выбирает средний элемент в качестве точки опоры.
Для справки, пример А-образной последовательности является 1 2 3 4 3 2 1, т.е. последовательность, которая увеличивается, достигает выбор в середине, а затем уменьшается; пример V-образной последовательности равен 4 3 2 1 2 3 4, то есть последовательность, которая уменьшается, достигает минимума в середине и затем увеличивается.
Подумайте о том, что происходит, когда вы выбираете средний элемент как ось A- или V-образной последовательности. В первом случае, когда вы передаете алгоритм A-образной последовательности 1 2 ... n-1 n n-1 ... 2 1, стержень является самым большим элементом массива --- это потому, что самый большой элемент A-образной последовательности является средним, и вы выбираете средний элемент в качестве поворота --- и вы будете делать рекурсивные вызовы в подмассивах размеров 0 (ваш код фактически не делает звонок по 0 элементам) и n-1. В следующем вызове в подмассиве размером n-1 вы выберете в качестве свода наибольший элемент подмассива (который является вторым по величине элементом исходного массива); и так далее. Это приводит к низкой производительности, так как время работы O (n) + O (n-1) + ... + O (1) = O (n^2), потому что на каждом шаге вы, по сути, проходите почти по всему массив (все элементы, за исключением точки поворота), другими словами, размеры массивов в рекурсивных вызовах сильно несбалансированы.
Вот след для А-образной последовательности 1 2 3 4 5 4 3 2 1:
[email protected]:/tmp$ ./test
pivot=5
1 2 3 4 1 4 3 2 5
pivot=4
1 2 3 2 1 3 4 4
pivot=3
1 2 3 2 1 3
pivot=3
1 2 1 2 3
pivot=2
1 2 1 2
pivot=2
1 1 2
pivot=1
1 1
pivot=4
4 4
1 1 2 2 3 3 4 4 5
Вы можете видеть из след, что при рекурсивном вызове алгоритм выбирает большой элемент (может быть до двух крупнейших элементов, следовательно, статья a, а не ) в качестве стержня. Это означает, что время работы для A-образной последовательности действительно O (n) + O (n-1) + ... + O (1) = O (n^2). (В техническом жаргоне А-образная последовательность является примером состязательного ввода, который заставляет алгоритм работать плохо.)
Это означает, что если вы планируете время выполнения для «отлично» A-образных последовательностей формы
1 2 3 ... n-1 n n-1 ... 3 2 1
для увеличения n, вы увидите хороший квадратичной функции. Вот график, я просто вычислить для n=5,105, 205, 305,...,9905 для А-образных последовательностей 1 2 ... n-1 n n-1 ... 2 1:
Во втором случае, при передаче алгоритма последовательность V-образную форму, Вы выбираете наименьший элемент массива, что и pivot, и, таким образом, вызовет рекурсивные вызовы в подмассивах размеров n-1 и 0 (ваш код фактически не делает звонок по 0 элементам). В следующем вызове в подвале размером n-1 вы выберете в качестве свода самый большой элемент; и так далее. (Но вы не всегда будете делать такие ужасные выборы, и в этом случае сложно сказать больше). Это приводит к низкой производительности по аналогичным причинам. Этот случай немного сложнее (это зависит от того, как вы делаете шаг «перемещение»).
Посмотрите график времени работы для V-образных последовательностей n n-1 ... 2 1 2 ... n-1 n для n=5,105,205,...,49905. Время работы несколько менее регулярное, так как я сказал, что это сложнее, потому что вы не всегда выбираете наименьший элемент в качестве точки опоры. График:
код, который я использовал для измерения времени:
double seconds(size_t n) {
int *tab = (int *)malloc(sizeof(int) * (2*n - 1));
size_t i;
// construct A-shaped sequence 1 2 3 ... n-1 n n-1 ... 3 2 1
for (i = 0; i < n-1; i++) {
tab[i] = tab[2*n-i-2] = i+1;
// To generate V-shaped sequence, use tab[i]=tab[2*n-i-2]=n-i+1;
}
tab[n-1] = n;
// For V-shaped sequence use tab[n-1] = 1;
clock_t start = clock();
quicksort(0, 2*n-2, tab);
clock_t finish = clock();
free(tab);
return (double) (finish - start)/CLOCKS_PER_SEC;
}
Я приспособил свой код, чтобы напечатать «след» алгоритма, так что вы можете играть с ним самостоятельно и усиления понимание того, что происходит:
#include <stdio.h>
void print(int *a, size_t l, size_t r);
void quicksort(int l,int p,int *tab);
int main() {
int tab[] = {1,2,3,4,5,4,3,2,1};
size_t sz = sizeof(tab)/sizeof(int);
quicksort(0, sz-1, tab);
print(tab, 0, sz-1);
return 0;
}
void print(int *a, size_t l, size_t r) {
size_t i;
for (i = l; i <= r; ++i) {
printf("%4d", a[i]);
}
printf("\n");
}
void quicksort(int l,int p,int *tab)
{
int i=l,j=p,x=tab[(l+p)/2],w; //x - pivot
printf("pivot=%d\n", x);
do
{
while (tab[i]<x)
{
i++;
}
while (x<tab[j])
{
j--;
}
if (i<=j)
{
w=tab[i];
tab[i]=tab[j];
tab[j]=w;
i++;
j--;
}
}
while (i<=j);
print(tab, l, p);
if (l<j)
{
quicksort(l,j,tab);
}
if (i<p)
{
quicksort(i,p,tab);
}
}
Кстати, я думаю, что график, показывающий бегущих раз будет гладко, если вы взяли в среднем, скажем, в 100 раз бегущие для каждой входной последовательности.
Мы видим, что проблема заключается в стратегии выбора стержня. Позвольте мне заметить, что вы можете устранить проблемы с состязательными входами, используя случайный выбор. Самый простой подход - выбрать шарнир равномерно случайным образом (каждый элемент в равной степени может быть выбран в качестве стержня); вы можете показать, что алгоритм работает в O (n log n) время with high probability.(Заметим, однако, что, чтобы показать этот острый хвост связаны вам нужны некоторые предположения на входе, результат, безусловно, имеет место, если эти цифры различны, см., Например, Motwani и рандомизированные Алгоритмы книги Рагаван в)
Чтобы подтвердить мои претензии, вот график времени работы для тех же последовательностей, если вы выбираете шарнир равномерно случайным образом, с x = tab[l + (rand() % (p-l))]; (убедитесь, что вы в основном вызываете srand(time(NULL))). Для получения А-образных последовательностей: 
Для V-образных последовательностей:
Известный недостаток в среднем с быстрой сортировки поворота. Классическая. – SergeyA
@SergeyA Я искал интернет для подобных графиков и ничего не нашел. Есть ли место, где я мог бы прочитать, почему он прыгает между сложностями? – vois
Ну, какова ваша метрика для создания такого эпического графа? Вы измеряете время? Как? – tomascapek