Поразрядная сортировка плавающих данных

См. эту страницу обсуждения этого.

http://codercorner.com/RadixSortRevisited.htm

По сути, компьютеры хранят числа с плавающей запятой в определенном формате. Они не пишут его как 45.13. В результате представление об этом таким образом не будет связано с тем, как это работает на самом деле.

Игнорируя это, сортировка Radix должна сначала просмотреть наиболее значимую часть. В числе с плавающей запятой это самые левые цифры. По сути, мы дополняем все числа так, чтобы у них было одинаковое количество цифр до запятой. Затем мы читаем цифры слева направо.

Сортировка по основанию работает с двоичным представлением числа и сортирует объекты, как если бы они были большим двоичным целым числом.

Для реальных целых чисел и строк двоичное представление вполне соответствует ожидаемому нами порядку сортировки, поэтому сортировка по основанию представляет собой интересную, хотя и несколько необычную альтернативу.

Оказывается, пока число с плавающей запятой перемещается в правильном направлении, сортировка по основанию может работать хорошо, за исключением того, что она будет обрабатывать бит знака в обратном порядке.

Во внутреннем двоичном представлении значения FP имеют бит знака, около 10 бит экспоненты, а затем примерно 20 или 50 бит составляют «дробь» или мантисса.

S E E E E E E E E M M M M M M M M M M M M M M M . . .

Показатель степени смещен, так что маленькие значения действительно являются самыми отрицательными показателями, поэтому он сортируется правильно, как и мантисса.

Пока все числа либо положительные, либо отрицательные, или если бит знака сначала инвертируется, а сканирование идет слева направо, то я думаю, что сортировка по основанию будет работать с числами FP.

Лучший известный мне код для сортировки двойников по основанию находится здесь: https://bitbucket.org/ais/usort/src/474cc2a19224/usort/f8_sort.c