Question

Objective:

     Implement a sorting algorithm.


Description:

     Implement a radix sort in a Java class named RadixSort.java.

Your program should receive its input from a file named "input.txt",
which contains one integer per line.

It should produce a sorted output file named "output.txt".

Include a main method which demonstrates that your algorithm works.

Answer 1

import java.io.*;
import java.util.*;

public class RadixSort {

   // function to get maximum value
   static int maxValue(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]; // output array
       int i;
       int count[] = new int[10];
       Arrays.fill(count,0);

       // Store count of occurrences in count[]
       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 ]--;
       }
       //Copy output array to arra[]
       for (i = 0; i < n; i++)
           arr[i] = output[i];
   }

   // The main function to that sorts arr[] of size n using
   // Radix Sort
   static void radixsort(int arr[], int n)
   {
       // Find the maximum number to know number of digits
       int m = maxValue(arr, n);

       // Do counting sort for every digit. Note that instead
       // of passing digit number, exp is passed. exp is 10^i
       // where i is current digit number
       for (int exp = 1; m/exp > 0; exp *= 10)
           countSort(arr, n, exp);
   }

   // A utility function to print an array
   static void print(int arr[], int n)
   {
       for (int i=0; i<n; i++)
           System.out.print(arr[i]+" ");
   }
  
   public static void writeSortedarray(String fileName,int arr[])
   {
   try {
  
   Writer wr = new FileWriter(fileName);
for (int i = 0; i < arr.length; i++)
{
wr.write(arr[i] + "");
wr.write("\r\n");
}
wr.close();
}
catch (IOException e)
{
System.out.println("Error - " + e.toString());
}
   }
  
public static int[] readIntegers(String fileName)
{
try{
File inputFile=new File(fileName);
Scanner s=new Scanner(inputFile);
int ctr=0;
while(s.hasNextInt())
{
ctr++;
s.nextInt();
}
int[] arr=new int[ctr];
Scanner s1=new Scanner(inputFile);
for (int i=0;i<arr.length;i++)
arr[i]=s1.nextInt();
return arr;
}
catch(Exception ex)
{
return null;
}
}

   /*Driver function to check for above function*/
   public static void main (String[] args)
   {
       int[] arr = readIntegers("input.txt");
   int n = arr.length;
   radixsort(arr, n);
   writeSortedarray("output.txt",arr);
   }
}