radix sorting in c programming - data structures and algorithms
October 8, 2022

Radix sorting in C Programming

RADIX SORTING:– A radix sort also called Bucket sort is the method used by most people when sorting a list of namesphabetic order. The procedure we follow: (a) First the names are grouped according to the first letter, thus the names are arranged in 26 classes, one for each letter of the alphabet. The first class consists of those names that begin with the letter A, the second class consists of those names that begin with the letter B, and so on. (b) Next, the nates are grouped according to the second letter. After this step, the list of names will be sorted by the first two letters (c) This process is continued a number of times depending on the length of the names with maximum letters.


If shorter names, we assume those names are padded with blanks. Since there are 26 letters of the alphabet, we make use of 26 buckets, one for each letter of the alphabet. After grouping these names according to their specific letter, we collect them in order of buckets i.e. first we pick up names from the first bucket (for letter A), then from the second bucket (for letter B), and so on. This new list becomes the input for the next pass i.e. to separate them on the next letter from the left. To sort decimal numbers, where radix or base is 10, we need ten buckets.


These buckets are numbered 0,1,2,3,4,5,6,7,8,9. Unlike sorting names decimal numbers are sorted from right to left i.e. first on the unit digit, then on the tens digit, then on the hundredth digit, and so on. The above process is to be repeated a number of times depending on the number of digits in the largest number. The smaller numbers are treated as filled with leading zeroes and they will go to bucket number 0. And secondly, the number appearing at the bottom of the bucket has a smaller index, and while collecting the numbers it is collected first. Thus from the above discussion, we conclude that bucket sort performs Well only when the number of digits in the elements is very small.


 

Algorithm for Radix Sorting in c programming.

RADIX_SORT (A, N)

Here A is an array with N elements. This algorithm sorts the array A with N elements in ascending order. We have assumed that the first index of the array is 0.

1.  [Calling of MAX Function]

         Call MAX (A. N. MAXITEM)

2.  (Calling of DIGIT_COUNT Function]

         Call DIGIT COUNT (MAXITEM, D).

3.  Repeat Steps 4 to 7 For K: = 1 to D:

         [Initialize MAT array with infinite]

4.      Repeat Steps For I: = 0 to 9:

              (a) Repeat Steps For J: 0 to N – 1:

                        Set MAT [I] [J] = infinite,

              [End of Step (a) loop.]

         [End of Step 4 loop.]

5.      Repeat Steps For I: = 0 to N – 1:

             (a) [Calling of DIGIT Function]

                        Call DIGIT (A [I], K, ROW).

             (b) Set COL: = 0.

             (c) Repeat Steps While MAT [ROW] [COL] != infinite

                       Set COL:= COL + 1.

              [End of Step (c) loop.]

              (d) Set MAT [ROW] [COL]: = A [I].

              (e) Set I: = I + 1.

           [End of Step 5 loop.]

6.      Set L: = 0.

7.      Repeat Steps For 1: = 0 to 9:

             (a) Repeat Steps For = 0 to N – 1:

                      MAX (A, N, MAXITEM)

                      If MAT [I][J] != infinite, then:

                             (i) Set A [L] = MAT [I] [J].

                             (ii) Set L = L + 1.

                      [End of if structure.]

              [End of Step (a) loop.]

          [End of Step 7 loop.]

     [End of Step 3 loop.]

8.  Return.


MAX (A, N, MAXITEM)

Here A is an array with N elements. This algorithm finds the maximum of N elements in A and assigns it to MAXITEM.

1.  Set MAXITEM: = 0.

2.  Repeat Steps 3 and 4 For I: = 1 to N:

3.      If A [I] > MAXITEM, then:

              Set MAX: = A [I].

         [End of if structure.]

4.      Set I: = I + 1.

      [End of Step 2 loop.]

5.  Return


DIGIT_COUNT (MAXITEM, COUNT)

1.  Set COUNT: = 0.

2.  Repeat Steps 3 and 4 While MAXITEM != 0:

3.      Set MAXITEM: = INT (MAXITEM / 10).

4.      Set COUNT = COUNT + 1.

      [End of Step 2 loop.]

5.  Return


DIGIT (N, I, DIG)

1.  Set DIG: = 0.

2.  Repeat Steps 3 and 4 For J: = 1 to I:

3.      Set DIG:= N MOD 10.

4.      Set N = N / 10.

     [End of Step 2 loop.]

5.  Return.


Radix sorting program in c programming.

#include<stdio.h>
#include<conio.h>
#define SIZE 10
void radix_sort(int [], int);
int max(int [],int);
int cnt_digit(int);
int digit(int,int);

void main()
{
    int a[SIZE],n,i;
    clrscr();
    printf("Enter how many elements");
    scanf("%d",&n);

    /*input array*/

    for(i=0;i<n;i++)
    {
        printf("Enter element %d ",i+1);
        scanf("%d",&a[i]);
    }

    radix_sort(a,n);

    /*Output Array */

    for(i=0;i<n;i++)
        printf("%dn",a[i]);

    getch();
}

void radix_sort(int a[], int n)
{
    int max[10][SIZE],i,j,k,l,row,col,m,d;
    m = max(a,n);
    d = cnt_digit(m);

    for(k=1;k<=d;k++)
    {
        /* initialize matrix with sentinel value - 1 */

        for(i=0;i<10;i++)
            for(j=0;j<n;j++)
                max[i][j] = -1;

        /* copy array A to matrix mat */

        for(i=0;i<n;i++)
        {
            row = digit(a[i],k);
            col = 0;
            while(mat[row][col] != -1)
                col++;
                mat[row][col] = a[i];
        }
        
        /*copy matrix to array except sentinel value - 1 */
        l=0;
        for(i=0;i<10;i++)
            for(j=0;j<n;j++)
                if(mat[i][j] != -1)
                    a[l++] = mat[i][j];
    }
}

int max(int a[], int n)
{
    int m,i;
    m = a[0];

    for(i=1;i<n;i++)
    {
        if(a[i] > m)
        m = a[i];
    }
    return (m);
}

int cnt_digit(int n)
{
    int c = 0;
    while(n>0)
    {
        c++;
        n = n/10;
    }
    return(c);
}

int digit(int n, int k)
{
    int a,i=1;
    while(i<=k)
    {
        a = n % 10;
        n = n / 10;
        i++;
    }
    return(a);
}

Also, Read

  1. Sorting Techniques in Data Structures
  2. Selection sorting in C Programming
  3. Bubble Sorting in C Programming
  4. Insertion Sorting in C Programming
  5. Shell Sorting in C Programming
  6. Merge Sorting in C Programming
  7. Quick Sorting in C Programming
  8. Heap Sorting in C Programming
  9. Selection Sorting Algorithm