Radix sort

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

Numbers and decimal digits

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.

radix decimal digits

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.

Algorithm

This technique is implemented in radix sort algorithm.

The elements are populated in an array. The radix sort algorithm implements a 10 rows of queues. The queues are maintained corresponding to the elements in the decimal number system. Queue[0] is for holding numbers whose digits ends with 0. Similarly queue[1] to queue[9] are for holding digits 1 - 9.

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. Queue process starts with digit 0 till 9

Now all the queues are filled. It is time to dequeue the numbers and put those back to array. Dequeue is done in the same order, starting from zero till 9. Now the array is repopulated with numbers based on the rank of the digit position.

This process is repeated starting from least significant digit to most significant digit. Once the above process completes for the the most significant digit, it completes the sorting process.

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:

Radix sort digit position ones
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 highest number in the array (98) has two digits, the process is repeated for the next digit, i.e. the most significant digit.

Queue based on most significant digit:

Radix sort digit position tens
Queue [0] :
Queue [1] : 12,
Queue [2] : 23,
Queue [3] : 34,
Queue [4] : 45,
Queue [5] : 54, 56,
Queue [6] : 67,
Queue [7] :
Queue [8] :
Queue [9] : 98,

After repopulating array:

	12	23	34	45	54	56	67	98

Thus, the array is sorted.

Extract Digits

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

The algorithm for the method may be written as:

int get_digit_at(int number, int position)
{
  int digit;
  while (position > 0)
  {
    digit = number % 10;
    number = number / 10;
    position--;
  }
10    return digit;
11  }
12 

Radix sort implementation

The method implementing radix sort may be defined as radix_sort(int elements[], int count) where elements[] is the array containing the elements, count is the number of elements present in the array. This function calculates the highest number and the digits present in that number.

It performs mainly these functions in a loop:

  • The numbers are provided to the get_digit_at(int number, int position) 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.

These steps are repeated from digits in zero th position till the highest digit in the max number present in the array.

The algorithm for the method may be written as:

void radix_sort(int elements[], int count)
{
  /* 10 queues for sorting digits */
  queue <int> *q[10];
  int i, j, k, digits, max = -2147483648;
  /* Determine max number */
10    for (= 0; i < count; i++)
11    {
12 
13      if (elements[i] > max)
14      {
15        max = elements[i];
16      }
17    }
18    i = 0;
19    /* Determine max decimal digits */
20    while (max)
21    {
22      max = max /10;
23      i++;
24    }
25    digits = i;
26 
27    /* Take elements from digit = 0 to max digit and sort */
28    for (= 0; i < digits; i++)
29    {
30      /* Initialize queue */
31      for (int j=0; j < 10; j++)
32      {
33        q[j] = new queue<int>;
34      }
35      /* Populate the queue(s) based on digit */
36      for ( k=0; k < count; k++)
37      {
38        /* get the digit */
39        int digit = get_digit_at(elements[k], i+1);
40 
41        /* enqueue at the rare of digit's queue */
42        q[digit]->push(elements[k]);
43      }
44      /* Dequeue individual queues to elements array */
45      k = 0;
46      for ( j=0; j < 10; j++)
47      {
48        while (!q[j]->empty())
49        {
50          /* dequeue from front */
51          elements[k] = q[j]->front();
52          q[j]->pop();
53          k++;
54        }
55 
56      }
57      /* Cleanup the queues */
58      for ( j=0; j < 10; j++)
59      {
60        delete q[j];
61      }
62    }
63  }
64 

Time complexities

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

Source code

Full working code of radix sort written in C language however we have utilizes C++ STL queue class for simplicity.

