Я тестил массивы, сгенерированные случайно, до 10 000 элементов, но тест был поставлен таким образом, что каждый массив нужно отсортировать 1 000 раз - так я сглаживал всякие случайные факторы
Из ограничений - разница между минимальным и максимальным значениями. Но даже так алгоритм сохраняет логарифмическую асимптоту
Изначально предполагалось что числа должны быть только целые, но это ограничение можно обойти, если все числа привести к целым - помножить на pow(10,x) где x есть количество разрядов после запятой
Позже я пришёл к тому, что это некая вариация сортировки подсчётом O(n+k), но поведение асимптоты другое O(log(n)+k) или O(log(n)+n^k) я ещё точно с этим не определился, но суть в том что логарифм остаётся на любых интервалах данных. И такого я нигде не нашёл, только в своих замерах
Ещё одно ограничение - динамические массивы и отрицательные индексы, так что этот алгоритм не есть универсальный, или нужно пилить дополнительные обёртки
Так как статья относительно свежая, и комментарии всего пол месяца ... Оставлю и свой комент
Я тут на днях изобрёл велосипед, который как оказалось ещё и сортировать массивы умеет, хотя изначально у меня стояли другие задачи
Едет этот велосипед в несколько раз быстрее "быстрой сортировки"
Сейчас я гоняю массированные тесты этого алгоритма, и в сравнение взял ещё две сортировки, помимо быстрой
К чему я всё это пишу: полез гуглить, и сходу не нашёл ничего, но чуть позже почитал немного про сортировку Хэна, и по описанию на вики - очень похоже, хотя по детальному изучению статей - сортировка Хэна какая-то "очень сложная", тут тебе и деревья, и хэши какие-то, описание с матаном - в общем действительно рокет-сайнс какой-то
А у меня всего два цикла верхнего уровня, и один вложенный как вспомогательный - для группировки дубликатов
практически не используют из-за большого скрытого коэффициента
Вот тут можете что-то по подробней ? Я бы хотел посмотреть "типовую" реализацию хотя бы псевдо-кодом, может выкладки какие
У меня же, сортировка как я уже написал, случилась сама собой, задачи были другие; моя реализация предоставляет кучу других плюшек, которые я преследовал изначально
В коментах нельзя картинки вкладывать
Я тестил массивы, сгенерированные случайно, до 10 000 элементов, но тест был поставлен таким образом, что каждый массив нужно отсортировать 1 000 раз - так я сглаживал всякие случайные факторы
Из ограничений - разница между минимальным и максимальным значениями. Но даже так алгоритм сохраняет логарифмическую асимптоту
Изначально предполагалось что числа должны быть только целые, но это ограничение можно обойти, если все числа привести к целым - помножить на pow(10,x) где x есть количество разрядов после запятой
Позже я пришёл к тому, что это некая вариация сортировки подсчётом O(n+k), но поведение асимптоты другое O(log(n)+k) или O(log(n)+n^k) я ещё точно с этим не определился, но суть в том что логарифм остаётся на любых интервалах данных. И такого я нигде не нашёл, только в своих замерах
Ещё одно ограничение - динамические массивы и отрицательные индексы, так что этот алгоритм не есть универсальный, или нужно пилить дополнительные обёртки
Так как статья относительно свежая, и комментарии всего пол месяца ... Оставлю и свой комент
Я тут на днях изобрёл велосипед, который как оказалось ещё и сортировать массивы умеет, хотя изначально у меня стояли другие задачи
Едет этот велосипед в несколько раз быстрее "быстрой сортировки"
Сейчас я гоняю массированные тесты этого алгоритма, и в сравнение взял ещё две сортировки, помимо быстрой
К чему я всё это пишу: полез гуглить, и сходу не нашёл ничего, но чуть позже почитал немного про сортировку Хэна, и по описанию на вики - очень похоже, хотя по детальному изучению статей - сортировка Хэна какая-то "очень сложная", тут тебе и деревья, и хэши какие-то, описание с матаном - в общем действительно рокет-сайнс какой-то
А у меня всего два цикла верхнего уровня, и один вложенный как вспомогательный - для группировки дубликатов
Вот тут можете что-то по подробней ? Я бы хотел посмотреть "типовую" реализацию хотя бы псевдо-кодом, может выкладки какие
У меня же, сортировка как я уже написал, случилась сама собой, задачи были другие; моя реализация предоставляет кучу других плюшек, которые я преследовал изначально