Time-space Trade-off in Radix Sort

In Radix Sort,

Time Complexity : O(nd)

Space Complexity: O(n+RADIX)

However, by changing RADIX, one can reduce d and get as low as O(n) which is similar to counting sort which uses the RADIX size equal to the range of array (Normalization or pull up is required if there are some negative numbers).

But that will cause rise in Space Complexity that is directly proportional to RADIX.

Careful selection of RADIX for a particular problem will help in sorting close to linear time and less space.

Please feel free to comment if you feel any error in it.

Radix Sort: C Implementation

Radix sort is one of the most popular algorithms and is used to sort the integers. It is based on counting sort and that makes it different from other algorithms which are based on comparison sorting. It gets name Radix sort because radix means digit. In this, stable counting sort runs on each radix position to sort the integers.
E.g.
I = {10,123,39,9,1234,56} and radix = 10
For I, first we run count sort on unit digit position and the output will be
I0 = {10,123,1234,56,39,9}
Then count sort is run on 10th position of I0 and output will be
I1 = {9,10,123,1234,39,56}
Please note that upto 2nd digit, whole array is sorted.
Similarly, for 100th position
I2 = {9,10,39,56,123,1234}
For 1000th position
I3 = {9,10,39,56,123,1234}
And I3 is sorted.
It is done by using Radix 10. Count sort employed here must be stable. Otherwise, whole array may not be sorted.
To extract ith digit from x use
x*RADIX/(RADIX^i)%RADIX

C Implementation:

#define SIZE 256
#define RADIX 10 //We are using 10 as base
void countsort(int *x,int n,int range,int *o,int digitposition)
{
int temp[RADIX];
int i;

for(i=0;i
    temp[i] = 0;
for(i=0;i
    temp[(x[i]*RADIX/digitposition%RADIX)]+=1;

for(i=1;i
    temp[i] += temp[i-1];

for(i=n-1;i>=0;i--)
    o[temp[(x[i]*RADIX/digitposition%RADIX)]-- -1] = x[i];
}

void radixsort(int *x,int n,int *xo)
{
int i,digex,j,digitcount;
int max=x[0];

for(i=1;i
    {
    if(x[i]>max)
        max = x[i];
    }
digitcount = 0;
//To count the number of digits
while(max)
    digitcount++,(max/=RADIX);
//Starting digit that is at unit place
digex = RADIX;
for(j=1;j<=digitcount;j++)
    {
    countsort(x,n,RADIX,xo,digex);
    for(i=0;i
        {x[i] = xo[i];//Copy the output to make it input for next iteration
        }
    digex *= RADIX;
    }
}

int main()
{
int x[SIZE],ox[SIZE];
int n;
int i;
scanf("%d",&n);
for(i=0;i
    scanf("%d",&x[i]);
radixsort(x,n,ox);
for(i=0;i
    printf("%d\n",ox[i]);
return 0;
}

Time Complexity: O(n*d) where n is the size of input and d is the number of digit
Space Complexity: O(n+RADIX)
Please feel free to comment if you find anything wrong. 

Count of an Element in a Sorted Array.

Problem: Given an array a1,a2,a3…an which is sorted in the non-decreasing order. Given an element e, find its number of occurence in the array.

For example: (1,1,1,2,2,3,3,3,4,4) is the given array and let the given element is 3. Its count is 3. For 4, it is 2.
One can think what is so difficult in the problem. It can be solved in more optimised way one can think of.
Method 1:
Simple, but not efficient.
Search for an element linearly. When it is encountered, then count it.
Complexity:

Method 2:
Efficient but consuming space.
First it involves preprocessing of O(n) and will space of O(n). In preprocessing, store the element and its count in another array
keeping its order. When, the element is to be found, it can be found in O(logn) using binary search alongwith its occurence.

Method 3:
Tricky, but efficient.
Use binary Search method to find leftmost and rightmost indices of the element.
Then use the formula right-left+1 to get the count.
Complexity: O(logn)

Code:
#include

#define PRINTRESULT(array,n,c)  printf(“%d%d\n”,c,getcountinsorted(array,n,c))
#define SIZE 16
int binarysearch(int *array,int n,int value)
{
int low=0,high=n-1,mid=(low+high)/2;
while(low<=high)
{
if(array[mid]==value)
return mid;
if(array[mid]
low = mid+1;
else
high = mid-1;
mid = (low+high)/2;
}
return -1;
}

int getcountinsorted(int *array,int n,int value)
{
int low,high,mid;
mid = binarysearch(array,n,value);
if(mid<0)
return 0;
int right,left;
//Search for the rightmost index
right = mid;
low = mid+1;high = n-1;
int mid1;
while(low<=high)
{
mid1 = (low+high)/2;
if(array[mid1]==value)
{right = mid1;low=mid1+1;}
else if(array[mid1]
low = mid1+1;
else
high = mid1-1;
}
//Search for the leftmost index
low=0;high = mid-1;
left=mid;
while(low<=high)
{
mid1 = (low+high)/2;
if(array[mid1]==value)
{left = mid1; high=mid1-1;}
else if(array[mid1]
low = mid1+1;
else
high = mid1-1;
}
return right-left+1;
}

/* Driver Program to test the above routine */
int main()
{
int array[SIZE] = {1,1,2,2,2,3,4,5,6,7,7,7,7,8,11,11};
PRINTRESULT(array,SIZE,1);
PRINTRESULT(array,SIZE,2);
PRINTRESULT(array,SIZE,3);
PRINTRESULT(array,SIZE,4);
PRINTRESULT(array,SIZE,5);
PRINTRESULT(array,SIZE,6);
PRINTRESULT(array,SIZE,7);
PRINTRESULT(array,SIZE,8);
PRINTRESULT(array,SIZE,9);
PRINTRESULT(array,SIZE,10);
PRINTRESULT(array,SIZE,11);
PRINTRESULT(array,SIZE,12);
return 0;
}

Output:
1 2
2 3
3 1
4 1
5 1
6 1
7 4
8 1
9 0
10 0
11 2
12 0