Big Sorting

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.

Solutions

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++

1
2
3
4
5
6
7
8
9

int n, i; cin >> n;
vector<string> v(n);
copy_n(istream_iterator<string>(cin), n, begin(v));

sort(begin(v), end(v), [](auto& l, auto& r) {      
    if (l.size() == r.size())
        return l < r;
    return l.size() < r.size();
});

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:

1

read line; sort -n

Solution in C#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int n = Convert.ToInt32(Console.ReadLine());
string[] a = new string[n];
for (int i = 0; i < n; i++) 
    a[i] = Console.ReadLine();

Array.Sort(a, (left, right) => {
    if (left.Length != right.Length)
        return left.Length - right.Length;
    else
        return string.CompareOrdinal(left, right); // left.CompareTo(right) is too slow
});
for (int i = 0; i < n; i++) 
    Console.WriteLine(a[i]);

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.

Very similar to C#: Java and Javascript.

Solution in Ruby

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

n = gets.strip.to_i
a = Array.new(n)
for i in (0..n-1)
    a[i] = gets.strip
end
a.sort! do |left, right|
    if left.length != right.length
        left.length <=> right.length
    else
        left <=> right
    end
end
for i in (0..n-1)
    puts a[i]
end

Ruby uses the so-called spaceship operator.

Haskell

1
2
3
4
5
6
7

import Data.List (sortBy)
import Data.Ord (compare, comparing)

bigSort :: [String] -> [String]
bigSort = sortBy $ (comparing length) <> compare

main = interact $ unlines . bigSort . drop 1 . lines

Haskell can compose comparing functions with the <> operator, so you can use the resulting function as parameter to sortBy.

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 mappend two Ordering values, 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 EQ.