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.– user270386Dec 3, 2015 at 15:04
-
integer is inferred but suggest you add that to the question to be clear– paparazzoDec 3, 2015 at 16:25
Add a comment
|
1 Answer
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.
answered Dec 3, 2015 at 14:50
-
-
Although this achieves linearity, is there a practical reason you would want to normalize the time to the highest possible value like this? 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 :( 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
-