Radix Sort

Radix sort is non-comparative sorting algorithm. The basic idea behind this technique is sort the keys digit by digit, starting from the least significant digit to most significant digit. radix sort is better than counting sort when data sets is too large.we have discussed counting sort at http://wikistack.com/counting-sort  and time complexity is  O(n+k) where n is the number of size of input array and k is the range of input as algorithm implementation takes simple for loops. also it is unstable for string and requires extra space for array. for large data sets counting sort is not good sorting algorithm.

Let us take an example to understand the radix sort algorithm steps:

443   828   605   431   296  439   592   350

“sort the keys digit by digit, starting from the least significant digit to most significant digit”

Step:1     443 828 605 431 296 439 592 350

Step:2     350 431 592 443 605 296 828 439

Step:3     605 828 431 439 443 350 592 296

               296 350 431 439 443 592 605 828

The input array { 443   828   605   431   296  439   592   350} after step 3 becomes sorted {296    350   431   439   443 592   605   828}.

Time  Complexity:

Best case O(nk), Average case O(nk) and worst case O(nk).

Implementation of radix sort by extending counting sort in c:

#include<stdio.h>

const int MAX = 10;

int get_max_element (int *arr, int size);

void radixsort (int arr[], int size)
{
   int i = 0;
    int max_number = get_max_element (arr, size);
//  printf("%d\n",max_number);

int bucket[MAX], position_of_digit = 1;

while (max_number / position_of_digit > 0)
{
    int count[10] = { 0 };
   /*# calculate the histogram of key frequencies*/
    int i = 0;
for (i; i < size; i++)
{
      ++count[arr[i] / position_of_digit % 10];
}

/*calculate the starting index for each key*/
   int total = 0;
   int oldCount = 0;
for (i = 0; i < 10; i++)
{
    oldCount = count[i];
    count[i] = total;
    total += oldCount;
}
/* copy to output array,
preserving order of inputs with equal keys */
 for (i = 0; i < size; i++)
 {
   bucket[count[arr[i] / position_of_digit % 10]] = arr[i];
   count[arr[i]] += 1;
 }
     for (i = 0; i < size; i++)
             arr[i] = bucket[i];

/* choose next positioned digit */
position_of_digit *= 10;
}

/* print output */
for (i = 0; i < size; i++)
          printf ("%4d", arr[i]);
printf ("\n");
}

/* main */
int main ()
{
  int arr[] = { 443, 828, 605, 431, 296, 439, 592, 350 };

  int size = sizeof (arr) / sizeof (arr[0]);
  radixsort (arr, size);
}

/* get largest element */
int get_max_element (int *arr, int size)
{
    int max = arr[0];
    int i = 0;
   for (i = 1; i < size; i++)
   {
        if (arr[1] > max)
        max = arr[1];
   }
return max;
}



Related Contents to follow