Почему пирамидальная сортировка не стабильна?

Окончательная последовательность результатов heapsort получается при удалении элементов из созданной кучи строго по размеру (на основе ключевого поля).

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

Пример нестабильной сортировки кучей

Рассмотрим массив 21 20a 20b 12 11 8 7 (уже в формате max-heap)

здесь 20a = 20b просто чтобы различать порядок, мы представляем их как 20a и 20b

В то время как heapsort сначала удаляется 21 и помещается в последний индекс, затем 20a удаляется и помещается в предпоследний индекс и 20b в предпоследний два индекса, поэтому после сортировки кучей массив выглядит так

7 8 11 12 20b 20a 21.

Он не сохраняет порядок элементов и, следовательно, не может быть стабильным

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

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

Из здесь:

При сортировке (в порядке возрастания) heapsort сначала выбирает самый большой элемент и помещает его последним в списке. Таким образом, элемент, выбранный первым, остается последним, а элемент, выбранный вторым, остается предпоследним элементом в отсортированном списке.

Опять же, процедура Build-Max-Heap работает таким образом, что сохраняет порядок одного и того же значения (например: 3a, 3b) при построении дерева кучи. Для извлечения максимального элемента он также работает из корня и пытается сохранить структуру дерева (кроме изменения для Heapify).

Итак, что происходит, для элементов с одинаковым значением [3a,3b] heapsort выбирает 3a перед 3b, но помещает 3a справа от 3b. Итак, поскольку список отсортирован в порядке возрастания, мы получаем 3b перед 3a в списке.

Если вы попробуете пирамидальную сортировку с (3a, 3b, 3b), вы сможете визуализировать ситуацию.

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

Сортировка кучей включает два этапа:

• Создание кучи
• Удаление и добавление корневого элемента из дерева кучи в новый массив, который будет отсортирован по порядку

<сильный>1. Разрывы порядка во время создания кучи

Допустим, входной массив равен {1, 5, 2, 3, 2, 6, 2}, и чтобы увидеть порядок двойки, скажем, что это 2a, 2b и 2c, поэтому массив будет {1, 5, 2а, 3, 2б, 6, 2в}

Теперь, если вы создадите из него кучу (здесь min-heap), представление массива будет {1, 2b, 2a, 3, 5, 6, 2c}, где порядок 2a и 2b уже изменился.

<сильный>2. Порядок прерывается при удалении корневого элемента

Теперь, когда нам нужно удалить корневой элемент (в нашем случае 1) из кучи, чтобы поместить его в другой новый массив, мы меняем его последней позицией и удаляем оттуда, следовательно, меняем кучу на {2c, 2b, 2a, 3, 5, 6}. Мы повторяем то же самое, и на этот раз мы удалим «2c» из кучи и поместим его в конец массива, где мы поместили «1».

Когда мы закончим повторять этот шаг, пока куча не станет пустой, и каждый элемент будет перенесен в новый массив, новый массив (отсортированный) будет выглядеть как {1, 2c, 2b, 2a, 3, 5, 6}.

Входные данные для сортировки кучей: {1, 5, 2a, 3, 2b, 6, 2c} --> Выходные данные: {1, 2c, 2b, 2a, 3 , 5, 6}

Отсюда мы видим, что повторяющиеся элементы (двойки) не находятся в том же порядке в массиве, отсортированном кучей, как они появляются во входных данных, и, следовательно, сортировка кучей не является стабильной!

Я знаю, что это поздние ответы, но я добавлю здесь свои 2 цента. Рассмотрим простой массив из 3 целых чисел. 2,2,2 теперь, если вы создадите максимальную кучу с помощью функции построения максимальной кучи, вы обнаружите, что массив, хранящий входные данные, не изменился, поскольку он уже находится в форме максимальной кучи. Теперь, когда мы помещаем корень дерева в конец массива в первой итерации сортировки кучей, стабильность массива уже исчезла. Итак, у вас есть простой пример нестабильности сортировки кучи.

Предположим, возьмите массив размера n (произвольное значение), и если в куче есть два последовательных элемента (предположим, 15), и если их родительские индексы имеют значения, такие как 4 и 20 (это фактический порядок (....4,20 ,.....,15,15.....). Относительный порядок 4 и 1-го 15 остается таким же, но поскольку 20> 15, 2-й 15 идет вперед (своп), как определено в алгоритме сортировки кучи, относительный порядок исчез.