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?

  • sorry about that. I thought I would clarify all the constraints when describing the problem. – user270386 Dec 3 '15 at 15:04
  • integer is inferred but suggest you add that to the question to be clear – paparazzo Dec 3 '15 at 16:25
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.

| improve this answer | |
  • Woah! that was such a simple and nice solution. Thanks :) – user270386 Dec 3 '15 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 '15 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 '15 at 15:06
  • BTW, I did not know about counting sort terminology; I figured out that algorithm myself. – Basile Starynkevitch Dec 3 '15 at 18:19
  • That must be why you explained it so much clearly and suscintly than wikipedia – radarbob Dec 5 '15 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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