For Advertisements on this blog Contact Us at developgram@gmail.com or +91-9923438816

Simple Programming Tutorials For Beginners

Monday, December 12, 2016

Radix Sort

/*
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;
}

No comments:

Post a Comment

SEARCH THIS BLOG