Please code alll in Java$-------$For this assignment you are going to implement several sorting algorithms.

RESTRICTIONS:

$-$ You may NOT import java.util.Comparator

o you must write your own comparators

$-$ You may NOT import java.util.Arrays

o You must write your own copy methods for any arrays

o You may NOT use any of the Java Array sorting features.

o You may NOT use any of the Java Array copying features.

$$ Exception, the textbook code for the mergeSort uses the Arrays.copyOfRange method. You use this method but only in the mergeSort method.

$-$ You may NOT import any other Java container class.

o e$.$g$.$ you must use your own Queue class.

Task $1$:

Create an employee Class that encapsulates the concept of an employee. The attributes of an employee are:

$-$ id

o a random integer in the range $0$ to $99999999($i$.$e$.$ like a social security number$)$

o we will ignore the fact that we may get duplicate id numbers

$-$ name

o a String of a random length between $5$ and $10$ characters $($inclusive$)$ made up of a random set of lower case characters

$-$ dept

o a random integer in the range $1$ to $5($inclusive$)$

$-$ hired

o a random integer in the range $2008$ to $2018($inclusive$)$

Task $2$:

Create a class named Sort that will act as a container for the following generic array sorting algorithms:

$-$ simpleBubbleSort

o a brute force bubble sort that just uses a pair of nested loops

o this needs to be a generic bubble sort

o this needs to be a stable sort

$-$ enhancedBubbleSort

o a bubble sort that only sorts the unsorted portion of the array on each pass through the inner loop

o a bubble sort that stops as soon as it knows the list is sorted

o this needs to be a generic sort

o this needs to be a stable sort

$-$ insertionSort

o the insertion sort as discussed in class

o you may use the code from the Java Illuminated text modified to be generic

o make sure it is a stable sort

$-$ selectionSort

o the insertion sort as discussed in class

o you may use the code from the Java Illuminated text modified to be generic

o make sure it is a stable sort

$-$ mergeSort

o this must be one of the mergeSort methods described in the textbook

o make sure it is a stable sort

o you may have to modify this code

$-$ quickSort

o this must be the quickSort methods described in the textbook

o make sure it is a stable sort

o you may have to modify this code

$-$ radixSort

o this should be the radix sort describe in class

o this should be a generic sort

o the radixSort should be able to support between two and four keys

o the first parameter in the parameter list should be the array being sorted.

o the remaining parameters in the parameter list should be the keys, ordered left to right from most significant to least significant

o you should use the Radix sort described in class and not the bucket approach described in the textbook

Task $3$:

$-$ Create a client class that tests your sorting algorithms for value of N $($number employees in the list$)$ where N goes from $1,000$ to $100,000,000$ increasing by a multiple of $10$ each time. i$.$e$.$ N goes from $1,000$ to $10,000,$ to $100,000$ to $1,000,000...$

$-$ For each value of N time the following operations

o Generate an array of N employees

o Sort the employee array on name using the merge sort

o Sort the employee array on dept using the quick sort

o Sort the employee array on id using the bubble sort

o Sort the employee array on hired using the enhanced bubble sort.

o Sort the employee array on name using the insertion sort

o Sort the employee array on id using the selection sort

o Sort the employee array using the radix sort so that

$$ All employees are sorted by department

$$ Within a department grouping all the employees are sorted by hire date

$$ Within a department and hire date grouping all the employees are sorted by their name

$-$ Since the list of employees is long

o You will not print out the unsorted or sorted employee lists, instead,

o Print out the time that it takes to run each sort

o Suggestion:

$$ Make a test run of $100$ employees and inspect the results to make sure that they are correctly ordered but you should not display them in your Word document

$-$ Caution

o Make sure that you are passing the same unsorted list to each of your sort routines.

$$ Do this by making a copy of your initial list and passing the copy to the sort method.

$$ Make the copy before a call to a sort method.

$$ Your client should never have more than one copy of the initial list in memory at any given time.

o Each of your sort methods should sort the copy of the initial list.

o For each sort make sure that the sorted list is deleted before moving on to the next sort method.

o At any given time, you should have at most two list in memory