Doesn't this use O(n^3) space and the time complexity will also be
O(n^3) (passing through n^3 different possible values).
Use Radix Sort with radix/base equal to n, meaning that instead of
using the digits of numbers in base 10, find the digits in base n.
On Oct 3, 1:30 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
