Почему бы не использовать сортировку кучи всегда [дубликат]

Question

Почему бы не использовать сортировку кучи всегда [дубликат]

этот вопрос уже есть ответ здесь:

Quicksort против heapsort

11 ответов

Превосходство над быстрой сортировки кучи сортировки

5 ответов

The Куча Вроде алгоритм сортировки кажется имеют наихудшую сложность o(nlogn) и используют пространство O (1) для операции сортировки.

Это выглядит лучше, чем большинство алгоритмов сортировки. Тогда почему бы не использовать сортировку кучи всегда в качестве алгоритма сортировки (и почему люди используют механизмы сортировки, такие как сортировка слиянием или быстрая сортировка)?

кроме того, я видел, как люди используют термин "нестабильность" с сортировкой кучи. Что это значит?

672 5

algorithm sorting heapsort

5 ответов:

Comments

Ничего не найдено.

Jim Mischel · Accepted Answer · 2011-11-29 16:09:57

стабильная сортировка поддерживает относительный порядок элементов, имеющих один и тот же ключ. Например, представьте, что ваш набор данных содержит записи с идентификатором сотрудника и именем. Начальный порядок:
1, Jim
2, George
3, Jim
4, Sally
5, George
вы хотите сортировать по имени. Стабильная сортировка расположит элементы в следующем порядке:
2, George
5, George
1, Jim
3, Jim
4, Sally
обратите внимание, что повторяющиеся записи для "George" находятся в том же относительном порядке, что и в исходном списке. То же самое с двумя записями "Джима".

неустойчивая сортировка может организовать элементы следующим образом:
5, George
2, George
1, Jim
3, Jim
4, Sally
Heapsort не является стабильным, потому что операции над кучей могут изменить относительный порядок равных элементов. Не все реализации алгоритма быстрой сортировки "стабильный". Это зависит от того, как вы реализуете перегородки.

хотя Heapsort имеет худший случай сложности O(n log(n)), это не рассказать всю историю. В реальной реализации существуют постоянные факторы, которые теоретический анализ не учитывает. В случай Heapsort против Quicksort, оказывается, что есть способы (медиана 5, например), чтобы сделать худшие случаи Quicksort очень редкими. Кроме того, поддержание кучи не является бесплатным.

учитывая массив с нормальным распределением, Quicksort и Heapsort будут работать в O(n log(n)). Но Quicksort будет работать быстрее, потому что его постоянные факторы меньше, чем постоянные факторы для Heapsort. Проще говоря, секционирование выполняется быстрее, чем поддержание кучи.

Jean Logeart · Accepted Answer · 2017-05-23 15:34:45

The Куча Вроде имеет худший случай сложности O(n log(n)). Однако эмпирические исследования показывают, что в целом Быстрая Сортировка (и другие алгоритмы сортировки) значительно быстрее, чем сортировка кучи, хотя его худший случай сложности O(n²) : http://www.cs.auckland.ac.nz / ~jmor159/PLDS210/qsort3.html

С быстрая сортировка статьи на Википедии:

самый прямой конкурент quicksort пирамидальная сортировка. Худшее время работы Heapsort всегда O (N log n). Но предполагается, что heapsort в среднем несколько медленнее, чем стандартная быстрая сортировка на месте. Это до сих пор обсуждается и в исследованиях, причем некоторые публикации указывают на обратное.[13] [14] Introsort-это вариант quicksort, который переключается на heapsort, когда обнаруживается плохой случай, чтобы избежать наихудшего времени работы quicksort. Если заранее известно, что heapsort будет необходим, использование его напрямую будет быстрее, чем ждем introsort, чтобы переключиться на него.

однако, быстрая сортировка не должна использоваться в приложениях, которые требуют гарантию времени отклика!

источник на Stackoverflow:Quicksort против heapsort

Karoly Horvath · Accepted Answer · 2011-11-29 15:25:20

нет серебряной пули...

просто чтобы упомянуть еще один аргумент, который я еще не видел здесь:

Если ваш набор данных очень большая и не влезает в память, то сортировка слиянием работает как шарм. Он часто используется в кластерах, где набор данных может охватывать сотни машин.

Kane · Accepted Answer · 2011-11-29 15:59:34

стабильные алгоритмы сортировки поддерживают относительный порядок записей с равными ключами

некоторые приложения, такие как наличие такой стабильности, большинство из них не заботятся, например, Google-ваш друг.

Что касается вашего утверждения о том, что "люди используют механизмы сортировки, такие как сортировка слиянием или быстрая сортировка", я бы поспорил, что большинство людей используют все, что встроено в их язык, и не думают об алгоритме сортировки так много. Те, что катят свои, наверное, не слышали типа кучи (последнее-личный опыт).

последняя и самая большая причина заключается в том, что не все будут хотеть отсортированную кучу. Некоторые люди хотят отсортировать список. Если босс среднего программиста Джо говорит: "сортируйте этот список", а Джо говорит: "Вот эта структура данных кучи, о которой вы никогда не слышали, босс!", Следующий обзор производительности Джо не будет таким большим.

mcdowella · Accepted Answer · 2011-11-29 21:02:14

когда я работал в течение короткого времени на тандемных нон-стоп компьютерах в середине 80-х годов, я отметил, что процедура сортировки системы в ядре была HeapSort, именно потому, что она давала гарантированную производительность NlogN. Я не знаю никого, у кого были бы причины использовать его, поэтому я не знаю, как он работал на практике. Мне нравится heapsort, но, как и недостатки, отмеченные выше, я слышал, что он плохо использует современные воспоминания, потому что он делает доступ к памяти повсюду, тогда как quicksort и даже небольшие виды radix в конечном итоге смешивают относительно небольшое количество потоков последовательных операций чтения и записи - поэтому кэши более эффективны.