This sorting algorithm is based on the values of the digits in the positional representation of numbers to be sorted.

For example:
Consider the number 235 in decimal notation It is written with 2 in the hundredth position, 3 in the tenth position and 5 in the units’ position. If we want to find which number is greater between two such numbers, it may be done in the following way: Starting with the least significant digit, we check which number has larger digit. The number with the larger most significant digit is the greater number. If all digits match, the numbers are equal.

This technique is implemented in radix sort algorithm.

The elements are provided in an array. The radix sort algorithm implements a two-dimensional array (queue) with 10 rows with each row acting as a queue. The two pointers required in the queue, front and rear, are declared as arrays of size 10 each (front[10] and rear[10]). The queues are maintained corresponding to the elements in the decimal number system. queue[0][n] is used to store numbers with 0 as the extracted digit and may hold a maximum of n numbers. front[0] and rear[0] are the pointers for queue[0][n].

The algorithm takes each number from the array and extracts the digit from a specific position in the number. The digit is checked and put in the corresponding queue.

When the queues have been filled, the array is repopulated from the queue in the following manner. The elements present in queue[0][n] are put into the array followed by the elements in queue[1][n] and so on until all elements have been returned to the array.

This process is repeated starting from least significant digit to most significant digit.

Let us consider the following example: Considering the following numbers:

	12	98	34	67	54	23	56	45

The algorithm creates the following two queue sets:

Queue based on least significant digit:

		Front			Rear
Queue[0]	
Queue[1]	
Queue[2]	12
Queue[3]	23
Queue[4]	34			54
Queue[5]	45
Queue[6]	56
Queue[7]	67
Queue[8]	98
Queue[9]

After repopulating array:

	12	23	34	54	45	56	67	98

Since the array is not sorted, the process is repeated for the next digit, i.e. the most significant digit.

Queue based on most significant digit:

		Front			Rear
Queue[0]	
Queue[1]	
Queue[2]	12
Queue[3]	23
Queue[4]	34			
Queue[5]	45
Queue[6]	54			56
Queue[7]	67
Queue[8]	98
Queue[9]

After repopulating array:

	12	23	34	45	54	56	67	98

Thus, the array is sorted.

The method responsible for extraction of the digit from a particular position may be indicated by ext(n,p) where n is the number sent for extraction and p is the position from which digit has to be extracted.

The algorithm for the method may be written as:

while (> 0)
{
  d = n%10;
  n = n/10;
  p--;
}
return d;

The method implementing radix sort may be defined as radix(ar[],n,m) where ar[] is the array containing the elements, n is the number of elements present in the array and m is the number of elements present in the greatest element in the array (if some numbers contain lesser number of digits, they are padded with leading zeros).

It performs mainly these functions:

  • The numbers are provided to the ext() method along with position for digit to be extracted
  • The number is put in the queue pointed by the extracted digit
  • The elements in the queues are put back into the array after all the numbers have been checked.
  • It is checked whether the array is sorted or not

These steps are repeated for each digit in the numbers.

The algorithm for the method may be written as:

  for (= 1; i <= m; i++)
  {
    for (= 0; j < n; j++)
    {
      p = ext (ar[j], i);
      queue[p][++rear[p]] = ar[j];
    }
    
10      /* for filling the queues */
11      for (= 0; j < 10; j++)
12      {
13        if (front[j] & ltrear[j])
14        {
15          for (= ++front[j]; k<=rear[j]; k++)
16          {
17            ar[p++] = queue[j][k];
18          }
19        }
20      }
21    
22      /* used for checking whether array is sorted */
23      f = 0; 
24      while (!= (- 1))
25      {
26        if(ar[p] & gtar[p+1])
27        {
28          f = 1;
29          break;
30        }
31        p++;
32      }
33      if(== 0)
34      {
35        break;
36      }
37    }/* end of for */
38 

The time requirement for the radix sorting method depends on the number of digits (m) and the number of elements in the array (n). Since the outer loop for(i=1;i<=m;i++) is traversed m times and inner loop is traversed n times, the sort is approximately O(m*n). this sort is reasonably efficient when the number of digits in the numbers is small.

Full working code of radix sort written in C language

/* Radix Sort */
/* Arranges a set of numbers entered by the user in ascending order */
/* To arrange in descending order, fill array starting with queue[9] */
#include <stdio.h>
#include <conio.h>
/* extracts element at pth position */
int ext(int n, int p)
10  {
11    int d;
12    while(p & gt0)
13    {
14      d = n % 10;
15      n = n / 10;
16      p--;
17    }
18    return d;
19  }
20 
21  /* performs radix sort */
22  void radix(int ar[], int n, int m)
23  {
24    int queue[10][100];
25    int front[10], rear[10];
26    int i, j, k, p, f;
27    for (= 1; i <= m; i++)
28    {
29      for (= 0; j < 10; j++)
30      {
31        front[j] =- 1;
32        rear[j] =- 1;
33      }
34      for (= 0; j < 10; j++)
35      {
36        for (= 0; k < 100; k++)
37        {
38          queue[j][k] = 0;
39        }
40      }
41 
42      /* for determining element belongs to which queue */
43      for (= 0; j < n; j++)
44      {
45        p = ext(ar[j], i);
46        queue[p][++rear[p]] = ar[j];
47      }
48      p = 0;
49 
50      /* used to repopulate the array */
51      /* for descending order, use for(j=9;j>=0;j--) */
52      for( j = 0; j < 10; j++)
53      {
54        if(front[j] < rear[j])
55        {
56          for (= ++front[j]; k <= rear[j]; k++)
57          {
58            ar[p++] = queue[j][k];
59          }
60        }
61      }
62    
63      /* used for checking whether array is sorted */
64      f = 0;
65      p=0;
66      while(!= (- 1))
67      {
68        if(ar[p] & gtar[p + 1])
69        {
70          f = 1;
71          break;
72        }
73        p++;
74      }
75      if (== 0)
76      {
77        break;
78      }
79    }
80  }
81  int main (int argc, char *argv[])
82  {
83    int i, n, m, ar[100];
84    printf ("\nEnter number of elements:");
85    scanf ("%d", &n);
86    printf (\“\nEnter size of maximum element:\”);
87    scanf ("%d", &m);
88    printf ("\nEnter elements:\n");
89    for (= 0; i < n; i++)
90    {
91      scanf ("%d", &ar[i]);
92    }
93    radix (ar, n, m);
94    printf ("\nSorted elements are:");
95    for (= 0; i < n; i++)
96    {
97      printf ("%d ", ar[i]);
98    }
99    return 0;
100  }
101 

You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.

 Vote 0

Similar topics related to this section

Selection Sort, Insertion Sort, Quick Sort, Heap Sort, Merge sort, Radix Sort, argc and argv, C startup routine, argv environ getenv,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan