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

Ответ 1

В основном в selection sort, swap, который происходит в конце каждого раунда, может изменить относительный порядок элементов, имеющих одинаковое значение.

например, предположим, что вы отсортировали 4 2 3 4 1 с помощью selection sort.

первый "раунд" будет проходить через каждый элемент, ища минимальный элемент. он найдет, что 1 является минимальным элементом. то он поменяет 1 на первое место. это приведет к тому, что 4 в первом пятне войдут в последнее место: 1 2 3 4 4

теперь изменился относительный порядок 4. "первый" 4 в исходном списке был перемещен в пятно после другого.

помните, что определение стабильного состоит в том, что

сохраняется относительный порядок элементов с одинаковым значением.

Ну, selection sort работает, найдя "наименьшее" значение в наборе значений, затем замените его первым значением:

код:

2, 3, 1, 1 # scan 0 to n и найдите "наименьшее" значение

1, 3, 2, 1 # замените "наименьшим" на элемент 0.

1, 3, 2, 1 # scan 1 to n и найдите "наименьшее" значение

1, 1, 2, 3 # замените "наименее" на элемент 1.

... и так далее, пока он не будет отсортирован.

Чтобы сделать это стабильным, вместо того, чтобы менять значения, вставьте вместо этого "наименьшее" значение:

код:

2, 3, 1, 1 # scan 0 to n и найдите "наименьшее" значение

1, 2, 3, 1 # вставить "наименьший" в pos 0, отбросив другие элементы.

1, 3, 2, 1 # scan 1 to n и найдите "наименьшее" значение

1, 1, 2, 3 # вставить "наименьший" в позицию 1, отбросив другие элементы.

... и так далее, пока он не будет отсортирован.

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

Ответ 2

В общем случае - вы не правы. Сортировка сортировки нестабильная. Это вытекает из этого определения. Таким образом, вы, очевидно, путаетесь с одним обычным случаем.

Он может быть стабильным - обычно, только с связанными списками. Для этого (классический способ, O (1) память) - вместо свопов минимальный элемент должен быть связан с несортированной частью, что делает весь алгоритм стабильным. И в этом и заключается разница в "реализации", которая, очевидно, будет обеспечивать стабильность только в этом случае из-за специфики структуры данных. Это не имеет ничего общего с обычным случаем, когда сортировка сортировки нестабильна

Ответ 3

Скажем, у меня есть этот массив:

A = {3, 3, 1}

Начиная с позиции 0, сортировка сортировки будет искать минимальное значение и сменять текущий элемент с минимумом. Для A мы поменяем первый 3 на 1 и ничего не делаем на втором шаге.

Это нестабильно, поскольку первый 3 должен был быть до второго. Если вы используете связанный список вместо массива и вставляете элемент в правильную позицию вместо замены, выбор сортировки стабилен.

Ответ 4

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