java recursion In class, you learned about some algorithms for sorting and searc

Question

java recursion

In class, you learned about some algorithms for sorting and searching collections, as well as how to write recursive methods.

The chocolate factory has recently determined that, while making and selling chocolate is nice, They want to hire more people. But they have a problem: they don’t want to hire the same person twice. Whenever they interview a candidate, they have to know whether that candidate has already been hired Your task will be to create a list of the names of the employees that have already been hired and provide a way for a user to determine whether a new candidate’s name is already in the list of hired employees.

First, you MUST create a list of the names of hired employees using ARRAY LIST . These are the names of the employees so far:

(Frank Frayburn, Christine Chriky, Scott Scofield, John Johnson, Catherine Cathright, Sarah Sargasso, Alex Alexander, Ida Id, Kevin Kevilry, Bailey Baines, Zeke Zephyr, Yancy Yankle, Diane DiAnthony, Xavier eXeter, Elaine Elosky)

If the user inputs any of the names from the list above it shoud display "“Do not hire this employee again!”?.

Then, at the console, query the user for a candidate’s name. If the user types 0, exit the program. Otherwise, take the given candidate name and search the list of employees:

1) Search using a RECURSIVE implementation of binary search.

2) Binary search requires a sort, so implement a RECURSIVE version of either selection sort, insertion sort, or merge sort. Not BUBBLE SORT

You must use recursion to implement these methods and you cannot use built-in Java implementations of sort or search

If the candidate name is found in the list of employees, output “Do not hire this employee again!” If the candidate name is not found in the list of employees, output “Hire this person right away!” Continue to query the user for candidate names until the user types 0.

Explanation / Answer

import java.util.*;
public class HelloWorld{

public static void main(String []args){
Scanner sc = new Scanner(System.in);
ArrayList<String> hired = new ArrayList();
hired.addAll(Arrays.asList("Frank Frayburn", "Christine Chriky", "Scott Scofield", "John Johnson", "Catherine Cathright", "Sarah Sargasso", "Alex Alexander", "Ida Id", "Kevin Kevilry", "Bailey Baines", "Zeke Zephyr", "Yancy Yankle", "Diane DiAnthony", "Xavier eXeter", "Elaine Elosky"));
hired = mergeSort(hired);
String inp = "";
while(1==1){
System.out.println("Enter name: ");
inp=sc.nextLine();
if(inp.equals("0"))
{
break;
}
if(binarySearch(hired,0,hired.size()-1,inp)!=-1){
System.out.println("Do not hire this employee again!");
}
else{
System.out.println(inp+" has not been hired previously");
}

}
}
public static int binarySearch(ArrayList<String> arr, int l, int r, String x)
{
if (r>=l)
{
int mid = l + (r - l)/2;

// If the element is present at the
// middle itself
if (arr.get(mid).equalsIgnoreCase(x))
return mid;

// If element is smaller than mid, then
// it can only be present in left subarray
if (arr.get(mid).compareTo(x)> 0)
return binarySearch(arr, l, mid-1, x);

// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, r, x);
}

// We reach here when element is not present
// in array
return -1;
}
//below is the code for merge sort of an arraylist of strings
public static ArrayList<String> mergeSort(ArrayList<String> whole) {
ArrayList<String> left = new ArrayList<String>();
ArrayList<String> right = new ArrayList<String>();
int center;

if (whole.size() == 1) { //if there is a single element return it
return whole;
} else {
center = whole.size()/2;
// copy the left half of whole into the left list
for (int i=0; i<center; i++) {
left.add(whole.get(i));
}

//copy the right half of whole into the new right arraylist
for (int i=center; i<whole.size(); i++) {
right.add(whole.get(i));
}

// Sort the left and right halves of the arraylist.
left = mergeSort(left);
right = mergeSort(right);

// Merge the results
merge(left, right, whole);
}
return whole;
}

private static void merge(ArrayList<String> left, ArrayList<String> right, ArrayList<String> whole) {
int leftIndex = 0;
int rightIndex = 0;
int wholeIndex = 0;

// As long as there are elements in the the left or the right ArrayList,
// keep taking the smaller of left.get(leftIndex)
// or right.get(rightIndex) and adding it at both.get(bothIndex).
while (leftIndex < left.size() && rightIndex < right.size()) {
if ( (left.get(leftIndex).compareTo(right.get(rightIndex))) < 0) {
whole.set(wholeIndex, left.get(leftIndex));
leftIndex++;
} else {
whole.set(wholeIndex, right.get(rightIndex));
rightIndex++;
}
wholeIndex++;
}

ArrayList<String> rest;
int restIndex;
if (leftIndex >= left.size()) {
// The left ArrayList has been used up
rest = right;
restIndex = rightIndex;
} else {
// The right ArrayList has been used up
rest = left;
restIndex = leftIndex;
}

// Copy the rest if any arraylist have any more elements.
for (int i=restIndex; i<rest.size(); i++) {
whole.set(wholeIndex, rest.get(i));
wholeIndex++;
}
}
}

Sample running:

$java HelloWorld

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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