/*
Summary: 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.
Two classifications of radix sorts are least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least digit and move towards the most significant digit. MSD radix sorts work the other way around.
Complexity - O(d·n)
*/

#include <stdio.h>
int min = 0, count = 0, array[100] = {0}, array1[100] = {0};

int main()
{
 int k, i, j, temp, t, n;

 printf("Enter size of array :");
 scanf("%d", &count);

 printf("Enter elements into array :");
 for (i = 0; i < count; i++)
 {
  scanf("%d", &array[i]);
  array1[i] = array[i];
 }

 for (k = 0; k < 3; k++)
 {
  for (i = 0; i < count; i++)
  {
                min = array[i] % 10;        /* To find minimum lsd */
   t = i;
   for (j = i + 1; j < count; j++)
   {
    if (min > (array[j] % 10))
    {
     min = array[j] % 10;
     t = j;
    }
   }

   temp = array1[t];
   array1[t] = array1[i];
   array1[i] = temp;
   temp = array[t];
   array[t] = array[i];
   array[i] = temp;
  }

        for (j = 0; j < count; j++)        /*to find MSB */
            array[j] = array[j] / 10;
 }

 printf("Sorted Array (Radix sort) : ");
 for (i = 0; i < count; i++)
  printf("%d ", array1[i]);

 return 0;
}