Comments 19
производительность соизмерима с быстрой сортировкой;
таблицы/графики? Соизмерима в чью пользу? Если в пользу быстрой, то смысл использовать ее? Или есть какие-то исходные данные, на которых она показывает себя лучше? Как пример недавно упоминавшаяся сортировка на строках ABC.
Просто замечу, что код «сравнивающий» производительность Quick Sort с предложенным алгоритмом абсолютно ничего не доказывает.
Если сравнивать «в лоб» сложности, то получается, что в среднем алгоритм медленнее Qucik Sort и потребляет памяти больше, чем Merge Sort. Область применимости остается загадкой.
Если сравнивать «в лоб» сложности, то получается, что в среднем алгоритм медленнее Qucik Sort и потребляет памяти больше, чем Merge Sort. Область применимости остается загадкой.
.
Кроме того, хотелось бы обратить внимание автора на блочную сортировку
Что-то Ваша хеш-функция и основная идея алгоритма немного мне напоминают FlashSort.
В целом интересный метод, пополнит мою копилку алгоритмов сортировок.
В целом интересный метод, пополнит мою копилку алгоритмов сортировок.
Алгоритм относится к классу устойчивых сортировок? Правда?
Он будет устойчив только в том случае, если из эквивалентности ключей (cmp(x,y)==0) следует равенство их хешей (h(x)==h(y)).
Иначе может получиться так, что эквивалентные ключи окажутся в разных корзинах.
Например, сравниваем строки нечувствительно к регистру. VASYA==Vasya==vasya, а хеши у этих строк одинаковые?
Хеш-таблица служит для того, чтобы осмысленно разбить входной массив на подмассивы, так, что идентичные ключи окажутся в одной корзине.
Но, во-первых, а существует ли какой-то выигрыш от этого? Если во входном наборе много дубликатов, то — выигрыш может быть, а может и не быть (вот как упадут все элементы в одну корзину, и что делать?)
И, во-вторых, затраты на вычисление хеша — против тупого разбиения входного массива на случайные подмассивы.
Причём, тупое разбиение на последовательные подмассивы как раз обеспечит устойчивость.
Он будет устойчив только в том случае, если из эквивалентности ключей (cmp(x,y)==0) следует равенство их хешей (h(x)==h(y)).
Иначе может получиться так, что эквивалентные ключи окажутся в разных корзинах.
Например, сравниваем строки нечувствительно к регистру. VASYA==Vasya==vasya, а хеши у этих строк одинаковые?
Хеш-таблица служит для того, чтобы осмысленно разбить входной массив на подмассивы, так, что идентичные ключи окажутся в одной корзине.
Но, во-первых, а существует ли какой-то выигрыш от этого? Если во входном наборе много дубликатов, то — выигрыш может быть, а может и не быть (вот как упадут все элементы в одну корзину, и что делать?)
И, во-вторых, затраты на вычисление хеша — против тупого разбиения входного массива на случайные подмассивы.
Причём, тупое разбиение на последовательные подмассивы как раз обеспечит устойчивость.
«устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами» — из вики. Два одинаковых значения здесь претендуют на одно и тоже место. При разрешении коллизий порядок одинаковых значений не изменяется.
В чем проблема-то? К чему здесь сравнение строк и корзины я вообще, извините, не понял.
В чем проблема-то? К чему здесь сравнение строк и корзины я вообще, извините, не понял.
Ну, если алгоритм работает только над числами, и только с единственным отношением порядка — естественным для чисел — тогда конечно, проблемы нет.
Просто этот алгоритм не получится обобщить на произвольные типы данных.
Просто этот алгоритм не получится обобщить на произвольные типы данных.
А что значит произвольный тип данных? Как вы будите сортировать блоки например? По размеру? По весу? Когда требуется сортировка не чисел? Может я не понимаю вас, обьясните.
Что, никогда строки не сортировали, например?
В общем случае, для упорядочивания произвольных данных достаточно лишь определения отношения порядка: что чего меньше-больше-равно. (Иначе, как можно было бы вообще понять, упорядочен набор данных или нет?)
И все эти квиксорты, мержсорты, пузырьки и вставки работают именно с отношением порядка, не вдаваясь в суть данных.
Что позволяет указывать произвольное отношение. Например, строки можно сортировать чувствительно и нечувствительно к регистру, с использованием национальных алфавитов или тупо сравнивая ascii/unicode-коды. А числа — по значению и по абсолютной величине, ну и так далее.
Некоторые типы данных можно сортировать, используя характерные особенности этого типа.
Целые числа — раскладывая на разряды, радиксом; разбивая на поддиапазоны — блочной сортировкой; подсчётом, наконец. Строки — префиксным деревом (trie).
Что делать с произвольными блоками — хозяйское дело. Можно трактовать их как сверхдлинные целые числа, как строки, как байтовые векторы, можно выделять из них какое-то нужное содержимое и сортировать по этому содержимому.
В общем случае, для упорядочивания произвольных данных достаточно лишь определения отношения порядка: что чего меньше-больше-равно. (Иначе, как можно было бы вообще понять, упорядочен набор данных или нет?)
И все эти квиксорты, мержсорты, пузырьки и вставки работают именно с отношением порядка, не вдаваясь в суть данных.
Что позволяет указывать произвольное отношение. Например, строки можно сортировать чувствительно и нечувствительно к регистру, с использованием национальных алфавитов или тупо сравнивая ascii/unicode-коды. А числа — по значению и по абсолютной величине, ну и так далее.
Некоторые типы данных можно сортировать, используя характерные особенности этого типа.
Целые числа — раскладывая на разряды, радиксом; разбивая на поддиапазоны — блочной сортировкой; подсчётом, наконец. Строки — префиксным деревом (trie).
Что делать с произвольными блоками — хозяйское дело. Можно трактовать их как сверхдлинные целые числа, как строки, как байтовые векторы, можно выделять из них какое-то нужное содержимое и сортировать по этому содержимому.
Просто оставлю это здесь: en.wikipedia.org/wiki/Bucket_sort
Sign up to leave a comment.
Сортировка вставкой в хэш-таблицу