Различные типы сортировок

Я читал про разные типы сортировок, пять из которых известны всем хорошо. Я их легко освоил.

Пузырьковая сортировка
Сортировка вставкой
Сортировка слиянием
Сортировка выборкой
Быстрая сортировка

Но есть две сортировки, которые я не смог понять (отличие от других, и когда он
применимы). Это

Карманная сортировка
Корневая сортировка (Radix Sort)

Не могли бы прояснить, где лучше их использовать, их преимущества и отличия, а такж
буду рад ссылкам (или прямому коду) на простейшие реализации данных алгоритмов на С или С++.     

Ответы

Ответ 1

В отличие от сортировок 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 очень хорош, если входные данные подчиняются требуемому распределению, но это бывает не слишком часто.


Ответ 2

Блочная сортировка Идея в том чтобы пользуясь какими-то известными заранее свойствам
входных данных раскидать последовательность в n корзин. После этого все, что попал
в отдельную корзину, сортируется либо рекурсивно таким же методом, либо другими методами. Если известно что данные раскидываются по корзином равномерно, получится что в корзину попадет мало элементов и в среднем алгоритм будет работать за O(n)
radix sort Применяется для сортировки последовательностей, сравниваемых лексикографически
Есть два варианта: либо сортировать с младшего положения к старшему стабильной сортировкой, либо отсортировать блочной сортировкой по первому символу, а затем корзины отсортировать рекурсивно по второму символу, и т.д.


Ответ 3

в книжке Каррано Ф.М., Причард Дж. Абстракция данных и решение задач на C++. Стены и зеркала
приводится пример реализации последних двух сортировок и даются некоторые комментарии


Ответ 4

на малочисленных объёмах данных рекоммендуется quicksort
на больших объёмах рекоммендуется merge sort, c использованием многопоточности
если по какой-то причине лучше не использовать многопоточность, например, данны
не достаточно большие, чтобы ощутим был выигрыш от распаралеливания, или, просто одноядерная система на атомной станции, то лучше использовать heapsort, у которой асимптотика немного лучше
в стандартной библиотеке алгоритмов можно найти их реализации http://en.cppreference.com/w/cpp/algorithm
остальные алгоритмы сортировок, пожалуй, не имеет практического смысла в применении