улучшение алгоритма быстрой сортировки, если больше дублирующих ключей
Я читаю алгоритм быстрой сортировки в книге Роберта Седвика Алгоритмы и структуры данных, часть 1-4.
template <class item>
static void quicksort(item [] a, int l, int r)
{
if(r <= l) return;
int i = partition(a,l,r);
quicksort(a, l, i-1);
quicksort(a, i+1, r);
}
template <class item>
int partition(item a[], int l, int r)
{
int i = l-1; j = r; item v = a[r];
for(;;) {
while( a[++i] < v );
while( v < a[--j] )
if( j == l )
break;
if( i >= j)
break; // pointer crossing.
exch(a[i], a[j]);
}
exch(a[i], a[r]);
return i;
}
Книга имеет следующий текст по вышеуказанному алгоритму.
Когда дубликаты ключей присутствуют в файле, пересечение указателя
тонкий. мы могли бы немного улучшить процесс разделения
прекратить сканирование, когда я < j, а затем с помощью j, а не i-1,
разграничить правый конец левого подфайла для первого рекурсивного
вызов. Позволить циклу повторяться еще раз в этом случае
улучшение, потому что когда-либо циклы сканирования заканчиваются на j
и я ссылаюсь на один и тот же элемент, мы в конечном итоге с двумя элементами в
их конечные позиции: элемент, который остановил оба сканирования, которые должны
следовательно, быть равным элементу разбиения, а разделение
сам элемент. Это изменение, вероятно, стоит сделать, потому что в этом
В конкретном случае программа оставляет запись с ключом, равным
ключ разделения в [r], и это делает первый раздел в
вызовите quick-sort (a, i + 1, r) вырожденным, потому что его самый правый ключ
его наименьшее.
Мои вопросы
- Как мы можем изменить вышеуказанную программу с описанием ниже? Я испытываю затруднения в изменении его, чтобы понять текст.
- Почему вышеупомянутый алгоритм быстрой сортировки не работает эффективно, если присутствует больше дублирующих ключей.
- Как вышеописанная модификация улучшится, если будет больше ключей дублирования?
- Что автор подразумевает под «первым разделом в вызове quick-sort (a, i + 1, r) вырождается, потому что его самый правый ключ — его наименьший». ? Что значит
автор имел ввиду под вырождением здесь?
Спасибо за ваше время и помощь.
Решение
>> Почему вышеупомянутый алгоритм быстрой сортировки не работает эффективно, если присутствует больше дублирующих ключей?
Это становится неэффективным, потому что ваше критическое состояние: if(i >= j) break;
так, как вы сканируете с обеих сторон i а также j, Вполне возможно, что вы нарушаете, когда я == j вместо того, чтобы позволить i превосходить j,
Какие плохой может случиться, когда мы сломаем i==j когда много дубликатов ключей присутствуют ?
Когда вы перерыв на i==j; с первого цикла в то время как вы должны были a[i] >= v и со второго цикла пока a[j] <=v но так как мы рассматриваем «перерыв» для: i==j так, a[i] = a[j] = v то есть a[i] такой же как v, ваш поворотный элемент.
В таком сценарии ваш самый внешний exch(a[i], a[r]); будет просто обменивать сводную стоимость на себя.
Следовательно, в вашем следующем рекурсивном вызове quicksort(a, i+1, r); для правой половины массива у вас будет минимальный элемент, расположенный в самом правом конце (ваша стратегия выбора сводной точки проста, item v = a[r]; ) и мы все знаем, что для QuickSort плохо выбирать элемент разворота, который составляет минимум или максимум массива. Следовательно, ваш последующий рекурсивный вызов для правой половины будет вырожденный.
Именно поэтому автор советует не разбиваться на я == J но поймай их как раз перед тем, как это произойдет.
>> Что автор имеет в виду под вырождением здесь?
Вырождение здесь означает, что дерево рекурсии становится искаженным, то есть последующие проблемы не генерируются практически одинакового размера.
Вы делите проблему размера N в нечто вроде проблемы размера N-1 а также 1 вместо того, чтобы что-то более сбалансированное, как деление этого на проблемы размера N/2 а также N/2,
>> Как мы можем изменить вышеуказанную программу с описанием ниже?
Мы могли бы реализовать это следующим образом:
int partition(int A[], int l, int r){
int i=l-1, j=r, v = A[r];
for(;;){
while(A[++i] < v);
while(A[--j] > v)
if(j == l)
break;
if(i>=j)
break;
swap(A[i], A[j]);
}
if(i == j){// case when we stopped at the pivot element.
j = j+1;//backtrack j 1 step.
if(j <= r)
swap(A[j], A[r]);
return j;// partition the subsequent problems around j now.
}
swap(A[i], A[r]);
return i;
}
>> Как выше модификация улучшается, если присутствует больше ключей дублирования?
Это повышает производительность, позволяя вам НЕ генерировать очевидный сценарий вырожденного случая.
Другие решения
Других решений пока нет …