Почему быстрая сортировка исключает средний элемент, а слияние включает его? - PullRequest
Новая
       51

Почему быстрая сортировка исключает средний элемент, а слияние включает его?

0 голосов
/ 28 октября 2018

Я рассматривал реализацию быстрой сортировки (из CLRS 3rd Edition).Я обнаружил, что рекурсивное деление массива идет от низкого индекса к середине-1, а затем снова от среднего + 1 к максимуму.

QUICKSORT(A,p,r)
1 if(p < r)
2        q = PARTITION(A,p,r)
3        QUICKSORT(A,p,q-1)
4        QUICKSORT(A,q+1,r)

А реализация сортировки слиянием задается следующим образом: 

MERGE-SORT(A,p,r)
1 if(p < r)
2       q = (p+r)/2 (floor)
3       MERGE-SORT(A,p,q)
4       MERGE-SORT(A,q+1,r)
5       MERGE(A,p,q,r)

Поскольку оба они используют одинаковую стратегию деления, почему быстрая сортировка игнорирует средние элементыпри переходе от 0 к q-1 и q+1 к r не включается q, в то время как сортировка слиянием имеет?

Ответы [ 2 ]

0 голосов
/ 28 октября 2018

Быстрая сортировка помещает все элементы, меньшие, чем шарнир, с одной стороны, и все элементы, большие с другой стороны.После этого шага мы знаем, что окончательная позиция центра будет между этими двумя, и именно там мы ее поместим, поэтому нам не нужно смотреть на нее снова.

Таким образом, мы можем исключить элемент центра врекурсивные вызовы.

Mergesort просто выбирает среднюю позицию и ничего не делает с этим элементом до тех пор, пока позже.Нет никакой гарантии, что элемент в этой позиции уже будет в нужном месте, поэтому нам нужно снова посмотреть на этот элемент позже.

Таким образом, мы должны включить средний элемент в рекурсивные вызовы.

0 голосов
/ 28 октября 2018

Оба метода используют стратегию разделения, но по-разному

Mergesort (наиболее распространенная реализация) рекурсивно делит массив на части равного (если возможно) размера, средние индексы - фиксированные позиции (для данной длины массива).Вызовы Recurive полностью обрабатывают левую и правую части массива.

Быстрая сортировка partition Подпрограмма помещает элемент поворота в нужное (конечное) положение (в большинстве случаев индекс поворота не является средним).Больше нет необходимости обрабатывать этот элемент, а рекурсивные вызовы обрабатывают части до и после этого элемента.

...