Question #1: Implement (in Java) the RadixSort algorithm to sort (in increasing
ID: 3705946 • Letter: Q
Question
Question #1:
Implement (in Java) the RadixSort algorithm to sort (in increasing order) an array of nonnegative integer keys.
public void radixSort(int arr[])
In your implementation you must consider that each key contains only even digits (0, 2, 4, 6, and 8). Your program must detect the case of odd digits in the keys, and, in this case, your program must replace each odd digit by the greater even digit that is less than the odd digit. Examples: 3 > 2; 9 > 8; 1 > 0;
Example of the output of the program:
Input array: 13, 4680, 24062, 51, 86, 642, 51, 426, 888,
After preprocessing (convert odd digits into even digits): 2, 4680, 24062, 40, 86, 642, 40, 426, 888,
Sorted array: 2, 40, 40, 86, 426, 642, 888, 4680, 24062,
Note: To storage and process the bucket lists, use an ArrayList structure.
Question #2:
What is the running time complexity of your radixSort method?
Explanation / Answer
import java.util.Random;
// Class BucketSort definition
class BucketSort
{
int originalNumbers[];
// Default constructor
BucketSort(int arr[])
{
// Dynamically allocates memory of size n
originalNumbers = new int[arr.length];
// Loops n times
for (int c = 0; c < arr.length; c++)
// Generates random number and stores it in array
originalNumbers[c] = arr[c];
}// End of constructor
// Method to return the sorted array
int[] sort(int maxValue)
{
// Crates an array to store the original numbers
int[] bucketOri = new int[maxValue + 1];
// Crates an array to store the sorted numbers
int[] bocketArray = new int[originalNumbers.length];
// Loops till the length of the original array
for (int c = 0; c < originalNumbers.length; c++)
// bocketOri's index position is originalNumbers c index position value add one to it
bucketOri[originalNumbers[c]]++;
// Initializes pass to zero
int pass = 0;
// Loops till length of the bucketOri array
for (int c = 0; c < bucketOri.length; c++)
// Loops till length of the bucketOri c index position value
for (int d = 0; d < bucketOri[c]; d++)
// Assigns c value at the pass index position of bocketArray
bocketArray[pass++] = c;
// Returns the sorted bocketArray
return bocketArray;
}// End of method
// Method to display the array
void printNumbers(int[] numbers)
{
// Loops till length of the numbers array
for (int c = 0; c < numbers.length; c++)
// Displays each element
System.out.print(numbers[c] + ", ");
}// End of method
// Method to return maximum value
int numberOfDigits()
{
// Initializes the maximum value to zero
int maxValue = 0;
// Loops till length of the numbers array
for (int c = 0; c < originalNumbers.length; c++)
// Checks if the current index position value is greater than the earlier maxValue
if (originalNumbers[c] > maxValue)
// Set the maxValue to array current index position value
maxValue = originalNumbers[c];
// Returns maximum value
return maxValue;
}// End of method
}// End of class
// Driver class BucketSortTest definition
public class BucketSortTest
{
// Static method to accept an array
// Converts each number each odd digit by its minus one value
static void numberConverter(int arr[])
{
// Loops till length of the array
for(int x = 0; x < arr.length; x++)
{
// Stores the array x index position value in no
int no = arr[x];
// To store the new number
int newNo = 0;
// To store the reverse number
int revNo = 0;
// Status for odd digit found in number
int flag = 0;
// Reverse the number
// Loops till number not equals to zero
while(no != 0)
{
// Calculates the reverse of the number
// (no % 10) for remainder
revNo = revNo * 10 + (no % 10);
// Stores the quotient
no /= 10;
}// End of while loop
// Odd digit replacement
// Loops till number not equals to zero
while(revNo != 0)
{
// Stores the remainder
int r = revNo % 10;
// Checks if the remainder is odd
if(r % 2 != 0)
{
// Set the flag to 1
flag = 1;
// Subtracts one from the remainder
r = r - 1;
// Generates new number
newNo = newNo * 10 + r;
}// End of if condition
// Stores the quotient
revNo /= 10;
}// End of while loop
// Checks if flag is one then odd digit found
if(flag == 1)
// Stores the new converted number in array x index position
arr[x] = newNo;
}// End of for loop
}// End of method
// main method definition
public static void main(String s[])
{
// Creates an array
int arr[] = {13, 4680, 24062, 51, 86, 642, 51, 426, 888};
// Calls the method to replace odd digit by minus one value
numberConverter(arr);
// Creates BucketSort object with parameterized constructor
BucketSort b = new BucketSort(arr);
// Calls the method to get the maximum value from the array
int maxValue = b.numberOfDigits();
// Calls the method to display the original array
System.out.println(" Original Array: ");
b.printNumbers(b.originalNumbers);
// Calls the method to display the sorted array
System.out.println(" Sorted Array: ");
// Calls the method to sort the array and display it
b.printNumbers(b.sort(maxValue));
}// End of main method
}// End of class
Sample Output:
Original Array:
2, 4680, 24062, 40, 86, 642, 40, 426, 888,
Sorted Array:
2, 40, 40, 86, 426, 642, 888, 4680, 24062,