2

Given a list of integers whose length is unknown, and each of its elements lies between 1 to 1000, how does one sort this list in linear time?

2
  • sorry about that. I thought I would clarify all the constraints when describing the problem.
    – user270386
    Dec 3, 2015 at 15:04
  • integer is inferred but suggest you add that to the question to be clear
    – paparazzo
    Dec 3, 2015 at 16:25

1 Answer 1

12

You know that every element of your int arr[]; is in [1;1000].

So have an array of counters, int cnt[1001]; in C parlance. Clear it (all zeros).

Then, read the arr[] array sequentially. Suppose that you have read the value x at index i (so x==arr[i]). Then increment its counter, so cnt[x]++;

When you have reached the end of the input array arr, iterate on cnt so for (int i=0; i<=1000; i++) and output the number i exactly cnt[i] times.

This is O(n) (because the bound 1000 is a constant).

This sort is often known as the counting sort.

5
  • Woah! that was such a simple and nice solution. Thanks :)
    – user270386
    Dec 3, 2015 at 14:57
  • Although this achieves linearity, is there a practical reason you would want to normalize the time to the highest possible value like this?
    – Flosculus
    Dec 3, 2015 at 14:57
  • Don't know. Just got asked in interview, suggested radix sort but got stuck.. I rarely use counting , radix, shell etc linear time sorting...i kinda forgot them and paid for it :(
    – user270386
    Dec 3, 2015 at 15:06
  • BTW, I did not know about counting sort terminology; I figured out that algorithm myself. Dec 3, 2015 at 18:19
  • That must be why you explained it so much clearly and suscintly than wikipedia
    – radarbob
    Dec 5, 2015 at 23:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.