The focus of this assignment is the search Algorithms. After seeing and hearing about the two basic search algorithms (linear and binary), this lab will help put these ideas to use. Here we have a starter code for each of these.
import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.Scanner; public class LinearVsBinarySearch { public static long linSteps,binSteps,bin2Steps; public static ArrayList<String> readDataFile(String fileName){ ArrayList<String> result=new ArrayList<String>(); File dataFile = new File(fileName); if (dataFile.exists()) { try{ FileReader inFile = new FileReader(dataFile); BufferedReader inStream = new BufferedReader(inFile); String newLine; newLine = inStream.readLine(); while (newLine!=null){ result.add(newLine); newLine = inStream.readLine(); } inStream.close(); } catch (IOException e){} } return result; } private static void showNameData(String n){ String[] d=n.split(" "); System.out.println("Popularity for "+d[0]+": (rank order)"); for (int i=1; i<12;i++){ System.out.print((1890+10*i)+": "); int rank=100-Integer.parseInt(d[i]); if (d[i].equals("0")) rank=0; for(int j=rank; j>0; j-=2) System.out.print("X"); System.out.println(" "+d[i]); } } public static void main(String[] args) { Scanner kb=new Scanner(System.in); ArrayList<String> names=readDataFile("names-data.txt"); System.out.println("Read "+names.size()+" names. Ready to Search SSN Name data"); System.out.print("type \"quit\" to end\nSearch for: "); String input=kb.nextLine(); while (!input.equals("quit")){ // Do linear search long linearTime=System.currentTimeMillis(); linSteps=0; int i=linearSearch(input, names); linearTime=System.currentTimeMillis()-linearTime; // Do binary Search long binaryTime=System.currentTimeMillis(); binSteps=0; i=binarySearch(input,names); binaryTime=System.currentTimeMillis()-binaryTime; bin2Steps=0; i=binarySearch2(input,names); //Report our findings if(i<0) { System.out.println("not found"); }else { showNameData(names.get(i)); } System.out.println("Linear search took "+linearTime+" ms, "+linSteps+" steps"); System.out.println("Binary search took "+binaryTime+" ms, "+binSteps+" steps"); System.out.println("Binary2 search took "+bin2Steps+" steps"); System.out.println("type \"quit\" to end\nSearch for: "); input=kb.nextLine(); } System.out.println("Ok. Data gathered from http://www.ssa.gov/OACT/babynames/"); } /** * liner Search of n in the first word of the ArrayList list * @param n name to search * @param list the ArrayList<String> to search * @return */ private static int linearSearch(String n, ArrayList<String> list){ int result=-1; for(int i=0; i<list.size(); i++) { linSteps++; String entry=list.get(i); entry=entry.substring(0,entry.indexOf(" ")); if (n.equals(entry))result=i; } return result; } private static int binarySearch(String n, ArrayList<String> list){ int low=0; int high=list.size(); int mid; while (low<high){ binSteps++; mid=(low+high)/2; String entry=list.get(mid); entry=entry.substring(0,entry.indexOf(" ")); if (entry.compareTo(n)<0) { low=mid+1; }else{ high=mid; } } binSteps++; if (low<list.size()){ String entry=list.get(low); entry=entry.substring(0,entry.indexOf(" ")); if (entry.equals(n))return low; } return -1; } private static int binarySearch2(String n, ArrayList<String> list){ int low=0; int high=list.size()-1; int mid; while (low<high){ bin2Steps++; mid=(low+high)/2; String entry=list.get(mid); entry=entry.substring(0,entry.indexOf(" ")); if (entry.compareTo(n)>0) { high=mid-1; }else if (entry.compareTo(n)<0){ low=mid+1; }else return mid; //found } return -1; //not found } }
/** * class Employee is a data record for an employee. * * @author Chris Thiel * @version 15 Jan 2009 */ public class Employee { // instance variables - replace the example below with your own public String job; public String fullName; public String lastName; public String phone; public String SSN; // just to make up a string of d random digits: private String rand(int d){ int min=1; for (int i=0; i<d-1; i++) min*=10; int result = min+(int)(9.0*min*Math.random()); return Integer.toString(result); } /** * The Constructors for objects of class Employee * are used to either read all the info, or * to make up phoney SSN and telephone numbers. */ public Employee(String j, String n) { job=j; fullName=n; lastName=n.substring(n.lastIndexOf(" ")+1); phone="("+rand(3)+") "+rand(3)+"-"+rand(4); SSN=rand(3)+"-"+rand(2)+"-"+rand(4); } public Employee(String[] s) { job=s[0]; fullName=s[1]; lastName=s[2]; phone=s[3]; SSN=s[4]; } public String getName (){ return fullName; } public String getLastName (){ return lastName; } public String getPhone (){ return phone; } public String getSSN (){ return SSN; } public String getJob (){ return job; } }
import java.io.*; import java.text.DecimalFormat; import java.util.ArrayList; import java.awt.*; import java.awt.event.*; import javax.swing.*; /** * Class StaffDirectory - write a description of the class here * * @author Chris Thiel * @version 15 Jan 2009 */ public class StaffDirectory extends JApplet implements ActionListener { // instance variables - replace the example below with your own private int x; TextArea textArea; ArrayList<Employee> list; Button sortName; Button sortJob; Button searchName; Button searchJob; TextField searchFor; String message; /** * Called by the browser or applet viewer to inform this JApplet that it * has been loaded into the system. It is always called before the first * time that the start method is called. */ public void init() { // this is a workaround for a security conflict with some browsers // including some versions of Netscape & Internet Explorer which do // not allow access to the AWT system event queue which JApplets do // on startup to check access. May not be necessary with your browser. JRootPane rootPane = this.getRootPane(); rootPane.putClientProperty("defeatSystemEventQueueCheck", Boolean.TRUE); list=new ArrayList<Employee>(); textArea=new TextArea("Added the following:",25,70); textArea.setEditable(false); setLayout(new FlowLayout()); sortName = new Button("Sort by Name"); sortName.addActionListener(this); sortJob = new Button("Sort by Job"); sortJob.addActionListener(this); add(sortName); add(sortJob); setSize(700,500); add(textArea); searchFor = new TextField(30); add(searchFor); searchName = new Button("Search Names"); searchName.addActionListener(this); searchJob = new Button("Search Job"); searchJob.addActionListener(this); add(searchName); add(searchJob); File dataFile = new File("CarTalkStaff.tab"); if (dataFile.exists()) { message="Car Talk Staff"; try{ FileReader inFile = new FileReader(dataFile); BufferedReader inStream = new BufferedReader(inFile); String newLine; newLine = inStream.readLine(); int i=0; while (newLine!=null){ i++; String[] s= newLine.split("\t"); Employee e=new Employee(s); list.add(e); textArea.append("\n"+i+". "+e.getJob()+" -- "+e.getName()); newLine = inStream.readLine(); } inStream.close(); textArea.select(0,0); } catch (IOException e){ message="File \"CarTalkStaff.tab\" not Found"; } } } /** * Paint method for applet. * * @param g the Graphics object for this applet */ public void paint(Graphics g) { // simple text displayed on applet g.setColor(Color.white); g.fillRect(0, 0, getWidth(), getHeight()); g.setColor(Color.black); g.drawString(message, 20, 20); g.setColor(Color.blue); g.drawString("created by BlueJ", 500, 20); } /** * showRecord will return a String describing the * the desired Employee from the list. */ public String showRecord(int i){ String result="Record not found"; if (i>=0 && i<list.size() ){ Employee e=list.get(i); result=e.getJob()+"\n"; result+=e.getName()+"\n"; result+="SSN: "+e.getSSN()+"\n"; result+="Telephone: "+e.getPhone()+"\n"; } return result; } /** * Here is the implementaqtion of the ActionPerformed interface * * This interface requred us to define a specific method called * actionPerformed, which will handle any ActionEvent which * is generated when our user pressed a button. */ public void actionPerformed (ActionEvent ev){ Object source = ev.getSource(); if (source == sortName){ list=mergeSort(list, "lastName"); message="Sorting by last name"; textArea.setText("Names and Jobs"); for (Employee e:list) textArea.append( "\n"+e.getName()+" -- "+e.getJob() ); } if (source == sortJob){ message="Sorting by job"; list=mergeSort(list, "job"); textArea.setText("Jobs and Names"); for (Employee e:list) textArea.append( "\n"+e.getJob()+" -- "+e.getName()); } if (source == searchName){ String userInput = searchFor.getText(); message="Searching Names for "+userInput; textArea.setText(message); list=mergeSort(list, "lastName"); int record =findLastName(userInput,list); textArea.setText(showRecord(record)); } if (source == searchJob){ String userInput = searchFor.getText(); message="Searching Jobs for "+userInput; int record =findJob(userInput,list); textArea.setText(showRecord(record)); } repaint(); } public static ArrayList<Employee> mergeSort(ArrayList<Employee> a, String field) { if (a.size()<=1) return a; int middle=a.size()/2; ArrayList<Employee> left=new ArrayList<Employee>(); ArrayList<Employee> right=new ArrayList<Employee>(); for (int i=0;i<middle; i++) { left.add(a.get(i)); } for (int i=middle;i<a.size();i++) { right.add(a.get(i)); } left =mergeSort(left, field); right=mergeSort(right, field); ArrayList<Employee> result=merge(left,right, field); return result; } private static ArrayList<Employee> merge(ArrayList<Employee> left, ArrayList<Employee> right, String field) { ArrayList<Employee> result=new ArrayList<Employee>(); while (left.size()>0 && right.size()>0) { String theLeft="",theRight=""; if (field.equals("lastName")) { theLeft=(left.get(0)).getLastName(); theRight=(right.get(0)).getLastName(); } if (field.equals("job")) { theLeft=(left.get(0)).getJob(); theRight=(right.get(0)).getJob(); } if (theLeft.compareTo(theRight)<0){ result.add(left.get(0)); left.remove(0); }else { result.add(right.get(0)); right.remove(0); } } //Since left or right ran out, we attach the remainder to the result while (left.size()>0) { result.add(left.get(0)); left.remove(0); } while (right.size()>0) { result.add(right.get(0)); right.remove(0); } return result; } public int findLastName(String last, ArrayList<Employee> list) { int n=list.size(); int result=-1; for(int i=0; i<n; i++){ String currentName= (list.get(i)).getName(); if (currentName.indexOf(last)>=0 ) result=i; } return result; } public int findJob(String job, ArrayList<Employee> list) { int n=list.size(); int result=-1; // Insert your code here! return result; } }