Probiem 1: The radix sort algorithm sorts an array of n integers using ten auxil

Question

Probiem 1: The radix sort algorithm sorts an array of n integers using ten auxiliary arrays. First place each value v into the auxiliary array whose index corresponds to the last digit of v. Then move all values back into the original array, preserving their order. Repeat the process, no using the next-to-last (tens) digit, then the hundreds digit, and so on. Implement the radx sort algorithm to sort arrays of integers. For simplicity, you can assume the integers are all positive and between 0 and 9999. The numbers should be loaded from the provided sample file numberlist.txt.

Explanation / Answer

Code for your problem.

I have used file.txt as source file......

------------------------------------------------------CODE----------------------------------------------

import java.io.*;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;

public class Radix {

// A utility function to get maximum value in arr[]
static int getMax(int arr[], int n)
{ //tells about the maximum length/itration we have to traverse
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}

// A function to do counting sort of arr[] according to
// the digit represented by exp.
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; // output array
int i;
int count[] = new int[10]; // AUXILLIARY ARRAY
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 the output array to arr[], so that arr[] now
// contains sorted numbers according to curent digit
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 = getMax(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);
}

// MAIN FUNCTION
public static void main(String[] args) throws IOException
{
Path fp = Paths.get("file.txt");
Scanner scan = new Scanner(fp);

List<Integer> data = new ArrayList<Integer>();

while (scan.hasNext()) {
if (scan.hasNextInt()) {
data.add(scan.nextInt());
}
else
{
scan.next();
}
}
  
  
int arr[] = new int[data.size()];

for (int i =0; i < data.size(); i++)
arr[i] = data.get(i);

  
int n = arr.length;
radixsort(arr, n);

// Printing the resultant array
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");

}
}

----------------------------------------------

It is working fine.

Create your own file and run it . THANKSSS

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.