Answers for "radix sort program in c"

c program for radix sort

#include<stdio.h>
int get_max (int a[], int n)
{
   int max = a[0];
   for (int i = 1; i < n; i++)
      if (a[i] > max)
         max = a[i];
   return max;
}
void radix_sort (int a[], int n)
{
   int bucket[10][10], bucket_cnt[10];
   int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
   lar = get_max (a, n);
   while (lar > 0)
   {
      NOP++; // No of passes
      lar /= 10; // largest number
   }
   for (pass = 0; pass < NOP; pass++)
   {
      for (i = 0; i < 10; i++)
      {
         bucket_cnt[i] = 0;
   	  }
      for (i = 0; i < n; i++)
      {
         r = (a[i] / divisor) % 10;
         bucket[r][bucket_cnt[r]] = a[i];
         bucket_cnt[r] += 1;
      }
      i = 0;
      for (k = 0; k < 10; k++)
      {
         for (j = 0; j < bucket_cnt[k]; j++)
         {
            a[i] = bucket[k][j];
            i++;
         }
      }
      divisor *= 10;
      printf ("After pass %d : ", pass + 1);
      for (i = 0; i < n; i++)
         printf ("%d ", a[i]);
      printf ("n");
   }
}
int main ()
{
   int i, n, a[10];
   printf ("Enter the number of items to be sorted: ");
   scanf ("%d", &n);
   printf ("Enter items: ");
   for (i = 0; i < n; i++)
   {
      scanf ("%d", &a[i]);
   }
   radix_sort (a, n);
   printf ("Sorted items : ");
   for (i = 0; i < n; i++)
      printf ("%d ", a[i]);
   printf ("n");
   return 0;
}

radix sort pseudocode

import java.io.*; 
import java.util.*; 
class Radix { 
           static int getMax(int arr[], int n){ 
           int mx = arr[0]; 
           for (int i = 1; i < n; i++) 
                 if (arr[i] > mx) 
                        mx = arr[i]; 
           return mx; 
    } 
   static void countSort(int arr[], int n, int exp) 
    {   
           int output[] = new int[n]; 
           int i; 
           int count[] = new int[10]; 
           Arrays.fill(count,0);
           for (i = 0; i < n; i++) 
                   count[ (arr[i]/exp)%10 ]++; 
           // Change count[i] so that count[i] now contains 
           // actual position of this digit in output[] 
           for (i = 1; i < 10; i++) 
                   count[i] += count[i - 1]; 
           // Build the output array 
           for (i = n - 1; i >= 0; i--){
                   output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
                   count[ (arr[i]/exp)%10 ]--; 
        }
           for (i = 0; i < n; i++) 
                   arr[i] = output[i]; 
    } 
   static void radixsort(int arr[], int n) 
       { // Find the maximum number to know number of digits 
           int m = getMax(arr, n);
           for (int exp = 1; m/exp > 0; exp *= 10) 
                  countSort(arr, n, exp); 
    } 
   static void print(int arr[], int n) 
    { 
        for (int i=0; i<n; i++) 
               System.out.print(arr[i]+" "); 
    } 
    public static void main (String[] args) 
    {    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; 
         int n = arr.length; 
         radixsort(arr, n); 
         print(arr, n); 
    } 
} 
JavaCopy

radix sort pseudocode

Radix-Sort(A, d)
       for j = 1 to d do
            int count[10] = {0};
            for i = 0 to n do
                count[key of(A[i]) in pass j]++
            for k = 1 to 10 do
                count[k] = count[k] + count[k-1]
            for i = n-1 downto 0 do
                result[ count[key of(A[i])] ] = A[j]
                count[key of(A[i])]--
            for i=0 to n do
                A[i] = result[i]
       end for(j)
 end func