Goal Build three search algorithms to find matching names in two different lists
ID: 3845473 • Letter: G
Question
Goal
Build three search algorithms to find matching names in two different lists using Java.
____
Problem
1. Read two input files, each containing a sorted list of first names. Assume the input
files will be in the working directory and will be named list1.txt and list2.txt.
2. Find the matching names using three different algorithms. The first list could be
considered the reference list, and the second list would contain the list of names to be
found.
(a) The first search method, named findByBruteForce should use a linear search of
the target list. The inputs to this function will be the two lists.
(b) The second search method, named findByBinarySearch should implement a binary
search algorithm. The inputs to this function will be the two lists.
(c) The third search method, named findByFinesse should implement the tokenized
search discussed in class and summarized below.
Start two markers, one for each list, at the beginning of each list.
Repeat the process outlined below
Compare the two marked items
If both are equal print the name and advance both markers one element.
else since they're not equal advance the marker that comes first, alphabetically.
EDIT: Go through the list tokenizing word by word. Then compare letter by letter to see if the words are the same. IF they are different then move the marker (A < B < C) alphabetically on the list that it applies to. IF they are the same then move both markers by one and print the name. Thanks for the help.
____
Testing
There are three _les supplied with the assignment:
1. list1.txt which contains the list of five names.
2. list2.txt also contains a list of five names.
3. expectedOutput.txt which is a redirection of the output. This is to be used as the
baseline for running the diff command to confirm the output results and formatting.
(See the Sample Output below for an example of how diff will be used.)
____
Sample output
java Lab01
list1.txt contains:
Akira
Bart
Chase
Declan
Duffman
list2.txt contains:
Atkins
Blinky
Carl
Duffman
Lisa
The method findByBruteForce found the following match(es):
Duffman
The method findByBinarySearch found the following match(es):
Duffman
The method findByFinesse found the following match(es):
Duffman
java Lab01 >myOutput.txt
diff myOutput.txt expectedOutput.txt
Note The diff command will report any differences between the input files. No output means there is no differences between the input files.
Explanation / Answer
Here is the code for the question. Output file contents is also shown. Please don't forget to rate the answer if it helped. Thank you very much.
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
public class SearchAlgorithms {
//loads the contents specified file into and an arraylist and returns the list
private static ArrayList<String> loadFile(String filename) throws FileNotFoundException
{
Scanner scanner = new Scanner(new File(filename));
ArrayList<String> list = new ArrayList<String>();
while(scanner.hasNext())
{
String str = scanner.next();
list.add(str);
}
scanner.close();
return list;
}
// words from list2 are searched in list1 using linear search algorithm. words that
//were found in are printed into writer object
private static void findByBruteForce(ArrayList<String> list1, ArrayList<String> list2,PrintWriter writer)
{
String search;
boolean found;
writer.write(" The method findByBruteForce found the following match(es): ");
for(int i = 0; i < list2.size()-1; ++i) //loop through list2
{
search = list2.get(i);
found = false;
//search the word in list1 linearly
for(int j = 0; j < list1.size() && !found; ++j)
{
if(list1.get(j).equals(search))
found = true;
}
//if found , write into writer
if(found)
writer.write(search+" ");
}
}
// words from list2 are searched in list1 using binary search algorithm. words that
//were found in are printed into writer object
private static void findByBinarySearch(ArrayList<String> list1, ArrayList<String> list2,PrintWriter writer)
{
String search;
boolean found;
int start, end, mid, cmp;
writer.write(" The method findByBinarySearch found the following match(es): ");
for(int i = 0; i < list2.size(); ++i) //loop through words in list2
{
search = list2.get(i);
//reset all variables
found = false;
start = 0;
end = list1.size()-1;
while(!found && start <= end)
{
mid = (start + end)/2;
cmp = search.compareTo(list1.get(mid));
if(cmp == 0)
found=true;
else if(cmp < 0 )
end = mid - 1;
else
start = mid + 1;
}
if(found) //write to writer if found
writer.write(search+" ");
}
}
// words from list2 are searched in list1 using Finesse method. words that
//were found in are printed into writer object
private static void findByFinesse(ArrayList<String> list1, ArrayList<String> list2,PrintWriter writer)
{
writer.write(" The method findByFinesse found the following match(es): ");
int idx1 = 0, idx2 =0;
String word1, word2;
int cmp;
while(idx1 < list1.size() && idx2 < list2.size())
{
word1 = list1.get(idx1);
word2 = list2.get(idx2);
cmp = word1.compareTo(word2);
if(cmp == 0) //words matched
{
writer.write(word1);
idx1++;
idx2++;
}
else if(cmp < 0) //word1 is alphabetically before word2
idx1++;
else //word2 is alphabetically before word1
idx2++;
}
}
public static void main(String[] args) {
try {
//load the files into 2 lists
ArrayList<String> list1 = loadFile("list1.txt");
ArrayList<String> list2 = loadFile("list2.txt");
//writer for output file
PrintWriter writer = new PrintWriter(new File("output.txt"));
findByBruteForce(list1, list2, writer);
findByBinarySearch(list1, list2, writer);
findByFinesse(list1, list2, writer);
writer.close();
} catch (FileNotFoundException e) {
System.out.println(e.getMessage());
}
}
}
input file list1.txt
Akira
Bart
Chase
Declan
Duffman
input file list2.txt
Atkins
Blinky
Carl
Duffman
Lisa
output file output.txt
The method findByBruteForce found the following match(es):
Duffman
The method findByBinarySearch found the following match(es):
Duffman
The method findByFinesse found the following match(es):
Duffman
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.