Насколько хороша эта оптимизация для heapsort, разделив на 2 части - PullRequest
Новая
       12

Насколько хороша эта оптимизация для heapsort, разделив на 2 части

0 голосов
/ 13 ноября 2018

Я думал о быстрой сортировке, не находящей точную среднюю точку для точки разворота. Любые попытки найти точную среднюю точку, так как поворот замедляет быструю сортировку и не стоит этого.

Так можно ли добиться этого с помощью heapsort и стоит ли это того? Я выбрал heapsort, потому что он может найти следующий максимум / мин за логарифмическое время.

Если мы разделим массив heapsort на 2 части. 

1) In the left half, we find max heap. (n/2-1 comparisons)
2) In the right half, we find min heap. (n/2-1 comparisons)
3) While 
     (max in left half is < min in right half){
      -- swap max in left half with min in right half
      -- heapify the swapped elements in respective halves 
      (i.e. find next max in left half 
       & find next min in right half).      
       } 
    end while loop.

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

1) Мы можем завершить оставшуюся кучу в каждой половине (log n / 2 для оставшихся элементов максимум). Таким образом, любой элемент, находящийся в правильной половине, будет в большинстве случаев создавать кучу log n / 2, а не log n.

Это одна оптимизация

Другая оптимизация может быть

2) Мы можем рекурсивно применить это в каждой непересекающейся половине (разделяй и соглашайся). 3) Также мы можем исключить центральные 2 элемента из последующих непересекающихся разбиений, потому что они уже находятся в своем неизменном расположении например 1-16 (n-1 сравнений, чтобы найти максимум / мин) у нас есть 1-7 и 8-16 раздел на первом этапе второй шаг может иметь 4 раздела (7 и 8 находятся в инвариантном местоположении) (так что n-3 сравнения, чтобы найти максимум / мин) 3 шага могут иметь 8 разделов еще 4 элемента в инвариантном местоположении. Так что n-7 сравнений, чтобы найти максимум / мин в каждом разделе.

Я пытаюсь это реализовать, Но я хотел бы знать, видит ли кто-нибудь теоретическое преимущество в этом подходе или он не годится.

Для уже отсортированных я вижу, что не будет никакого обмена, и мы просто продолжаем находить макс / мин в последующих половинах Для сортировки по убыванию мы видим, что все элементы меняются местами и разделяются на части без возможности разделения и совпадения. Так что это будет так же хорошо или так же плохо, как обычный heapsort. это может быть худшим случаем.

Для всех остальных мы увидим любое улучшение после макс / мин перестановок.

1 Ответ

0 голосов
/ 13 ноября 2018

У вас есть проход O (n), который создает две кучи. Тогда в худшем случае у вас есть (n/2)*(log n/2) замен в каждой из двух куч. На данный момент вы уже выполнили n*log(n/2) операций и даже не начали сортировку. Для завершения сортировки вам потребуется еще n*log(n/2) операций.

Сравните это с heapsort, который имеет проход O (n), который создает одну кучу, а затем n * log (n) операций для завершения сортировки массива.

Я не вижу особого преимущества в построении двух куч размера n / 2, а не одной кучи размера n. В лучшем случае у вас есть более сложный код, который имеет такую ​​же или худшую асимптотическую сложность и вряд ли даст вам реальное увеличение производительности.

...