On 5/5/06, Manu <[EMAIL PROTECTED]> wrote:
> I know counting sort can do in linear time but we dont need to use and
> extra space.
> as we do in case of counting sort.
if the array values are only 0 and 1, assuming that the array contains
at best 255 elements, counting sort would need only 3 bytes:
Let 'i' be an integer variable of 1 byte, 'cs' an array of two bytes,
'arr' the array to be sorted, sort would be:
for (i=0;i<array_length;cs[arr[i++]]++);
that's it ! :)
If you need, for example, to print out the sorted array:
for (i=0;i<cs[0];i++) print('0');
for (i=0;i<cs[1];i++) print('1');
Obviously, if you limit your array size to 65535, then bytes required
are 3*2 and-so-on.
Please, re-read these pieces of code, maybe there are some typos ...
bye !
Mattia Merzi.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
