@harshal :
range of integers are given from 1 to n^3-1,,there are total n integers
only.
also:-Treat the numbers as 2-digit numbers in radix n. Each digit ranges
from 0 to n^3 -1.
Sort these 2-digit numbers with radix sort.
There are 2 calls to counting sort, each taking (n + n) = (n) time, so
that the
total time is (n).
On Sun, Oct 3, 2010 at 4:00 PM, bittu <shashank7andr...@gmail.com> wrote:
> Use counting Sorting Algorithm...i am givin the code below ..it sort
> the array in O(n) but uses xtra memory space (n+k)...we have to pay
> eother memory or time....
>
>
> #include <stdlib.h>
> #include<stdio.h>
> #include<conio.h>
>
>
> int main()
> {
> int array[]={4,2,2,2,4,5,9,5,10};
> int size=10;
> int min,max;
> max=min=array[0];
> int i=0;
> //clrscr();
> for(i = 1; i < size; i++)
> {
> if (array[i] < min)
> min = array[i];
> else if (array[i] > max)
> max = array[i];
> }
>
> int range = max - min + 1;
> int *count =(int *) malloc(range * sizeof(int));
>
> for(i = 0; i < size; i++)
> count[i] = 0;
>
> for(i = 0; i < size; i++)
> count[array[i]]++;
>
>
>
> int pos=0;
>
> for(i=0;i<size;i++)
> {
> for(int j=0;j<count[i];j++)
> {
> array[pos]=i;
> pos++;
> }
> }
> //free(count);
>
> for(int i=0;i<size;i++)
> printf("%d \n" ,array[i]);
>
> getch();
> }
>
> Regard's
> Shashank Mani Narayan " Don't Be Evil U Can Earn While U learn"
> Computer Science & Engineering
> Birla Institute of Technology,Mesra
> Cell No. +91-9166674831
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
best wishes!!!!!
vaibhav
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
