Killer-sequence для Quick Sort

#cpp #алгоритм #сортировка

Имеется код для Quick-Sort, представленный ниже. Здесь пивотом будет являться серединный
элемент. А как построить пример, при котором данная сортировка будет работать за O(n^2)?
Нашёл лишь статью http://www.cs.dartmouth.edu/~doug/mdmspe.pdf, но не разобрался, так
как плохо владею английским. Можно ли ещё прикрепить пример кода, который будет генерировать
killer-sequence за O(n)?

void qsort(int *a,int l,int r)
   {
   if(l>=r)
   return;
    int x = a[(l+r)/2];
    int i = l,j = r;
    while(i<=j){
            while(a[i] < x) ++i;
        while(a[j] > x) --j;
        if(i<=j){
            swap(a[i],a[j]);
            ++i,--j;
        }
    }
    qsort(a,l,j);
    qsort(a,i,r);
}

    

Ответы

Ответ 1

Эх, тряхнём стариной :) Давайте-ка протрассируем индексы назад. Получается вот что:

void prepare_killer(int* a, int length)
{
    int origidx[length];
    for (int i = 0; i < length; i++)
        origidx[i] = i;

    // эмулируем прохождение qsort по плохому пути
    // r будет всё время константой
    int r = length - 1;

    // а l будет каждый раз увеличиваться на 1
    for (int l = 0; l < r; l++)
    {
        // так будет выбран pivot:
        int p = (l + r) / 2;

        // элементы с индексами l и p поменяются местами
        swap(origidx[l], origidx[p]);
    }

    // имея позиции, куда придут данные, можно теперь их расставить:
    for (int i = 0; i < length; i++)
        a[origidx[i]] = i + 1;
}


Для проверки напишем модифицированную версию qsort, которая будет проверять, что
данные отправляют её всё время по «плохому» пути: одно из двух подзаданий будет всегда
пустым.

bool qsort_check_failed = false;

void qsort_with_check(int *a, int l, int r)
{
    if (l >= r)
        return;
    int x = a[(l + r) / 2];
    int i = l, j = r;
    while (i <= j)
    {
        while (a[i] < x) ++i;
        while (a[j] > x) --j;
        if (i <= j)
        {
            swap(a[i], a[j]);
            ++i, --j;
        }
    }

    if (!(l >= j))
    {
        cout << "Mistake: have non-empty first subtask!" << endl;
        qsort_check_failed = true;
    }
    qsort_with_check(a, l, j);
    qsort_with_check(a, i, r);
}


Проверка здесь: http://ideone.com/a9L22p


Ответ 2

Самое простое решение твоей задачи, это уже отсортированный массив. В этом случае
у тебя quick sort будет давать худший результат.

int * array = new int[7];
for(int size = 0; size < 7; size++)
{
   (*array)[size] = size;
}


Это как вариант заполнения