Почему не стабильный порт?

Question

Я пытаюсь понять, почему heapsort не стабилен. Я гуглил это, но не нашел хорошего, интуитивного объяснения.

Я понимаю важность стабильной сортировки - она ​​позволяет нам сортировать по нескольким ключам, что может быть очень полезным (т. Е. Выполнять несколько сортировок, каждая из которых основана на различном ключе. Поскольку каждая сортировка сохраняет относительный порядок элементов, предыдущие сортировки могут складываться, чтобы дать окончательный список элементов, отсортированных по нескольким критериям). Тем не менее, почему бы и порт не сохранить это?

Спасибо за вашу помощь!

Answer 1

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

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

Answer 2

Нестабильный пример кучи

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

Вот 20a = 20b просто чтобы дифференцировать порядок мы представляем их как 20a а также 20b

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

7 8 11 12 20b 20a 21,

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

Answer 3

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

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

Отсюда:

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

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

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

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

Answer 4

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

Answer 5

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

Куча-сортировка включает в себя два этапа:

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

1. Перерывы при создании кучи

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

Теперь, если вы создадите из него кучу (мин-куча), ее представление в массиве будет {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) находятся не в том же порядке в массиве, отсортированном в куче, как они появляются во входных данных, и поэтому сортировка в куче не является стабильной!

Answer 6

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