0
$\begingroup$

$k = \Theta(n)$

The arrays consist only natural numbers $1$ to $n$

The sum of the length of all arrays = $\Theta(n)$

It should return the $k$ original arrays, each sorted on its own.

The running time should be at worst $\Theta(n)$. How is it even possible? There's something I must be missing because I have no idea how to approach this. The data I gave you is all the given data. Any ideas?

Using counting sort on each array won't work, for it will be $\Theta(n^2)$, but maybe a different approach using this method?

Improve this question
$\endgroup$
7
  • $\begingroup$ Just for iterating over all arrays you need $\theta(n^2)$ operations, are you sure about your text ? $\endgroup$ Commented Dec 7, 2017 at 10:23
  • $\begingroup$ sorry I edit it, the change is "The sum of the length of all arrays = θ(n) " $\endgroup$ Commented Dec 7, 2017 at 10:26
  • $\begingroup$ No (explicit/$\omicron(n)$) limit on space? How is the problem/solution different from handling a single such array? $\endgroup$ Commented Dec 7, 2017 at 12:01
  • $\begingroup$ Cheeky (practical but impermissible) non-answer: radix sort all of the arrays. $\endgroup$ Commented Dec 7, 2017 at 12:25
  • $\begingroup$ @greybeard There's no space limit to this question. the difference is you need to sort each array on its own, every element should stay at his original array. $\endgroup$ Commented Dec 8, 2017 at 5:08

1 Answer 1

Reset to default
1
$\begingroup$

You can solve the issue by using some pointers. First, run counting sort algorithm on all arrays in $\Theta(n)$ (suppose all of them are in a set). In the meanwhile, when running the algorithm, set a pointer for each number of each array to the sorted index of that number.

Using this data structure, you will have $k$ sorted arrays at the end.

Improve this answer
$\endgroup$
3
  • $\begingroup$ tnx, sorry but I didn't quite understand the part when you set pointers. can you elaborate? you point each number to its index in the counter? $\endgroup$ Commented Dec 7, 2017 at 11:44
  • $\begingroup$ @MatanyaP Yes. Indeed, you can see all these arrays as a single array. Then sort them using counting sort algorithm. When you run the algorithm, set a pointer from each element of each array to its index in that universal sorting. In this way, you have sorted the sub arrays. $\endgroup$ Commented Dec 7, 2017 at 12:14
  • $\begingroup$ Note that you need multiple counts per bucket, and to avoid allocating it all in advance that means you probably want to make each bucket a dynamically-sized hash map. Not all that cheap on real hardware ;). $\endgroup$ Commented Dec 7, 2017 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.