Зачем нужны блочная и поразрядная сортировки?
1,00
р.
Я читал про разные типы сортировок, пять из которых известны всем хорошо. Я их легко освоил.
Пузырьковая сортировка Сортировка вставкой Сортировка слиянием Сортировка выборкой Быстрая сортировка
Но есть две сортировки, которые я не смог понять (отличие от других, и когда они применимы). Это
Карманная сортировка (блочная, Bucket Sort) Корневая сортировка (поразрядная, Radix Sort)
Не могли бы прояснить, где лучше их использовать, их преимущества и отличия, а также буду рад ссылкам (или прямому коду) на простейшие реализации данных алгоритмов на С или С++.
Ответ
В отличие от сортировок 1–5, которые требуют от типа данных лишь операции сравнения, задающей линейный порядок, карманная и поразрядная (radix) сортировки предполагают, что нам известно больше о сортируемых элементах, за счёт чего они работают за O(n) от размера входных данных, преодолевая теоретический барьер O(n log(n)) для сортировок 1–5.
Карманная сортировка (bucket sort) Этот алгоритм предполагает, что входные данные — числа, распределённые равномерно на некотором отрезке (скажем, [0 1]). Разобьём этот отрезок на n частей, и распределим по ним данные n чисел. Ожидается, что в каждую часть попадёт немного элементов, а, значит, к ним можно применить простую и быструю сортировку (например, вставками). Ответом будет объединение результатов сортировки частей. Алгоритм требует O(n) дополнительной памяти и, в случае равномерного распределения входных данных, работает за O(n). Обоснование асимптотики.
Поразрядная сортировка (radix sort) Этот алгоритм предполагает, что сортируются целые числа от 0 до C, представленные в позиционной системе счисления c основанием k (например, 2^8 или 2^16). Пойдём циклом по разрядам чисел от младших к старшим. Заведём массив count размером k, т.ч. count[i] = число элементов, имеющих в текущем разряде i (это делается линейным проходом по элементам). Далее, рассчитаем суммы на префиксах массива count (т.е. pref[i] это сумма count[j] для всех j меньше i. Теперь пройдёмся по сортируемым числам, кладя их в новом массиве на место pref[текущий разряд числа] и увеличивая этот элемент pref. После такого прохода за O(n + k) числа окажутся стабильно отсортированными по текущему разряду, а значит, в силу стабильности, и по всем более младшим разрядам. В конце все числа будут стабильно отсортированы. Работает данная реализация за O((n + k) * log_k(C)), что, в принципе, является O(n) (k и C от n не зависят). Также этот алгоритм можно модифицировать для быстрой сортировки строк в лексикографическом порядке, если развернуть внешний цикл и избежать копирования строк в процессе работы алгоритма. Некоторые реализации.
С практической точки зрения, когда сортируются числа, о которых не известно почти ничего, quicksort, обладая теоретически худшей асимптотикой, практически всегда обгоняет эти алгоритмы. В принципе, очень хорошо написанный radixsort может обогнать heapsort/mergesort, если от сортировки требуется стабильность. Bucketsort очень хорош, если входные данные подчиняются требуемому распределению, но это бывает не слишком часто.
Пузырьковая сортировка Сортировка вставкой Сортировка слиянием Сортировка выборкой Быстрая сортировка
Но есть две сортировки, которые я не смог понять (отличие от других, и когда они применимы). Это
Карманная сортировка (блочная, Bucket Sort) Корневая сортировка (поразрядная, Radix Sort)
Не могли бы прояснить, где лучше их использовать, их преимущества и отличия, а также буду рад ссылкам (или прямому коду) на простейшие реализации данных алгоритмов на С или С++.
Ответ
В отличие от сортировок 1–5, которые требуют от типа данных лишь операции сравнения, задающей линейный порядок, карманная и поразрядная (radix) сортировки предполагают, что нам известно больше о сортируемых элементах, за счёт чего они работают за O(n) от размера входных данных, преодолевая теоретический барьер O(n log(n)) для сортировок 1–5.
Карманная сортировка (bucket sort) Этот алгоритм предполагает, что входные данные — числа, распределённые равномерно на некотором отрезке (скажем, [0 1]). Разобьём этот отрезок на n частей, и распределим по ним данные n чисел. Ожидается, что в каждую часть попадёт немного элементов, а, значит, к ним можно применить простую и быструю сортировку (например, вставками). Ответом будет объединение результатов сортировки частей. Алгоритм требует O(n) дополнительной памяти и, в случае равномерного распределения входных данных, работает за O(n). Обоснование асимптотики.
Поразрядная сортировка (radix sort) Этот алгоритм предполагает, что сортируются целые числа от 0 до C, представленные в позиционной системе счисления c основанием k (например, 2^8 или 2^16). Пойдём циклом по разрядам чисел от младших к старшим. Заведём массив count размером k, т.ч. count[i] = число элементов, имеющих в текущем разряде i (это делается линейным проходом по элементам). Далее, рассчитаем суммы на префиксах массива count (т.е. pref[i] это сумма count[j] для всех j меньше i. Теперь пройдёмся по сортируемым числам, кладя их в новом массиве на место pref[текущий разряд числа] и увеличивая этот элемент pref. После такого прохода за O(n + k) числа окажутся стабильно отсортированными по текущему разряду, а значит, в силу стабильности, и по всем более младшим разрядам. В конце все числа будут стабильно отсортированы. Работает данная реализация за O((n + k) * log_k(C)), что, в принципе, является O(n) (k и C от n не зависят). Также этот алгоритм можно модифицировать для быстрой сортировки строк в лексикографическом порядке, если развернуть внешний цикл и избежать копирования строк в процессе работы алгоритма. Некоторые реализации.
С практической точки зрения, когда сортируются числа, о которых не известно почти ничего, quicksort, обладая теоретически худшей асимптотикой, практически всегда обгоняет эти алгоритмы. В принципе, очень хорошо написанный radixsort может обогнать heapsort/mergesort, если от сортировки требуется стабильность. Bucketsort очень хорош, если входные данные подчиняются требуемому распределению, но это бывает не слишком часто.
