Это эквивалентно вставке сортировки?

Question

Скажем, у нас есть 0-индексированная последовательность S, возьмите S [0] и вставьте ее в место в S, где следующее значение больше, чем S [0], а предыдущее значение меньше, чем S [0].Формально S [i] следует поместить в такое место, где S [i-1] Работает так в списке:

Sorting [2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 5, 4, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 0, 6, 1, 7, 8, 10, 3, 9]
[0, 2, 4, 5, 6, 1, 7, 8, 10, 3, 9]
[0, 2, 4, 5, 1, 6, 7, 8, 10, 3, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 10, 3, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 3, 9, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Got [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Так как каждый раз, когда элемент вставляется в список до (n-1) числа в списке могут быть перемещены, и мы должны делать это n раз, когда алгоритм должен запускаться за O (n ^ 2) времени.

У меня была реализация Python, но я как-то ее не поместил.Я постараюсь написать это немного позже, но это довольно сложно реализовать.Любые идеи?

Реализация Python здесь: http://dpaste.com/hold/522232/. Он был написан busy_beaver с reddit.com, когда обсуждался здесь http://www.reddit.com/r/compsci/comments/ejaaz/is_this_equivalent_to_insertion_sort/

Answer 1

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

Предположим, что исходный список: v ₁ , v ₂ , ..., v _п . Затем, после i шагов алгоритма, я утверждаю, что список выглядит так:

ш _1,1 , ш _1,2 , ..., ш _{1, r (1)} , v _{σ (1)} , w _2,1 , ... w _{2, r (2)} , v _{σ (2)} , ш _3,1 ... ... ш _{i , r ( я )} , v _{σ ( i )} , ...

Где σ - отсортированная перестановка: v ₁ до v _i и w являются элементами v _j с j > i . Другими словами, v ₁ до v _i находятся в отсортированном порядке, возможно, чередуются с другими элементами , И более того, w _{j, k} ≤ v _j для каждого j и k . Таким образом, каждому из правильно отсортированных элементов предшествует (возможно, пустой) блок элементов, меньший или равный ему.

Ниже приведен алгоритм, в котором отсортированные элементы выделены жирным шрифтом, а предыдущие блоки элементов выделены курсивом (где они не пусты). Вы можете видеть, что каждый блок выделенных курсивом элементов меньше выделенного жирным шрифтом элемента.

[4, 8, 6, 1, 2, 7, 5, 0, 3, 9]
[ 4 , 8, 6, 1, 2, 7, 5, 0, 3, 9]
[ 4 , 6, 1, 2, 7, 5, 0, 3 , 8 , 9]
[ 4 , 1, 2 , 6 , 7, 5, 0, 3 , 8 , 9 ]
[ 1 , 4 , 2 , 6 , 7, 5, 0, 3 , 8 , 9]
[ 1 , 2 , 4 , 6 , 7, 5, 0, 3 , 8 , 9]
[ 1 , 2 , 4 , 6 , 5, 0, 3 , 7 , 8 , 9]
[ 1 , 2 , 4 , 5 , 6 , 0, 3 7 , 8 , 9]
[ 0 , 1 , 2 , 4 , 5 , 6 , 3 , 7 , 8 , 9]
[ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
[ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]

Если мое утверждение верно, то алгоритм сортируется, потому что после n шагов все v _i находятся в порядке, и нет оставшихся элементов для чередования. Но верно ли утверждение?

Что ж, давайте докажем это по индукции. Это, безусловно, верно, когда i = 0. Предположим, что это верно для i . Затем, когда мы запускаем ( i + 1) -й шаг, мы выбираем v _{i + 1} и перемещаем его в первую позицию где это подходит. Это, безусловно, проходит через все v _j с j ≤ i и v _j <<em> v _{i + 1} (так как они отсортированы по гипотезе, и каждому предшествует только меньший или равные элементы). Он не может пройти через любые v _j с j ≤ i и v _j ≥ v _{i + 1} , поскольку в блоке есть некоторая позиция перед v _j , где это будет соответствовать. Итак, v _{i + 1} заканчивается сортировкой по всем v _j с j ≤ i . Таким образом, он заканчивается где-то в блоке элементов перед следующей v _j , и, поскольку он оказывается в first такой позиции , состояние на блоках сохраняется. Что и требовалось доказать.

Тем не менее, я не виню вашего профессора за неправильную маркировку. Если вы собираетесь изобрести алгоритм, которого никто раньше не видел, до вас , чтобы доказать его правильность!

(алгоритму нужно имя, поэтому я предлагаю fitsort , потому что мы помещаем каждый элемент на первое место, где он подходит.)

Answer 2

Ваш алгоритм мне кажется очень отличным от сортировки вставок. В частности, очень легко доказать, что сортировка вставкой работает правильно (на каждом этапе первые, однако, многие элементы в массиве правильно сортируются; доказательство по индукции; выполнено), тогда как для вашего алгоритма это кажется гораздо сложнее доказать и неясно, какое именно свойство частичной сортировки он гарантирует в любой данный момент своей обработки.

Точно так же очень легко доказать, что сортировка вставкой всегда делает не более n шагов (где под «шагом» я подразумеваю размещение одного элемента в нужном месте), тогда как, если я поняла ваш алгоритм правильно, он не продвигает указатель «какой элемент к процессу следующий», если он просто перемещает элемент вправо (или, иначе говоря, иногда ему может потребоваться обработать элемент более одного раза), так что это не настолько ясно, что ваш алгоритм действительно занимает O (n ^ 2) время в худшем случае.

Answer 3

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

Ваш алгоритм делает это, но иногда он также делает дополнительный шаг перемещения элемента по указателю напрямо без продвижения указателя.Это делает алгоритм в целом не сортировкой вставки, хотя вы можете назвать ее модифицированной сортировкой вставки из-за сходства.

Этот алгоритм работает в среднем за O ( n ²), каксортировка вставки (также как сортировка пузыря).Наилучшим случаем для сортировки вставкой является O ( n ) в уже отсортированном списке, для этого алгоритма это O ( n ), но для списка с обратной сортировкой, поскольку вы находитеправильная позиция для каждого элемента в одном сравнении (но только если вы оставляете первый, самый большой элемент на месте в начале, когда не можете найти для него подходящую позицию).

Answer 4

Мне трудно понять, что это сортировка вставкой.Используя сортировку вставкой, на каждой итерации еще один элемент будет правильно размещен в массиве.В вашем решении я не вижу, чтобы элемент "полностью сортировался" при каждой итерации.

Алгоритм сортировки вставки начинается:

1. let pos = 0
2. , еслиpos == arraysize, затем возвращает
3. найти наименьший элемент в оставшемся массиве из pos и поменять его на элемент в позиции pos
4. pos ++
5. перейти к 2

Answer 5

Многие профессора печально известны наличием ошибки "это не тот ответ, который я ищу". Даже если это правильно, они скажут, что это не соответствует их критериям.

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

Что он может сказать, так это то, что вы, по сути, «вытаскиваете» значение и «отбрасываете его обратно» в правильное место. Ваш проф, вероятно, искал "обмен значения вверх (или вниз), пока вы не нашли его правильное местоположение."

У них одинаковый результат, но они разные в реализации. Обмен будет быстрее, но не так значительно.