Здравствуйте, vdimas, Вы писали:

V>>>Линейный он лишь для случая одновременного поиска и сдвига элементов массива.
V>>>В этом случае он представляет из себя разновидность пузырьковой сортировки.
EP>>Это не разновидность пузырьковой сортировки.
V>Извини, но сравнение и обмен строго с соседним элементом — это характеристика сортировок из семейства пузырьковой.
V>Не помнишь, почему сортировка названа "пузырьковой"?

Я же говорю, что при повороте swap не нужен — это точно не пузёрок.

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

Тебе сказали что описанный тобой вариант это shaker sort. Утверждений того что пузырьковая только одна — не было.

V>Аналогично по сортировкам слиянием — мы их штук пять-шесть проходили (если склероз не изменяет). А на визуализации я вижу лишь один из вариантов.

Естественно там далеко не все разновидности. Сортировку слияниям кстати хорошо разбирает Степанов в своей книге Elements of Programming.

V>>>Если же сначала найти необходимую позицию, а затем сдвинуть все необходимые элементы за раз, то так может оказаться эффективней.
EP>>Может, не спорю что есть вариант с двоичным поиском, и что у него есть область применения. Я говорю что обычно он линейный.
V>"Обычно" — это из-за std::sort, что ле? ))
V>Там, как раз, всё очень необычно, а весьма специфично для специфичного этапа сортировки.

Обычно — это значит типичный код реализации.

EP>>Там вообще говоря swap использовать не выгодно — там нет необходимости менять каждый соседний элемент между собой. Оптимальнее переместить текущий элемент в temp, все остальные переместить вправо, а потом переместить temp в левый край. Это операция ЕМНИП rotate_by_one.
V>Об этом и речь, чтобы не производить на каждом шаге сравнение с перестановкой.

Не, как раз из-за того что бывает выгодней производить и сравнение и перемещения одновременно — то эти два этапа сливают. А выгодно потому что условных операций / ветвей меньше — достаточно дать гарантию что в самом начале есть guard element, тогда на каждой итерации достаточно одного вызова предиката сравнения, без проверки выхода за пределы массива.

V>Но искать-то выгодней двоично, а не линейно, для массива из более 16-ти элементов на современных машинах!

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

V>>>Похоже, что в тех реализациях, что ты представляешь — пузырьковая сортировка отработает N! (факториал) раз независимо от исходных данных. ))
EP>>Очень смешно. Пузырьковая сортировка квадратична в худщем случае.
V>Вот как раз не смешно. Самый простой вариант пузырьковой сортировки отрабатывает фиксированное кол-во раз, независимо от содержимого массива.

С квадратичной сложностью, а не факториалом

V>Я же тебе намекаю уже многократно,

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

V>что пузырьковая сортировка — это целое семейство алгоритмов.

А теперь прочитай ещё раз мой ответ на эту тему:

V>>Не будет. Простой пузырёк протягивает флаг наличия несортированных элементов, а модифицированный вместо этого протягивает границы несортированной области (индекс начала и индекс конца) и работает в оба направления туда-сюда, сужая к центру (обычно) несортированную область.
EP>Даже с этими модификациями получается больше сравнений — дойдёт до 6, сделает swap, дойдёт до конца, а потом ещё сделает проход от 5 до 1.

EP>>>>Покажи реализацию без лишнего прохода, или хотя бы дай ссылку на код.
V>>>Стандартная и есть без лишнего прохода.
EP>>Код в студию, иначе наш спор не разрешится.
V>В западной литературе шейкерную выделяют в отдельный вид сортировки, нас же её давали как разновидность пузырьковой.

Я же тебе говорю, возьми хоть шейкерную — у неё всё равно в этом случае сравнений будет больше чем вставками (вариант с линейным поиском обратно).

V>Более того, визуализация шейкерной сортировки на видео — ошибочна, ы-ы-ы.

Какое видео?

V>В шейкерной необходимо запоминать первое и последнее место обмена, т.е. должно происходить сужение диапазона.

Да, но только самое правое место обмена запоминается/важно при проходе направо, а левое — при проходе налево.

V>На прямом проходе обнаруживается единственный обмен 5 с 6, на обратном проходе должно быть одно сравнение 5 с 4 и сразу выход.

Нет там выхода сразу после сравнения 4 vs 5. У пузырьковой/шейкера нет break внутри цикла. Вместо пятёрки там мог быть ноль: 1 2 3 4 6 0 7 8 9.

Да даже если допустить что там выход после 4 vs 5 — это всё равно опровергает твой тезис о том что вставками здесь дороже, так как там столько же сравнений.

V>Код тривиальный, писать не буду. ))

Можешь скопировать откуда-нибудь, хоть псевдокод. Только не тяни, не надо растягивать это на десятки сообщений