Radix Sort

Radix Sort

Radix sort is a sorting technique in which sorting can be done by sorting digit by digit starting from least significant digit to most significant digit.

Ex. 6.7.1: Sort the given list of elements using Radix sort

45 37 05 09 06 11 18 27

Sol. :

Step 1: Now sort the element according to the last digit.

Now sort this number

Step 2: Now sort the above array with the help of second last digit.

Since the list of element is of two digit that is why, we will stop comparing. Now whatever list we have got (shown in above array) is of sorted elements. Thus finally the sorted list by radix sort method will be

05  06  09  11  18  27  37  45

Algorithm:

1. Read the total number of elements in the array.

2. Store the unsorted elements in the array.

3. Now the simple procedure is to sort the elements by digit by digit.

4. Sort the elements according to the last digit then second last digit and so on.

5. Thus the elements should be sorted for up to the most significant bit.

6. Store the sorted element in the array and print them.

7. Stop.

Ex. 6.7.2 C Program for sorting elements using radix sort. Sol. :

/**************************************************************

Program for sorting the elements by radix sort.

**************************************************************/

/*Header Files*/

#include<stdio.h>

#include <conio.h>

#include <math.h>

void main()

{ int a[100] [100],r=0,c=0,i,sz,b[50],temp;

clrscr();

printf("Size of array: ");

scanf("%d", &sz);

printf("\n");

for(r=0;r<100;r++)

{

 for(c=0;c<100;c++)

a[r][c]=1000;

}

for(i=0;i<sz;i++)

{ printf("Enter element %d: ",i+1);

scanf("%d", &b[i]);

r=b[i]/100;

c=b[i]%100;

a[r][c]=b[i];

}

for(r=0;r<100;r++)

{ for(c=0;c<100;c++)

{ for(i=0;i<sz;i++)

{ if(a[r][c]==b[i])

{ printf("\n\t");

printf("%d", a[r][c])

}

}

}

}

getch();

}

**********End of Program************

Output

Size of array: 5

Enter element 1: 7

Enter element 2: 5

Enter element 3: 37

Enter element 4: 27

Enter element 5: 29

5

7

27

29

37