See the original problem on HackerRank.
Consider an array of numeric strings where each string is a positive number with anywhere from \( 1 \) to \( 10^6 \) digits. Sort the array’s elements in non-decreasing, or ascending order of their integer values and print each element of the sorted array on a new line.
See Big Sorting on HackerRank.
We may be tempted to use arbitrary precision arithmetic - e.g. Big Integers. This is not needed and it’s possibly slow to convert from/to the decimal number system.
Instead, we could note that if the numbers have a different number of digits then a lexicographical comparison does the job. Otherwise, the number with more digits is clearly bigger.
Thus, we could just read all the numbers as strings and sort them by using a comparison function that implements such an observation.
It’s interesting to use different languages and see how to the customize the standard sort:
Solution in C++
In this snippet, you can see that we use
std::string::operator< that implements a lexicographical comparison.
Solution in Bash
The simplicity of Bash is disarming:
Solution in C#
Differently from C++, here you see that C#‘s
Sort wants a C-style comparison operator: when the method returns 0, it means that two objects sort the same. Negative value means the first object is smaller, positive value means the first object is bigger.
Solution in Ruby
Ruby uses the so-called spaceship operator.
Haskell can compose comparing functions with the
so you can use the resulting function as parameter to
The (free) book Learn You a Haskell for Great Good! explains how it works here in Chapter 11
1 2 3 4 5
instance Monoid Ordering where mempty = EQ LT `mappend` _ = LT EQ `mappend` y = y GT `mappend` _ = GT
The instance is set up like this: when we
Orderingvalues, the one on the left is kept, unless the value on the left is
EQ, in which case the right one is the result. The identity is