Имеется код для 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
Комментариев нет:
Отправить комментарий