Комментарии 10
В вашем варианте можно попробовать в левом отсортированном подмассиве применить бинарный поиск, чтобы найти место вставки нового элемента не перебирая все элементы, а затем просто сдвинуть все элементы от этого места вправо и на освободившееся место поставить новый элемент. Таким образом водно уменьшить число сравнений элементов.
Близкие по теме статьи, может кто не читал:
https://habr.com/en/post/204600/
https://habr.com/en/post/204968/
Общий смысл - модификации общеизвестных и/или тривиальных алгоритмов сортировки.
Ваша последняя сортировка — это сортировка вставками aka InsertionSort. На частично сортированных массивах оно лучше пузырька.
Cocktail sort слился пузырьку, потому что "выталкивание легких элеменов" ни чем не лучше "выталкивания тяжелых" как в обычном пузырьке. Это хождение по массиву туда-обратно оказывается чуть менее дружественно к кешу и поэтому слегка проигрывает. Но если вы проведете бенчмарки правильно (что весьма сложно, на самом деле — надо гнать много раз, прогревать кеш, выбрасывать аутлаеров), то наверняка найдете что разница практически незаметна.
И разница по количеству проходов объясняется вот этим: если в массиве "aabaaa" вытащить наверх максимальный элемент, то он станет отсортирован за один проход. Если же вытаскивать вниз минимальный элемент, то понадобятся все 5 проходов. В зависмости от того, чего там у вас в массиве будет больше, всегда выталкивать максимальные элементы может быть оптимальнее чем чередовать минимальный и максимальный.
Ваша последняя сортировка — это сортировка вставками aka InsertionSort.
У Кнута сортировка вставками идёт в описании отдельно от сортировки обменами. Пузырьковая и её модификации обменивают пары, а сортировка вставками находит позицию элемента, то есть это реализация одно- или двунаправленного списка. В моем случае это модификация шейкерной сортировки (или развитие её идеи).
Мне такой способ сортировки показался интересным тем что он работает за один проход от начала массива к концу, то есть он может получать входные данные и сортировать их не дожидаясь поступления следующей порции.
Это хождение по массиву туда-обратно оказывается чуть менее дружественно к кешу и поэтому слегка проигрывает
Тогда бы это не работало бы и на других файлах, но Cocktail Sort очевидно более быстрый чем пузырёк по объективным причинам и я как раз пытаюсь понять бутылочное горлышко именно того набора байт.
максимальные элементы может быть оптимальнее чем чередовать минимальный и максимальный
мысль понял, как дойдут руки нужно будет проверить на немного измененных паттернах.
В моем случае это модификация шейкерной сортировки (или развитие её идеи).
Но получилась сортировка в ставками. Только у вас не список, а массив. Поэтому вам надо найти место для элемента, сдвинуть все правее этого места на одну позицию и потом воткнуть элемент на это место. Вы же ставите новый элемент в конец массива и обмениваете пары, пока он не станет на свое место. Получаете тоже самое, только чуть медленее (можно не гнать цикл как только обмены завершились, можно не делать обмены, а сдвиг и потом в конце поставить новый элемент на пустое место).
Тогда бы это не работало бы и на других файлах, но Cocktail Sort очевидно более быстрый чем пузырёк
нет тут объективных причин. Оно быстрее на каких-то тестах. На каких-то оно медленее. В среднем не лучше — не хуже.
Бутылочное горлышко — там больше максимальных элементов, чем минимальных во всем массиве, или потом на каком-то этапе сортировки.
Но получилась сортировка в ставками. Только у вас не список, а массив
Тогда и пузырёк тоже сортировка вставками? Пока не убедили, звучит просто как способ взгляда на происходящее с совпадающими (похожими) элементами в работе.
Бутылочное горлышко — там больше максимальных элементов, чем минимальных во всем массиве
Там 2 символа 50/50 распределены рандомно, нет доминирования того или иного значения.
Тогда и пузырёк тоже сортировка вставками?
Нет, потому что в процессе работы пузырька не поддерживается инвариант, что после i-ой итерации, первые i элементов — отсортированные элементы исходного массива. А в сортировке вставками и вашей "камешек в болоте" — поддерживается.
Там 2 символа 50/50 распределены рандомно, нет доминирования того или иного значения.
Зависит и от расположения элементов. Так "abaaabbb" при поднятии вверх за один проход все отсортируется, а при опускании вниз — за 3.
Модификации сортировки пузырьком