CODEWITHSUNDEEP
c++algorithmsorting
aroma
aroma

Reputation: 1421

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.

Upvotes: 4

Views: 302

Answers (2)

Henrik
Henrik

Reputation: 23324

vector<int> count(n*n+1);
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        ++count[i*j];
for (int i = 1; i <= n*n; ++i)
    for (int j = 0; j < count[i]; ++j)
        cout << i << " ";

This is in essence the O(n*n) solution as described in cmaster's answer.

Upvotes: 3

cmaster - reinstate monica
cmaster - reinstate monica

Reputation: 40645

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.

Upvotes: 4

Related Questions