Re:My Favorite Algorithm: Linear Time Median Finding
by anonymoushn on Thursday July 25, 2024 @08:51AM
(#41068075)
Sorting fractions by numerical value is a good example. Previously I've heard that there are some standard collation schemes for some human languages that resist radix sort, but when I asked about which ones in specific I didn't hear back :(
Re:My Favorite Algorithm: Linear Time Median Finding
by contravariant on Thursday July 25, 2024 @10:38AM
(#41069228)
The Unicode Collation algorithm doesn't look fun to implement in radix sort, but not entirely impossible either. They do note that some characters are contextual, an example they give is that CH can be treated as a single character that sorts after C (so also after CZ). Technically that is still lexicographical, but not byte-for-byte.
It's actually hard to come up with something that cannot be sorted lexicographically. The best example I was able to find was big fractions. Though even then you could write them as continued fractions and sort those lexicographically (would be a bit trickier than strings).