Question

Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort

I need it in Java with comments and I need the input file to be placed with Scanner not BufferedReader Please help I need Class River Class CTRiver and Class Driver

Class River describes river’s name and its length in miles. It provides accessor methods (getters) for both variables, toString() method that returns String representation of the river, and method isLong() that returns true if river is above 30 miles long and returns false otherwise.

Class CTRivers describes collection of CT rivers. It has no data, and it provides the following service methods. None of the methods prints anything, except method printLongRiversRec, which prints all long rivers. Input parameter n in all methods is number of occupied elements in the list.

// Prints all long rivers in the list. Print them in same order as they were in the list . List can be

// empy or not.

• void printLongRiversRec(River[] list, int n)

// Returns index for the river object with given name. Returns -1 for unsuccessful search. List can

// be empy or not.

• int linearSearch(River[] list, int n, String name)

// Returns ArrayList of rivers with length between min and max inclusive. If no such river was found,

// method returns an empty Arraylist<River>. List can be empy or not.

• ArrayList <River> searchRange(River[] list, int n, int min, int max)

// Sorts list of rivers by comparing them by names. Apply selection sort recursively. List of rivers can be

// empy or nonempty. Empty list and list with one river only are sorted. Lists with two or more rivers are

// sorted by swapping last river in the list with river object that has name that is last in lexicographic order // in the array, and after that recursively sorting sublist of first n-1 rivers.

• void sortByNameRec(River[] list, int n)

// PRECONDITION: Method assumes that input list is sorted by names. First and last are indices of the first

// and last river of the current sublist. Method returns index of river object with given name or returns -1

// if none of the rivers has that name. List of rivers can be empy or not.

• int binarySearchRec(River[] list, int first, int last, String name)

The three methods highlighted in yellow must be implemented recursively.

File “input.txt”

Naugatuck   40

Pawcatuck   34

Quinebaug   69

Shepaug   26

Connecticut   407

Still   25

Quinnipiac   46

Housatoic 139

Class Driver has main method in it. Read data from the input file "input.txt" into an array of River objects, named riverList, and keep track of number of rivers stored in variable counter. Array riverList has capacity 100. Input file should be as shown. Program should work for any input file with up to 100 rivers in it.

• Print all long rivers.
• Apply one successful and one unsuccessful linear search.
• Print all rivers with length between min and max (min and max are provided by user). Must use for each loop in the main method to print resulting ArrayList<River> returned by method searchRange .
• Sort myList by river names, and print sorted list.
• Apply one successful and one unsuccessful binary search on sorted list.

Must print appropriate explanation in English of all steps performed in outcome.

SUBMIT:

• Copy of the code for each class and input file in separate rectangle.
• Picture of program run from BlueJ.
• Picture of UML diagram.

Answer 1

PROGRAM :

River.java
public class River
{
private String name;
private int length;

public River(String name, int length) {
this.name = name;
this.length = length;
}

public String getName() {
return name;
}

public int getLength() {
return length;
}

@Override
public String toString()
{
String str = String.format("%-12s %10d",name,length);
return str;
}

}

CTRiver.java

import java.util.ArrayList;

public class CTRivers
{
public void printListRec(River[] list, int n)
{
for(int i=0;i<n;i++)
System.out.println(list[i]);
}
public int linearSearch(River[] list, int n, String name)
{
for(int i=0;i<n;i++)
{
if(list[i].getName().equalsIgnoreCase(name))
return i;
}
return -1;
}
public ArrayList <River> searchRange(River[] list, int n, int min, int max)
{
ArrayList <River> riverList=new ArrayList<>();
for(int i=0;i<n;i++)
{
if(list[i].getLength()>=min && list[i].getLength()<=max)
riverList.add(list[i]);
}
return riverList;
}
public void sortByNameRec(River[] list, int n)
{
selectionSort(list,0,n);
}
//these are the helper function
private static void swap(River[] arr, int i, int j)
{
River temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Recursive function to perform selection sort on sub-array arr[i..n-1]
private static void selectionSort(River[] arr, int i, int n)
{
// find the minimum element in the unsorted sub-array[i..n-1]
// and swap it with arr[i]
int min = i;
for (int j = i + 1; j < n; j++)
{
// if arr[j] element is less, then it is the new minimum
if (arr[j].getName().compareTo( arr[min].getName() ) < 0)
{
min = j; // update index of min element
}
}
// swap the minimum element in sub-array[i..n-1] with arr[i]
swap(arr, min, i);
if (i + 1 < n)
{
selectionSort(arr, i + 1, n);
}
}
River binarySearchRec(River[] list, int n, String name)
{
int index=binarySearch(list, 0, n-1, name);
if(index!=-1)
return list[index];
return null;
}
private static int binarySearch(River 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[mid].getName().equals(x))
return mid;

// If element is smaller than mid, then it can only
// be present in left subarray
if ((arr[mid].getName().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;
}
public void insertInOrder(River[] list, int n, River river)
{
int i=0;
for(i=0;i<n;i++)
{
if(list[i].getName().compareTo(river.getName())>0)
break;
}
for(int j=n; j > i; j--)
{
list[j] = list[j-1];
}
list[i] = river;
}
}

Driver.java
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Driver {

/**
* @param args the command line arguments
*/
public static void main(String[] args)
{
BufferedReader reader;
River []MyList=new River[100];
CTRivers ctObject=new CTRivers();
int count=0;
try
{
reader = new BufferedReader(new FileReader("input.txt"));
String line = reader.readLine();
while (line != null)
{
String[] splited = line.split(" ");
MyList[count]=new River(splited[0],Integer.parseInt(splited[1]));
line = reader.readLine();
count++;
}
reader.close();
} catch (IOException e)
{
e.printStackTrace();
}
System.out.printf("%-7s %15s\n","River Name","Length");
ctObject.printListRec(MyList, count);
int index=ctObject.linearSearch(MyList, count, "Quinnipiac");

System.out.println("\n\nUsing linear search\n");
if(index>=0)
System.out.println("Quinnipiac is in the array at location :"+index);

index=ctObject.linearSearch(MyList, count, "Ganga");
if(index>=0)
System.out.println("Ganga is in the array at location :"+index);
else
System.out.println("Ganga is not in the array");

ctObject.sortByNameRec(MyList, count);
System.out.println("\n\nAfter sorting\n");
System.out.printf("%-7s %15s\n","River Name","Length");
ctObject.printListRec(MyList, count);

System.out.println("\n\nUsing binary search\n");

River r=ctObject.binarySearchRec(MyList, count, "Pawcatuck");

if(r==null)
System.out.println("Pawcatuck is not available in the list");
else
System.out.println("Pawcatuck is available in the list");

r=ctObject.binarySearchRec(MyList, count, "Jamuna");

if(r==null)
System.out.println("Jamuna is not available in the list");
else
System.out.println("Jamuna is available in the list");

ctObject.insertInOrder(MyList, count, new River("Farmington",47));
count++;
ctObject.insertInOrder(MyList, count, new River("Ganga",187));
count++;

System.out.println("\n\nAfter adding 2 new river the list is :");
ctObject.printListRec(MyList, count);

}

OUTPUT :