Бисерная сортировка (Bead sort)

Вовсе нет, если речь о Double, то ничего не изменится. Проблемой тут будет только вылет возможных сортируемых значений за предел double при умножении.

Хабр, ты окончательно ебанулся.
Под эту сортировку выделяется N * Max памяти, где N — число элементов, max — максимальная величина элемента. В любую реализацию гляньте, блин.

for (i = 1, max = a[0]; i < len; i++)
		if (a[i] > max) max = a[i];
 
	beads = calloc(1, max * len);
 

На сортировку N целых чисел, таким образом, нужно N * Max * sizeof(int) памяти.
На сортировку дробных чисел нужно будет N * round(Max * 10^k) * sizeof(int) памяти, потому что умножение на 10^k увеличивает максимальное значение. Это верно вообще для всех сортировок вычёрпыванием.
Технический ресурс, my ass.

Это статья о страшной сортировке в честь надвигающегося Хеллоуина :)

O(n²) — это худший случай по памяти. Максимальное количество возможных значений n сортируемых натуральных чисел как раз равно n. В худшем случае m = n.

Почему при оценке памяти именно умножение, а не сложение? Потому что изначально входной массив из n элементов, а дополнительно приходится обрабатывать матрицу n x n (в худшем случае).

Насчёт counting sort. Да, бисерная сортировка — это сортировка подсчётом, но только через «одно место», ухудшенный вариант. Вместо того чтобы обрабатывать сами сортируемые числа, мы обрабатываем каждую единичку каждого числа. Всего единиц в массиве натуральных чисел равно сумме всех чисел S, отсюда и временная сложность O(S).

Сортировать бусинками невыгодно с какой стороны ни посмотри, но для пятничного поста алгоритм вполне годится :)

O(n log n) — это минимум для сортировок абстрактных элементов с определенной на них функцией сравнения. Т.е. алгоритм ничего не знает ни о природе элементов, ни об их начальном расположении.

Здесь же сортируются исключительно натуральные числа и алгоритм использует их свойства. Еще пример — поразрядная сортировку с временем O(nk).

Да, самое интересное в семействе сортировок подсчетом — тот факт, что сложность может быть меньше Ω(n log n)

Пожалуй, да )

Чаще всего сортировку наглядно представляют как бисер нанизанный на спицы. Или как шарики, скатывающиеся по узким желобкам. Второй вариант мне был проще для создания анимации.

O(1) — это результат некоего теоретизированного рассуждения, мысленный эксперимент с участием идеального физического устройства в идеальных условиях, реализующего эту сортировку. Если абсолютно исключить трение, поместить устройство вблизи сверхмассивного тела, мгновенно и одномоментно предоставить шарикам возможность упасть вниз по спицам — то временная сложность будет стремиться как раз к такому значению. Как-то так.

Ой, промахнулся, смотрите моим комментарием ниже.

>>> Не понятно, как в такой сортировке данные к ключу привязывать?

В статье в двух местах приведена ссылка на реализацию сортировки на 37 языках программирования.

>>> Т.е. например отсортировать строки в таблице по натуральному ключу?

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

>>> А если ни как, то какой хоть один параметр у нее лучше чем у Сортировки подсчетом?

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

Зачем вообще нужна тогда Bead sort и на кой чёрт о ней писать целую статью? Прежде всего научный интерес: в целях образования, для любителей поразбирать алгоритмы. Неэффективные методы также полезно изучать как и эффективные. Да и на практике вдруг кому-то пригодится — приём тотального сдвига может понадобиться для решения какой-нибудь задачи, вообще не связанной с сортировкой.