Разумеется, просто здесь без лямбд.
А так, да - Ваш на первой полочке, хотя и с ограничением на диапазон.

Вот без ограничений на знак:

Два раза бегать по массиву - это чемпион?

Где сказано, что это "чемпион"?
Да и два раза пробежаться - это линейная сложность.

Два раза бегать или сортировать только натуральные числа - такая альтернатива?
Два раза бегать - это два раза. Сегодня в обед испытал удовольствие, забыл кошелек, обнаружил уже у кассы. К черту такую линейную сложность.

Вам хочется поспорить ни о чем? Предоставляю это увлекательное занятие в форме Вашего же само-диалога.

Здесь не о чем спорить. Констатация факта в форме вопроса.

Да тут не в лямбдах дело. Лямбда - это просто способ внедрить тело функции в выражение. Предыдущий пример без лямбды:



Предыдущий пример (120-й пост и этот выше) без ограничений на диапазон.


А сколько проходов по массиву совершается внутри функции сортировки? Или вы полагаете, что внутри sort() оно за один проход сортирует? И вообще, каков вес (в смысле затрат) прохода по массиву - сиречь, работа с памятью, - на фоне операций сортировки?

Логично, что того, кто пробежал дополнительный круг, вряд ли назовут чемпионом. Вот последнее ваше решение вполне может претендовать. Наряду с подобными на других языках - функция метода сравнения + сама библиотечная функция сортировки. Правда, ничего восхитительного в этом нет. Казуальное решение, оно и есть лучшее.
Количество проходов от функции сортировки зависит. Будем считать, используется быстрая. Сколько надо, столько и есть. Проход по массиву с инвертированием членов, удовлетворяющих условию, думаю, соизмерим с проходом со сравнением пары и обменом местами.

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

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


Так у TSerg по сути используется тот же метод. В моём примере выполняется подготовка ключей - массив элементов, каждый из которых связан с целевым сортируемым элементом, а затем собственно сортировка целевых элементов на основе значений ключей. У TSerg делается принципиально то же самое: сначала он готовит ключи, модифицируя элементы массива так, чтобы они могли выполнять роль ключей, затем сортировка по этим ключам. Ну, и финально вернуть значения элементов массива в исходному виду. Стандартные способы тут ничем не вырвутся вперёд.


Проход со сравнением пары и перестановкой местами - это что, "пузыёк"? "Пузырёк" - один из самых медленных (хотя и один из самых простых и незатратных) способов сортировки. Там совершается почти столько проходов по массиву, сколько в массиве элементов. На этом фоне лишний проход по массиву ничего не портит.

Нет, не "пузырек". Многие функции сортировки работают с парой элементов одинаково - сравнивают и, если нужно, переставляют местами. В том числе и быстрая сортировка.

quicksort (который Хоара), насколько мне известно, сравнивает с опорным элементом, а переставляет пару, в которую опорный не входит. Но это не важно. Там всё равно суммарно получается эн проходов по массиву, где эн зависит логарифмически от количества элементов. Да, гораздо лучше "пузырька", особенно, когда элементов много. Один лишний проход снаружи сортировки погоды не портит.

В сообщении 105 алгоритм быстрой сортировки показан. Пусть не так работает с парой, это, действительно не существенно.

Вообще-то, даже два: один до сортировки, один после. А можно без них, внутри функции сортировки все выполнить. Экономия очевидна.

Вообще-то, тут не просто сортировка, а сортировка с дополнительным условием (чёт-нечет), и это тоже надо как-то учитывать. Т.е. это выливается в некие дополнительные действия, и не факт, что они будут менее затратными, нежели один доп. проход по массиву.

Это все издержки ЯВУ. На любом асме эта проблема ничего не стоит. Просто считаем младший бит числа самым старшим и все.
Можете, чисто для удобства, "крутануть" циклически весь регистр вправо, перед сравнением...
Чет будет в начале, нечет - в конце отсортированного списка. Если нужен обратный порядок - инвертируем бит перед сравнением.
P.S. По-моему, основной вопрос для любого языка - кому должно быть "удобно": программисту или процессору?

Весело тут у Вас
Кто-то считает, что линейный пробег по массиву сравним по быстродействию с любой сортировкой, даже самой быстрой?
Таки я его разочарую.
Берем алгоритм из поста #121.
Делаем точные замеры ( на PC, Win7, Delphi 7, размерность времени в мкс) и что видим?
Ой!
- prepare и post - линейная пробежка по массиву;
- sort - сортировка массива методом QuickSort, можно еще Radix-сортировку применить, но не принципиально что-то изменится.




Сообщение отредактировал Gruffly - Apr 6 2017, 21:52