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?
How to sort a list containing bounded set of values in linear time when length is unknown?
You know that every element of your
int arr; is in
So have an array of counters,
int cnt; in C parlance. Clear it (all zeros).
Then, read the
arr array sequentially. Suppose that you have read the value
x at index
x==arr[i]). Then increment its counter, so
When you have reached the end of the input array
arr, iterate on
for (int i=0; i<=1000; i++) and output the number
This is O(n) (because the bound 1000 is a constant).
This sort is often known as the counting sort.
Woah! that was such a simple and nice solution. Thanks :) 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? 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