9

So here is the question:

Suppose you have 100 thousand integers which ranges from 1 to 1 million. Please sort out the integers. The time complexity should be O(n).

Anybody who shares his or her ideas is well appreciated.

Ryan Berger
  • 9,644
  • 6
  • 44
  • 56
Tracy
  • 1,988
  • 5
  • 25
  • 36
  • 4
    Counting sort: http://en.wikipedia.org/wiki/Counting_sort – Paul R Oct 14 '10 at 08:44
  • 1
    @Paul R: The Wikipedia article claims this is O(n+k), and only efficient if n > k. In this case n = 100,000 and k = 1,000,000. – Jackson Pope Oct 14 '10 at 08:49
  • 1
    Or radix sort ( 1 million is 20 bits, so 20 passes over 100,000 integers in naive case; naive counting sort requires you to zero the million counters (using a hash table doesn't, but you don't key the results in order, so you then have to sort it, using a tree map doesn't, but non-constant time insertion) and then iterate over them to get the result, which is also of the order of 2 million operations; binary radix sort can be done in place so requires no extra storage. – Pete Kirkham Oct 14 '10 at 08:52
  • 1
    If the runtime requirement is O(n) and n is in the 10^5 range, then counting sort runtime is dominated indeed by k, however k=10*n, so you can still regard it as efficient in this case. Counting sort efficiency is a problem if you want to sort f.ex. 1000 integers in a full 2^32 range. – Frank Oct 14 '10 at 08:52

5 Answers5

15

Sounds like a straightforward counting sort.

  1. Reserve memory for an array a of size 1 million
  2. Initialize all array values to 0
  3. Loop through the integers. For each integer i increment a[i] by one.
  4. Output sorted sequence by walking through the array and printing each number i for a[i] times.

Space is constant. Runtime is O(n).

Frank
  • 10,461
  • 2
  • 31
  • 46
  • Gotcha，thanks，sounds like this question is not that hard.I just hate myself – Tracy Oct 15 '10 at 07:33
  • 1
    runtime is constant too, unless you change the question, which as I wrote you should. Then Space is O(n), runtime is O(n). You can't have it both ways. – piccolbo Oct 15 '10 at 15:55
  • 2
    One more thing to add to this good answer. For setup 4 you should walk through the array backwards if you want to have a stable sort (i.e. in case of ties things get printed in the order of the pre-sorted array ). – Himadri Choudhury Jun 08 '12 at 15:10
3

The hint should be that they range from 1 to 1 million.

See pigeonhole sort

The Archetypal Paul
  • 41,321
  • 20
  • 104
  • 134
3

Since the problem has fixed size and includes a finite set of instances, any sorting algorithm will terminate in O(1). You should tell the tester to go back to algorithm analysis school. One possible way to generalize this problem to an infinite set is: you have an array of size n with numbers ranging in [0, 10n]. Can you sort it in O(n)? That makes sense to me. Or you could parametrize the problem with the size of the array and the range of the integers and come up with some O(f(n,k)) bound. The problem is when you get a question like this in an interview, what do you do? Do you try to guess what the interviewer would like to hear or do you say something like "let me rephrase your question"? Or you just scoot towards the exit with a big smile?

piccolbo
  • 1,305
  • 7
  • 17
0

Use count sort. Just count all of them ( O(n) ), and then create fill the result array ( O(n), again).

ruslik
  • 14,714
  • 1
  • 39
  • 40
0

You have to use any known sorting algorithms with complexity O(n)

Is there an O(n) integer sorting algorithm?

Community
  • 1
  • 1
Alec Smart
  • 94,115
  • 39
  • 120
  • 184