Sort the elements of an array A in ascending order.

According to wikipedia, the radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers.

How it works: for each digit i where i varies from rightmost digit to the leftmost digit, sort input array using counting sort.

Input data: 13 107 33 5 37 209 110 90

Step 1: compute the maximum value to know the maximum number of digits 

Step 2: usng counting sort, sort according to the rightmost bit
110 90 13 33 5 107 37 209

Step 3: usng counting sort, sort according to the second rightmost bit
5 107 209 110 13 33 37 90

Step 4: usng counting sort, sort according to the leftmost bit
5 13 33 37 90 107 110 209


Difficulty level
This exercise is mostly suitable for students
#include<stdio.h>
#include<conio.h>
#include<limits.h>
#define SIZE 50
void main()
{
	int A[SIZE], N;
	int i, j, max ,exp;
	int count[10]={0};
	int out[SIZE]; // sorted array

	do {
		printf("Enter the dimension: ");
		scanf("%d", &N);
	} while (N <= 0 || N > SIZE);

	for (i = 0; i < N; i++)
	{
	
		printf("Enter A[%d]: ", i);
		scanf("%d", &A[i]);
	}

 	// Radix sort 

	// step 1: Find the maximum number to know number of digits 
	max=INT_MIN;
	for (i = 0; i < N;  i++) 
  		if (A[i] > max)
  			max= A[i];

	// step 2: for every digit do counting sort
	exp=1; // start srom the rightmost digit
	while (max / exp >  0) 
	{

		for (i = 0; i <  10; i++)
  			count[i] =0;

  		for (i = 0; i <  N; i++)
 			count[A[i] / exp %  10]++;
  
		for (i = 1; i <  10; i++)
  			count[i] += count[i -  1];
  
		for (i = N - 1; i  >= 0; i--)
  			out[--count[A[i] / exp  % 10]] = A[i];
  
		for (i = 0; i <  N; i++)
  			A[i] = out[i];
  		exp *= 10;
  	}

	printf("\n\n** After sorting ** \n");
	for (i = 0; i < N; i++)
	{
		printf("A[%d]=%d\n", i, out[i]);
	}

	getch();
}


Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Graph Edge Property