Быстрая сортировка времени, С++

Ответ 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-образных последовательностей:

Ответ 2

в QuickSort одним из основных факторов, влияющих на время работы, является входной ramdom.

в общем случае выбор стержня в определенной позиции может быть не лучшим, если не считать, что вход случайным образом перетасован. Использование median of three partition является одним из широко используемых средств, чтобы удостовериться, что стержень является случайным числом. Из вашего кода вы его не реализовали.

Кроме того, когда рекурсивная quicksort будет испытывать некоторые накладные расходы с момента использования внутреннего стека (придется генерировать несколько функций и назначать параметры), поэтому рекомендуется, чтобы размер оставшихся данных находился вокруг 10 - 20, вы можете использовать другой вид алгоритм, подобный InsertionSort, поскольку это ускорит процесс 20%.

void quicksort(int l,int p,int *tab){
  if ( tab.size <= 10 ){

      IntersionSort(tab);
   }
 ..
 ..}

Что-то в этом роде.

В целом лучшее время работы для быстрой сортировки - nlogn хуже время работы n ^ 2 часто вызвано входами non-random или входами duplicates

Ответ 3

Все ответы здесь имеют очень хорошие моменты. Моя идея состоит в том, что в алгоритме нет ничего плохого (поскольку проблема с опорой хорошо известна и является причиной O (n ^ 2), но есть что-то не так, как вы ее измеряете.

clock() - возвращает количество тиков процессора, прошедших с некоторой точки (возможно, запуск программы? Не важно).

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

Точка в том, что многие (все?) современных современных процессоров динамически меняют свою частоту, чтобы сэкономить энергию. Я думаю, это очень не детерминировано, поэтому каждый раз, когда вы запускаете свою программу, частота процессора будет зависеть не только от размера вашего ввода, но и от того, что происходит в вашей системе прямо сейчас. Как я понимаю, длина одного тика может отличаться при выполнении программы.

Я попытался найти, что делает макрос CLOCKS_PER_SEC. Это текущие часы в секунду? Имеет ли он некоторые средние значения в течение какого-то загадочного периода времени? Я, к сожалению, не смог узнать. Поэтому я считаю, что ваш способ измерения времени может быть ошибочным.

Так как мой аргумент стоит на чем-то, я точно не знаю, я могу быть ошибочным.

Один из способов узнать, несколько раз запускать несколько тестов с одними и теми же данными с различным общим использованием системы и видеть, если он ведет себя существенно различно каждый раз. Другой способ - установить частоту процессора компьютера на какое-то статическое значение и протестировать его аналогичным образом.

IDEA Не было бы лучше измерить "время" в тиках?

EDIT 1 Благодаря @BeyelerStudios, теперь мы, наверняка, знаем, что вы не должны относиться к clock() на машинах Windows, потому что это не соответствует стандарту C98. Источник

Надеюсь, я помог, если я ошибаюсь, , пожалуйста, поправьте меня. Я студент, а не специалист HW.

Ответ 4

Quicksort имеет худшую временную сложность O (n ^ 2) и среднее значение O (n log n) для n записей в наборе данных. Более подробную информацию об анализе временной сложности можно найти здесь:

https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort

и здесь:

http://www.cise.ufl.edu/class/cot3100fa07/quicksort_analysis.pdf