Can you help me with this Java Program?

Sorting and Searching

Part A - Sorting

In the first part of this assignment, you will implement a radix sort algorithm. Radix sort does not use direct key comparison to arrange data. Instead, repeated passes are made over the data and a selected piece of each data item is used to order the data.

The following example illustrates the process using binary data. The radix sort begins by examining the least significant digit (LSD) of each item. The digit is extracted and the data set is divided into two bins (for radix = 2, bin 0 and bin 1) based on the value of the least significant digit. After separating all the data items into the two bins, the content of the bins is combined (elements in bin 0 followed by elements in bin 1) and the process is repeated for next most significant digit. This process is repeated until all the digits are examined. Study the example shown below. The sorted data set appears in the rightmost column.

Original Data	Sort on Bit 0	Combine Bins	Sort on Bit 1	Combine Bins	Sort on Bit 2	Combine Bins	Sort on Bit 3	Combine Bins
0101 1011 0100 1100	Bin 0 0100 1100	0100 1100 0101 1011	Bin 0 0100 1100 0101	0100 1100 0101 1011	Bin 0 1011	1011 0100 1100 0101	Bin 0 0100 0101	0100 0101 1011 1100
	Bin 1 0101 1011		Bin 1 1011		Bin 1 0100 1100 0101		Bin 1 1011 1100

Your task is to develop a radix sort function and test program that takes an unsorted array of positive integer values and sorts the data using a radix sort. Your program must have the following features:

Inside main, create the array of size 100 and fill it with random numbers between 0 and 10000.

Create a radix sort function (this will be a static method within your test program) that takes the array to be sorted as a parameter. Use radix 10 for your sort function.

Create the storage needed based on the value of the radix for radix 10, you need 10 buckets

Calculate the number of digits the max value from the array contains using the radix as a base. This will determine the number of times your outer loop will execute.

Ie. 942 base 10 has 3 digits. The base (10) raised to the 3^rd power is the smallest power larger than the number

For each digit, least significant to most significant, map the numbers from the array into the buckets based on the digit

After splitting into buckets, copy the values from the buckets back into the original array

When the outer loop has completed, the array will be sorted

Display the contents of the array before and after sorting (10 values per line). Verify that the data is properly sorted.

Part B - Searching

There are many techniques for searching for data values in a set of data. The simplest technique is a linear search that on average requires an amount of time directly proportional to the size of the data set to find a specific value. A linear search compares the search value to each item in the data set in series until the desired value is located or until the entire data set is examined. If the data set is sorted, a better solution is to apply a binary search technique that locates values in time proportional to the log of the number of items in the data set. In a binary search, the sorted data set is split in the middle and the search value is compared to the middle data value. If the search value matches the middle data value, the search terminates. If the search value is less than the middle data value, the search continues with the data segment containing the smaller data values, otherwise it continues with the data segment with the larger values. An even better approach for searching large sorted data sets is to use an interpolation search that on average requires time proportional to the log of the log of the size of the data set to find a data value.

An interpolation search is similar to a binary search. The technique selects a position to split the data set. If the search value is equal to the value at the split position, the search terminates. If the search value is less than the data value at the split position, the search continues with the data segment containing the smaller data values, otherwise it continues with the data segment with the larger values. The choice of the position to split the array is based on the data values in the array. For example, suppose we have an array called DATA of ten double precision data values:

0	1	2	3	4	5	6	7	8	9
2.0	5.1	6.5	8.1	10.1	12.5	13.3	15.1	16.7	17.0

To search for the data value 16.7, we would compute a fraction that estimates the position of 16.7 in the series of numbers from 2.0 to 17.0. For this example,

lb = 0 // lower bound of the segment of the array

ub = 9 // upper bound of the segment of the array

sv = 16.7 // search value

dvlb = DATA[lb] // data at the position specified by the lower bound

dvub = DATA[ub] // data at the position specified by the upper bound

sp = lb + ( ( sv dvlb) / ( dvub dvlb ) ) * ( ub lb )

= 0 + ( ( 16.7 2.0 ) / ( 17.0 2.0 ) ) * ( 9 0 )

= (int)8.82 = 8

The interpolation search would begin with position eight (8). Since the search value is found immediately, the search terminates. If the value in position eight was not the search value, the search would continue with the array segment from DATA[0]DATA[7] or the segment from DATA[9]DATA[9].

NOTE: Be aware that this search requires that the value being searched for is between the lowest value in the array and the highest value in the array: lowest value <= search value <= highest value. Your search function should verify that the value being searched for is within this range when the search method is called.

As Part B of this lab, add interpolation search to the program from Part A with the following requirements:

1. Add a static method for doing interpolation search to Part A of this lab. This method is implemented using recursion (no loop). The recursive method has 4 parameters: the array to search, the lower and upper index position which identify the part of the list to be searched, and the value to search for. The method returns the index of where the value is found or -1 to indicate the value is not in the array.

2. The test cases are added in main following the test cases from Part A. The sorted array from Part A will be used as the array to be searched. Make sure your test cases include the following searches:

First value in the array

Last value in the array

Somewhere near the middle in the array

Less than the first value

More than the last value

Some value near the middle not in the data

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

You are not permitted to use any static variables.

Part A Rubric [17 pts]:

Create the array and fill it with random data as described above. (2 pts)

Display the array content 10 values per line before and after sorting. (3 pts)

The radix sort method takes an array and correctly sorts the data using radix 10. (10 pts)

Use proper programming style and commenting. (2 pts)

Part B Rubric [18 pts]:

Recursive interpolation search method returns correct results (10 pts)

All test cases described above (6 pts)

Use proper programming style and commenting. (2 pts)