Страницы

Поиск по вопросам

вторник, 4 июня 2019 г.

Killer-sequence для Quick Sort

Имеется код для 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); }


Ответ

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

Комментариев нет:

Отправить комментарий