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.

sort 
We've worked on this challenge in these gyms: modena 
comments powered by Disqus