ash -4 years ago 84
C++ Question

# What is the fastest way to sort these n^2 numbers?

Given a number 'n', I want to return a sorted array of n^2 numbers containing all the values of k1*k2 where k1 and k2 can range from 1 to n.

For example for n=2 it would return : {1,2,2,4}.(the number are basically 1*1,1*2,2*1,2*2).

and for n=3 it would return : {1,2,2,3,3,4,6,6,9}.

(the numbers being : 1*1, 2*1, 1*2, 2*2, 3*1, 1*3, 3*2, 2*3, 3*3)

I tried it using sort function from c++ standard library, but I was wondering if it could be further optimized.

Well, first of all, you get `n^2` entries, the largest of which will be `n^2`, and of the possible value range, only a tiny amount of values is used for large `n`. So, I'd suggest a counting approach:

1. Initialize an array `counts[]` of size `n^2` with zeros.
2. Iterate through your array of values `values[]`, and do `counts[values[i]-1]++`.
3. Reinitialize the `values` array by iterating through the `counts` array, dropping as many values of `i+1` into the `values` array as `counts[i]` gives you.

That's all. It's `O(n^2)`, so you'll hardly find a more performant solution.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download