Ответ 1
TL; DR: Проблема заключается в стратегии выбора поворота, которая делает неоднозначные варианты выбора этих типов входов (последовательности A- и V-образных последовательностей). Это приводит к быстрому сортировке, что приводит к "неуравновешенным" рекурсивным вызовам, что, в свою очередь, приводит к тому, что алгоритм работает очень плохо (квадратичное время для A-образных последовательностей).
Поздравляем, вы (повторно) обнаружили, состязательный ввод (или, скорее, семейство входов) для версии быстрой сортировки, который выбирает средний элемент как стержень.
Для ссылки пример A-образной последовательности 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), потому что на каждом шаге вы, по существу, передаете почти весь массив ( все элементы, за исключением точки поворота), другими словами, размеры массивов в рекурсивных вызовах сильно несбалансированы.
Здесь след для A-образной последовательности 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 для A-образных последовательностей 1 2 ... n-1 n n-1 ... 2 1:
Во втором случае, когда вы передаете алгоритму V-образную последовательность, вы выбираете наименьший элемент массива в качестве точки опоры и, таким образом, рекурсивные вызовы на подмассивах размеров n-1 и 0 (ваш код фактически не вызывает вызов 0). В следующем вызове в подмассиве размером n-1 вы выберете в качестве свода наибольший элемент; и так далее. (Но вы не всегда будете делать такие ужасные выборы, о чем трудно сказать об этом случае.) Это приводит к плохой работе по аналогичным причинам. Этот случай немного сложнее (это зависит от того, как вы делаете шаг "move" ).
Здесь приведен график времени работы для 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) времени с высокой вероятностью, (Обратите внимание, однако, что для отображения этой жесткой хвостовой границы вам нужны некоторые предположения на входе, результат, безусловно, имеет место, если все цифры различны, см., Например, книгу Motwani и Raghavan Randomized Algorithms.)
Чтобы подтвердить мои претензии, здесь график времени выполнения для тех же последовательностей, если вы выбираете шарнир равномерно случайным образом, с x = tab[l + (rand() % (p-l))]; (убедитесь, что вы вызываете srand(time(NULL)) в основном).
Для А-образных последовательностей:
Для V-образных последовательностей:
