c program for radix sort

Solutions on MaxInterview for c program for radix sort by the best coders in the world

showing results for - "c program for radix sort"
Henry
02 Jan 2019
1#include<stdio.h>
2int get_max (int a[], int n)
3{
4   int max = a[0];
5   for (int i = 1; i < n; i++)
6      if (a[i] > max)
7         max = a[i];
8   return max;
9}
10void radix_sort (int a[], int n)
11{
12   int bucket[10][10], bucket_cnt[10];
13   int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
14   lar = get_max (a, n);
15   while (lar > 0)
16   {
17      NOP++; // No of passes
18      lar /= 10; // largest number
19   }
20   for (pass = 0; pass < NOP; pass++)
21   {
22      for (i = 0; i < 10; i++)
23      {
24         bucket_cnt[i] = 0;
25   	  }
26      for (i = 0; i < n; i++)
27      {
28         r = (a[i] / divisor) % 10;
29         bucket[r][bucket_cnt[r]] = a[i];
30         bucket_cnt[r] += 1;
31      }
32      i = 0;
33      for (k = 0; k < 10; k++)
34      {
35         for (j = 0; j < bucket_cnt[k]; j++)
36         {
37            a[i] = bucket[k][j];
38            i++;
39         }
40      }
41      divisor *= 10;
42      printf ("After pass %d : ", pass + 1);
43      for (i = 0; i < n; i++)
44         printf ("%d ", a[i]);
45      printf ("\n");
46   }
47}
48int main ()
49{
50   int i, n, a[10];
51   printf ("Enter the number of items to be sorted: ");
52   scanf ("%d", &n);
53   printf ("Enter items: ");
54   for (i = 0; i < n; i++)
55   {
56      scanf ("%d", &a[i]);
57   }
58   radix_sort (a, n);
59   printf ("Sorted items : ");
60   for (i = 0; i < n; i++)
61      printf ("%d ", a[i]);
62   printf ("\n");
63   return 0;
64}