/* Radix sort CPP file */
#include <iostream>
#include <queue>
#include <list>
using namespace std;
int array[]={2000,300, 256, 12, 98, 34, 67, 54, 23, 56, 45};
char * radix_positios [] = {
10    "ones", "tens", "hundreds", "thousands", 
11    "ten thousands", "hundred thousands", "millions"
12 
13  };
14 
15  /* get the digit at position */
16  int get_digit_at(int number, int position)
17  {
18    int digit;
19    while (position > 0)
20    {
21      digit = number % 10;
22      number = number / 10;
23      position--;
24    }
25    return digit;
26  }
27  /* print the entire number array */
28  void print_array(int elements[], int count)
29  {
30 
31    printf("Element :");
32    for (int index = 0; index < count; index ++)
33    {
34      printf("%d, ",elements[index]);
35    }
36    printf("\n");
37  }
38 
39  /* Radix sort algorithm */
40  void radix_sort(int elements[], int count)
41  {
42 
43    /* 10 queues for sorting digits */
44    queue <int> *q[10];
45    int i, j, k, max = -2147483648;
46 
47    /* Determine max number */
48    for (= 0; i < count; i++)
49    {
50 
51      if (elements[i] > max)
52      {
53        max = elements[i];
54      }
55    }
56    i = 0;
57    /* Determine max decimal digits */
58    while (max)
59    {
60      max = max /10;
61      i++;
62    }
63    max = i;
64 
65    /* Take elements from digit = 0 to max digit and sort */
66    for (= 0; i < max; i++)
67    {
68 
69      printf("Radix sort position %s\n",
70              (< 7 )? radix_positios[i] : "");
71      /* Initialize queue */
72      for (int j=0; j < 10; j++)
73      {
74        q[j] = new queue<int>;
75      }
76      /* Populate the queue(s) based on digit */
77      for ( k=0; k < count; k++)
78      {
79        /* get the digit */
80        int digit = get_digit_at(elements[k], i+1);
81 
82        /* enqueue at the rare of digit's queue */
83        q[digit]->push(elements[k]);
84      }
85      /* Dequeue individual queues to elements array */
86      k = 0;
87      for ( j=0; j < 10; j++)
88      {
89        printf("Queue [%d] : ", j);
90        while (!q[j]->empty())
91        {
92          /* dequeue from front */
93          elements[k] = q[j]->front();
94          q[j]->pop();
95          printf("%d, ", elements[k]);
96          k++;
97        }
98        printf("\n");
99 
100      }
101      /* Cleanup the queues */
102      for ( j=0; j < 10; j++)
103      {
104        delete q[j];
105      }
106      print_array(elements, count);
107    }
108  }
109  int main(int argc, char* argv[])
110  {
111    /* print unsorted array */
112    printf("Radix sort\n");
113    print_array(array, 11);
114 
115    /* run radix sort */
116    radix_sort(array, 11);
117 
118    /* print sorted array */
119    printf("Radix sorted array\n");
120    print_array(array, 11);
121    return 0;
122  }

Output

Radix sort
Element :12, 98, 34, 67, 54, 23, 56, 45,
Radix sort position ones
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] :
Element :12, 23, 34, 54, 45, 56, 67, 98,
Radix sort position tens
Queue [0] :
Queue [1] : 12,
Queue [2] : 23,
Queue [3] : 34,
Queue [4] : 45,
Queue [5] : 54, 56,
Queue [6] : 67,
Queue [7] :
Queue [8] :
Queue [9] : 98,
Element :12, 23, 34, 45, 54, 56, 67, 98,
Radix sorted array
Element :12, 23, 34, 45, 54, 56, 67, 98,
Press any key to continue

Output

Radix sort
Element :2000, 300, 256, 12, 98, 34, 67, 54, 23, 56, 45,
Radix sort position ones
Queue [0] : 2000, 300,
Queue [1] :
Queue [2] : 12,
Queue [3] : 23,
Queue [4] : 34, 54,
Queue [5] : 45,
Queue [6] : 256, 56,
Queue [7] : 67,
Queue [8] : 98,
Queue [9] :
Element :2000, 300, 12, 23, 34, 54, 45, 256, 56, 67, 98,
Radix sort position tens
Queue [0] : 2000, 300,
Queue [1] : 12,
Queue [2] : 23,
Queue [3] : 34,
Queue [4] : 45,
Queue [5] : 54, 256, 56,
Queue [6] : 67,
Queue [7] :
Queue [8] :
Queue [9] : 98,
Element :2000, 300, 12, 23, 34, 45, 54, 256, 56, 67, 98,
Radix sort position hundreds
Queue [0] : 2000, 12, 23, 34, 45, 54, 56, 67, 98,
Queue [1] :
Queue [2] : 256,
Queue [3] : 300,
Queue [4] :
Queue [5] :
Queue [6] :
Queue [7] :
Queue [8] :
Queue [9] :
Element :2000, 12, 23, 34, 45, 54, 56, 67, 98, 256, 300,
Radix sort position thousands
Queue [0] : 12, 23, 34, 45, 54, 56, 67, 98, 256, 300,
Queue [1] :
Queue [2] : 2000,
Queue [3] :
Queue [4] :
Queue [5] :
Queue [6] :
Queue [7] :
Queue [8] :
Queue [9] :
Element :12, 23, 34, 45, 54, 56, 67, 98, 256, 300, 2000,
Radix sorted array
Element :12, 23, 34, 45, 54, 56, 67, 98, 256, 300, 2000,
Press any key to continue

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

 Vote 0